= 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, so
$$
\boxed{\chi(G)\leq\Delta(G)+1}.
$$
Equality 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\geq3$.
Back to article page
