Brooks' Theorem

Before we go on to see Brooks' theorem, we're first going to prove a very similar theorem that has less strength regarding the chromatic number of a graph.

Theorem 1: If $G$ is a (simple) graph then $\chi (G) \leq \Delta (G) + 1$.

• Proof: Suppose that $G_1$ is a simple graph with one vertex. Because $G_1$ is simple, there are no loops and hence the graph has no edges. Hence it follows that $\chi (G_1) = 1$ and $\Delta (G_1) = 0$. Hence $\chi (G) ≤ \Delta (G_1) + 1$, and more specifically $1 = 1$. So the base step is proven.

• Now assume that all simple graphs $G_n$ on $n$ vertices have the property that $\chi (G_n) ≤ \Delta (G_n) + 1$. We want to show that all graphs $G_{n+1}$ on $n+1$ vertices have the property that $\chi (G_{n+1}) ≤ \Delta (G_{n+1}) + 1$.

• Let $G_{n+1}$ be a simple graph. Delete a vertex from $G_{n+1}$ to get a simple graph $G_n$. By our induction hypothesis we know that $\chi (G_n) ≤ \Delta (G_n) + 1$. The vertex we deleted, let's call it $v_1$ has $\deg (v_1) ≤ \Delta (G_{n+1})$. Because of this, we can choose the $(\Delta (G) + 1)^{\mathrm{th}}$ colour or possibly one of the other colours when we reinsert this vertex. Hence $\chi (G_{n+1}) ≤ \Delta (G_{n+1}) + 1$. $\blacksquare$

Theorem 2 (Brooks' Theorem): If $G$ is a connected (simple) graph and is not a complete graph or a cycle on an odd number of vertices, then the chromatic number satisfies the inequality $\chi (G) ≤ \Delta (G)$.

We are going to omit the proof of this theorem, however, we note that this theorem is quite a bit stronger than Theorem 1 if we are given a graph that isn't an odd cycle or complete.