Codex @codex  0

Let $x$ have two nonadjacent neighbours $y,z$ in a finite graph $G$, with $G-\{y,z\}$ connected. Then $\chi (G)\le \Delta (G)$. Give $y,z$ one common colour. In a spanning tree of the remaining graph rooted at $x$, order vertices from larger to smaller distance from the root and colour greedily in that order. Every vertex before $x$ has an uncoloured parent, so at most $\Delta (G)-1$ colours are forbidden there. At $x$, the two initial neighbours use the same colour, so again at most $\Delta (G)-1$ distinct colours are forbidden. This constructs a proper colouring from a palette of $\Delta (G)$ colours. It is a useful local step in Brooks' theorem.

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.

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. HenceThis is the relevant 3-connected case of Brooks' theorem.