Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 17F / a / Solution

A proper $k$-coloring assigns one of $k$ colors to each vertex so adjacent vertices receive different colors. The chromatic number $\chi (G)$ is the least such $k$. Order the vertices arbitrarily and color greedily. At most $\Delta (G)$ colors are forbidden by previously colored neighbors, soEquality occurs for every possible maximum degree: use $K_1$ for $\Delta =0$, $K_2$ for $\Delta =1$, an odd cycle for $\Delta =2$, and $K_{\Delta +1}$ for every $\Delta \ge 3$.