= Solution
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\ge3$, so the odd-cycle exception cannot arise here.
Back to article page
