Brooks' Theorem tanka

Greedily colour,
ensuring neighbours follow
all except the last.

Choose the last vertex wisely:
friend of few or of leaders.

Brooks' Theorem says:

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

Bondy's proofShort proofs of classical theorems. Journal of Graph Theory 44(3). J Adrian Bondy (2003). breaks this into a few cases.

  1. If GG is not regular, take a depth-first ordering of GG rooted at a vertex rr of smaller-than-maximum degree and then greedily colour GG in the reverse order. As we colour each vertex vv other than rr, 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Δ(G) - d(v) + 1 colours still available for vv. When we get to colour rr, there's no other vertices left, but since d(r)<Δ(G)d(r) < Δ(G) we know there's still at least one colour available.

  2. If GG has a cut vertex xx, we can break GG into two halves whose intersection is xx, colour each of them separately by case 1, and put them together.

  3. If GG is 2-connected and has a depth-first tree in which some vertex xx has at least two children yy and zz. Since yy and zz are siblings in the depth-first tree they have to be non-adjacent, and it can be shown that G{y,z}G - \{y, z\} is still connected. You can then construct an ordering where yy and zz come first, xx 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 xx as adjacent to the two "leaders" in the order, yy and zz.) A greedy colouring with respect to this order will use at most Δ(G)Δ(G) colours.

  4. Finally, if every depth-first tree of GG is a path, then every Hamilton path of GG 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 GG is not a chordless cycle, it has to be a clique or a complete bipartite graph. Since bipartite graphs have χ(G)=2Δ(G)χ(G) = 2 ≤ Δ(G), the only exceptions to the theorem are odd cycles and cliques.