A Complete Proof of Brooks' Theorem

The Bound and Its Exceptions

A greedy coloring with a suitable vertex order can sometimes use the maximum degree \(\Delta(G)\) colors, rather than the general bound of \(\Delta(G)+1\). Brooks' theorem says that this sharper bound holds for every connected graph except complete graphs and odd cycles. The key is not simply to color in an arbitrary order: the proof arranges that most vertices have an earlier neighbor, while a final vertex has two neighbors already colored alike.

The exceptions are necessary. A complete graph \(K_r\) has \(\chi(K_r)=r\) and \(\Delta(K_r)=r-1\). An odd cycle has maximum degree \(2\), but needs \(3\) colors. The proof below establishes the bound for all other connected graphs.

Low-Degree Cases and Cut Vertices

First consider connected graphs with \(\Delta(G)\leq2\). A connected graph of maximum degree at most two is a path, a cycle, or a single vertex: starting at a vertex of degree at most one gives a path covering the graph; if there is no such vertex, following edges returns to the starting vertex and gives a cycle covering the graph. A path can be colored alternately with two colors, as can an even cycle. The single vertex and \(K_2\) are complete graphs, while an odd cycle is an exception in the theorem. This settles all connected graphs with \(\Delta(G)\leq2\).

For larger graphs, we use induction on the number of vertices. A vertex \(c\) is a cut vertex if deleting it disconnects the graph. The following reduction explains how to color a graph with a cut vertex using the theorem for smaller graphs.

Proof. Let \(C_1,\ldots,C_k\), where \(k\geq2\), be the vertex sets of the components of \(G-c\). For each \(i\), let \(H_i=G[C_i\cup\{c\}]\), the induced subgraph on \(C_i\cup\{c\}\). Each \(H_i\) is connected and has fewer vertices than \(G\). Write \(\Delta=\Delta(G)\); then \(\Delta(H_i)\leq\Delta\).

If \(H_i\) is complete, say \(K_r\), it needs \(r\) colors. The only way it could need more than \(\Delta\) colors is if \(r=\Delta+1\). In that case \(c\) has degree \(\Delta\) within \(H_i\), and it has at least one neighbor in another component of \(G-c\). Thus \(\deg_G(c)\geq\Delta+1\), contradicting the definition of \(\Delta\). So every complete \(H_i\) can be colored with at most \(\Delta\) colors. If \(H_i\) is an odd cycle, then \(c\) has two neighbors on that cycle and at least one neighbor outside it, so \(\Delta\geq3\); the cycle can therefore be colored with at most \(\Delta\) colors. Every other \(H_i\) satisfies the induction hypothesis, so it too can be colored with at most \(\Delta\) colors.

Choose a palette of \(\Delta\) colors. In each coloring, relabel the colors so that \(c\) receives the same color. The colorings then combine to color \(G\): different \(C_i\) have no edges between them, and every edge joining \(c\) to a component is already properly colored within its \(H_i\). This proves the reduction. \(\square\)

In particular, for the inductive proof it remains to treat connected graphs with no cut vertex. The one-vertex graph is complete, and a connected graph with at least three vertices and no cut vertex is called 2-connected.

A Greedy Ordering for 2-Connected Graphs

We first find the three vertices that make the ordering work. In a connected, noncomplete graph there are nonadjacent vertices \(a,b\). Choose a shortest \(a\)-\(b\) path, written \(p_0,p_1,\ldots,p_\ell\), where \(p_0=a\), \(p_\ell=b\), and \(\ell\geq2\). The vertices \(p_0\) and \(p_2\) cannot be adjacent: that edge would give a shorter \(a\)-\(b\) path. Thus, setting \(x=p_0\), \(v=p_1\), and \(y=p_2\), we have \(xv,vy\in E\) and \(xy\notin E\).

Now suppose \(G\) is 2-connected, and fix such \(x,v,y\). Consider the components of \(G-\{x,y,v\}\). Each has a neighbor in \(\{x,y,v\}\), since \(G\) is connected. In fact, each has a neighbor in \(\{x,y\}\). If a component had no neighbor in \(\{x,y\}\), all its neighbors outside itself would have to be \(v\). Deleting \(v\) would then separate that component from \(x\) and \(y\), making \(v\) a cut vertex. This contradicts 2-connectivity.

For each such component, choose a vertex adjacent to \(x\) or \(y\), and choose a spanning tree of the component rooted at that vertex. A spanning tree is a connected, cycle-free subgraph containing all vertices of the component. List its vertices with each parent before its children. Concatenate these lists, in any order of the components, to form the middle of the coloring order. Use the full order

Give \(x\) and \(y\) the same color first; they are nonadjacent, so this is proper on those two vertices. Each vertex in the middle has an earlier neighbor: a root is adjacent to \(x\) or \(y\), and every other vertex has its parent earlier. Since its total degree is at most \(\Delta(G)\), it has at most \(\Delta(G)-1\) earlier neighbors. At most that many colors are forbidden, so one of a palette of \(\Delta(G)\) colors is available.

Finally color \(v\). Both \(x\) and \(y\) are neighbors of \(v\) and have the same color. Therefore the colored neighbors of \(v\) use at most \(\deg(v)-1\leq\Delta(G)-1\) distinct colors: among its \(\deg(v)\) neighbors, the pair \(x,y\) contributes at most one color. At least one palette color remains for \(v\). This completes the greedy argument for a 2-connected graph with \(\Delta(G)\geq2\); the low-degree cases were handled above.

Completing the Induction

We can now prove Brooks' theorem. Induct on \(|V(G)|\) for connected graphs. The connected graphs with \(\Delta(G)\leq2\) were handled directly. For a connected graph with \(\Delta(G)\geq3\), if it has a cut vertex, the cut-vertex reduction colors it using at most \(\Delta(G)\) colors. Otherwise it has no cut vertex, so it is 2-connected. If it is not complete, the shortest-path argument supplies \(x,v,y\), and the greedy ordering colors it with at most \(\Delta(G)\) colors. A complete graph is precisely one of the theorem's exceptions. Odd cycles have maximum degree \(2\), so they were already separated in the low-degree case. These cases prove the stated theorem.

Common Pitfall: Greedy Coloring Needs the Right Order

A greedy coloring does not automatically use \(\Delta(G)\) colors just because the graph is connected and not complete. The \(C_5\) calculation shows exactly how an order can leave the last vertex with all available colors blocked. Brooks' proof avoids that failure by first coloring two nonadjacent neighbors \(x,y\) alike and making their common neighbor \(v\) the final vertex. At \(v\), those two neighbors count as only one forbidden color. The cut-vertex reduction is also essential: the special ordering argument is applied only after the graph has been reduced to pieces with no cut vertex, or to the 2-connected case.