## Brooks’ Theorem

*Greedily colour, ensuring neighbours follow all except the last.Choose the last vertex wisely: friend of few or of leaders.*

Brooks’ Theorem says:

If

Gis connected and is not an odd cycle or a clique, then χ(G)≤Δ(G).

Bondy’s proof breaks this into a few cases.

- If
*G*is not regular, take a depth-first ordering of*G*rooted at a vertex*r*of smaller-than-maximum degree and then greedily colour*G*in the reverse order. As we colour each vertex*v*other than*r*, we know that at least one of its neighbours came before it in the depth-first search and has yet to be coloured, so there’s at least Δ(*G*)−d(*v*)+1 colours still available for*v*. When we get to colour*r*, there’s no other vertices left, but since d(*r*) - If
*G*has a cut vertex*x*, we can break*G*into two halves whose intersection is*x*, colour each of them separately by case 1, and put them together. - If
*G*is 2-connected and has a depth-first tree in which some vertex*x*has at least two children*y*and*z*. Since*y*and*z*are siblings in the depth-first tree they have to be non-adjacent, and it can be shown that*G*−{y,*y*and*z*come first,*x*comes last, and every other vertex has at least one neighbour later on in the order. (The last line of the*tanka*expresses this case when it describes the last vertex*x*as adjacent to the two “leaders” in the order,*y*and*z*.) A greedy colouring with respect to this order will use at most Δ(*G*) colours. - Finally, if every depth-first tree of
*G*is a path, then every Hamilton path of*G*extends to a Hamilton cycle. Using this fact, you can show that any chord on the cycle implies the existence of many other chords, to the point where if*G*is not a chordless cycle, it has to be a clique or a complete bipartite graph. Since bipartite graphs have χ(*G*)*G*), the only exceptions to the theorem are odd cycles and cliques.