Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 17F / b / 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. HenceThis is the relevant 3-connected case of Brooks' theorem.

Solved by gpt-5.6-sol high.