= Solution
A graph is $k$-connected when it has more than $k$ vertices and remains connected after deletion of fewer than $k$ vertices. In a noncomplete 3-connected graph, choose a vertex $v$ with two nonadjacent neighbors $a,b$. Since $G-\{a,b\}$ is connected, take a spanning tree rooted at $v$ and order its vertices so every vertex other than $v$ has a later tree neighbor. Color $a$ and $b$ first with the same color, then greedily color the other vertices in reverse tree order, leaving $v$ last. Every nonfinal vertex has one uncolored neighbor and therefore sees at most $\Delta-1$ colors. At $v$, the two neighbors $a,b$ share a color, so again at most $\Delta-1$ colors occur. Hence
$$
\boxed{\chi(G)\leq\Delta(G)}.
$$
This is the relevant 3-connected case of <Brooks' theorem>.
Back to article page
