Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 3 / 17F / a

The Brooks' theorem states that a finite connected simple graph with maximum vertex degree $\Delta$ has chromatic number at most $\Delta$, unless it is a complete graph or an odd cycle graph; those exceptions have chromatic number $\Delta +1$.

First, if the graph is not regular, choose a vertex $v$ of degree less than $\Delta$ and a spanning tree rooted at $v$. Order vertices with every child before its parent, and apply the greedy coloring algorithm. Every vertex except $v$ has an as-yet uncolored parent, so has at most $\Delta -1$ colored neighbors; $v$ also has fewer than $\Delta$ neighbors. Thus $\Delta$ colors suffice. This justifies reducing to the regular case.

Now let $G$ be regular, 3-connected and not complete. A shortest path between two nonadjacent vertices contains an induced two-edge path $a,v,b$ with $a,b$ nonadjacent. By 3-connectivity, $G-\{a,b\}$ is connected. Color $a,b$ with the same color. Choose a spanning tree of the remaining graph rooted at $v$ and color its vertices in child-before-parent order. Each vertex other than $v$ again has an uncolored parent and thus at most $\Delta -1$ already colored neighbors. At the last vertex $v$, the two neighbors $a,b$ share a color, so its $\Delta$ neighbors use at most $\Delta -1$ distinct colors. A color is therefore available at every step, proving $\boxed{\chi (G)\le \Delta }$ in the required 3-connected noncomplete case. A 3-connected graph has $\Delta \ge 3$, so the odd-cycle exception cannot arise here.