Brooks' theorem

Statement

Let $G$ be a finite connected simple graph with maximum degree $\Delta$. Suppose that $G$ is not a complete graph and not a cycle graph of odd length. Then $\chi(G) \le \Delta$.

Remarks

A greedy colouring gives $\chi(G) \le \Delta + 1$ for every graph. Brooks' theorem improves this bound by $1$ in all other cases. The two exceptions need $\Delta + 1$ colours: $\chi(K_n) = n$ with $\Delta = n - 1$, and an odd cycle has $\chi = 3$ with $\Delta = 2$.

History

R. Leonard Brooks published the theorem in 1941.

Explanations

L1 human

If each vertex has at most $\Delta$ neighbours, then $\Delta + 1$ colours are always enough. Brooks' theorem says that $\Delta$ colours are enough, except for complete graphs and odd cycles.