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 G is 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) < Δ(G) we know there’s still at least one colour available.
- 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, z} is still connected. You can then construct an ordering where 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) = 2 ≤ Δ(G), the only exceptions to the theorem are odd cycles and cliques.