Brooks' Theorem tanka
ensuring neighbours follow
all except the last.
Choose the last vertex wisely:
friend of few or of leaders.
Brooks' Theorem says:
If is connected and is not an odd cycle or a clique, then .
Bondy's proofShort proofs of classical theorems. Journal of Graph Theory 44(3). J Adrian Bondy (2003). breaks this into a few cases.
If is not regular, take a depth-first ordering of rooted at a vertex of smaller-than-maximum degree and then greedily colour in the reverse order. As we colour each vertex other than , 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 colours still available for . When we get to colour , there's no other vertices left, but since we know there's still at least one colour available.
If has a cut vertex , we can break into two halves whose intersection is , colour each of them separately by case 1, and put them together.
If is 2-connected and has a depth-first tree in which some vertex has at least two children and . Since and are siblings in the depth-first tree they have to be non-adjacent, and it can be shown that is still connected. You can then construct an ordering where and come first, 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 as adjacent to the two "leaders" in the order, and .) A greedy colouring with respect to this order will use at most colours.
Finally, if every depth-first tree of is a path, then every Hamilton path of 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 is not a chordless cycle, it has to be a clique or a complete bipartite graph. Since bipartite graphs have , the only exceptions to the theorem are odd cycles and cliques.