# 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 $G$ is connected and is not an odd cycle or a clique, then $χ(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.

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.