# Chapter 71. Brooks' Theorem # Chapter 71. Brooks' Theorem The greedy coloring argument proves that every graph \(G\) satisfies $$ \chi(G)\le \Delta(G)+1, $$ where \(\Delta(G)\) is the maximum degree of \(G\). This bound is often not sharp. Many graphs can be colored with fewer colors. Brooks' Theorem identifies the exact obstruction to improving the bound. The theorem states that only two kinds of connected graphs truly require \(\Delta(G)+1\) colors: - complete graphs, - odd cycles. All other connected graphs can be colored with only \(\Delta(G)\) colors. Brooks' Theorem is one of the central structural results in graph coloring. It explains why the greedy bound is usually stronger than it first appears. ## 71.1 Statement of the Theorem Let \(G\) be a connected graph. Brooks' Theorem states: If \(G\) is neither a complete graph nor an odd cycle, then \chi(G)\le\Delta(G) where \(\chi(G)\) is the chromatic number and \(\Delta(G)\) is the maximum degree. This theorem is standard in graph coloring theory. ([mathworld.wolfram.com](https://mathworld.wolfram.com/BrooksTheorem.html?utm_source=chatgpt.com)) The exceptional cases are necessary. For the complete graph \(K_n\), $$ \chi(K_n)=n $$ and $$ \Delta(K_n)=n-1. $$ Thus $$ \chi(K_n)=\Delta(K_n)+1. $$ Similarly, for an odd cycle \(C_{2m+1}\), $$ \chi(C_{2m+1})=3 $$ while $$ \Delta(C_{2m+1})=2. $$ Hence again $$ \chi(C_{2m+1})=\Delta(C_{2m+1})+1. $$ Brooks' Theorem says that these are the only connected examples where the extra color is unavoidable. ## 71.2 Comparison with the Greedy Bound The greedy coloring algorithm proves: $$ \chi(G)\le \Delta(G)+1. $$ Brooks' Theorem improves this by one color for almost every connected graph. | Graph type | Chromatic number bound | |---|---| | General graph | \(\chi(G)\le \Delta+1\) | | Noncomplete, nonodd-cycle connected graph | \(\chi(G)\le \Delta\) | Thus Brooks' Theorem refines the basic greedy argument. The theorem is remarkable because it gives a purely structural characterization of the exceptional cases. ## 71.3 First Examples ### Complete Graphs For \(K_n\), $$ \chi(K_n)=n, \qquad \Delta(K_n)=n-1. $$ Thus the theorem excludes complete graphs because they genuinely require the extra color. ### Odd Cycles For \(C_{2m+1}\), $$ \chi(C_{2m+1})=3, \qquad \Delta(C_{2m+1})=2. $$ Again the theorem excludes these graphs because the bound \(\chi\le\Delta\) fails. ### Even Cycles For \(C_{2m}\), $$ \chi(C_{2m})=2, \qquad \Delta(C_{2m})=2. $$ Thus equality holds: $$ \chi(C_{2m})=\Delta(C_{2m}). $$ Even cycles satisfy Brooks' bound. ### Trees A tree with at least two vertices satisfies $$ \chi(T)=2. $$ If the tree is not a single edge, then typically $$ \Delta(T)\ge 2. $$ Hence $$ \chi(T)\le \Delta(T). $$ Trees are far from the exceptional cases. ## 71.4 Why Complete Graphs Are Exceptional Suppose \(G=K_n\). Every vertex is adjacent to every other vertex. Therefore no two vertices may share a color. Each vertex requires a distinct color, so: $$ \chi(K_n)=n. $$ Since every vertex has degree \(n-1\), $$ \Delta(K_n)=n-1. $$ Thus: $$ \chi(K_n)=\Delta(K_n)+1. $$ Complete graphs represent maximal local obstruction. Every neighborhood already uses all possible colors. ## 71.5 Why Odd Cycles Are Exceptional An odd cycle alternates between two colors until the cycle closes. For example, consider: $$ v_1v_2v_3v_4v_5v_1. $$ If $$ c(v_1)=1, $$ then alternation forces: $$ c(v_2)=2, \quad c(v_3)=1, \quad c(v_4)=2, \quad c(v_5)=1. $$ But \(v_5\) is adjacent to \(v_1\), producing a conflict. Thus two colors are impossible. Since every odd cycle has maximum degree 2, $$ \Delta(C_{2m+1})=2, $$ yet $$ \chi(C_{2m+1})=3. $$ Odd parity forces the extra color. ## 71.6 Idea of the Proof The proof of Brooks' Theorem is constructive. The main idea is to find a vertex ordering that allows greedy coloring with only \(\Delta(G)\) colors. The ordinary greedy algorithm may fail because some vertex might encounter all \(\Delta(G)\) colors already used among its neighbors. Brooks' proof carefully arranges the order so that this never happens. The difficult part is ensuring that when the last vertices are colored, at least one color remains available. The theorem is often proved using depth-first search trees or spanning trees together with carefully chosen terminal vertices. One standard proof uses a spanning tree ordering and a special choice of endpoints. ([mathworld.wolfram.com](https://mathworld.wolfram.com/BrooksTheorem.html?utm_source=chatgpt.com)) ## 71.7 The Case \(\Delta(G)=2\) Suppose \(G\) is connected and $$ \Delta(G)=2. $$ Then every vertex has degree at most 2. Connected graphs of maximum degree 2 are exactly: - paths, - cycles. Paths are bipartite, so $$ \chi(G)=2. $$ Even cycles are also bipartite: $$ \chi(G)=2. $$ Odd cycles satisfy: $$ \chi(G)=3. $$ Thus the theorem is immediate for \(\Delta(G)=2\). The only obstruction is the odd cycle. ## 71.8 The Case \(\Delta(G)\ge 3\) Now suppose: $$ \Delta(G)\ge 3. $$ If the graph is not complete, then there exists a vertex \(v\) whose neighbors are not all mutually adjacent. Thus there exist neighbors \(x\) and \(y\) of \(v\) such that $$ xy\notin E(G). $$ This nonadjacency creates flexibility in coloring. The proof constructs a vertex ordering beginning with \(x\) and \(y\), ending with \(v\), and arranged so that each intermediate vertex has at least one later neighbor. Greedy coloring is then applied backward through the order. When \(v\) is colored last, its neighbors \(x\) and \(y\) already share a color because they are nonadjacent. Therefore at most $$ \Delta(G)-1 $$ distinct colors appear among the neighbors of \(v\), leaving one available color for \(v\). This is the key mechanism in the proof. ## 71.9 Consequences Brooks' Theorem immediately gives several useful corollaries. ### Triangle-Free Cubic Graphs Suppose \(G\) is connected, triangle-free, and 3-regular. Then: $$ \Delta(G)=3. $$ Since the graph contains no triangle, it is not \(K_4\). If it is not an odd cycle, Brooks' Theorem gives: $$ \chi(G)\le 3. $$ Thus every connected triangle-free cubic graph is 3-colorable. ### Sparse Graphs Graphs with bounded degree are often colorable with few colors. Brooks' Theorem shows that local degree constraints nearly determine colorability unless complete subgraphs or odd parity create obstructions. ## 71.10 Sharpness Brooks' Theorem is best possible. The complete graphs and odd cycles exactly attain the larger bound: $$ \chi(G)=\Delta(G)+1. $$ All other connected graphs satisfy: $$ \chi(G)\le\Delta(G). $$ Thus the theorem completely characterizes equality in the greedy bound for connected graphs. Few graph coloring theorems achieve such a precise classification. ## 71.11 Relation to Degeneracy A graph is \(d\)-degenerate if every subgraph contains a vertex of degree at most \(d\). Every \(d\)-degenerate graph is greedily colorable with at most $$ d+1 $$ colors. Brooks' Theorem is stronger because it uses global structure, not only local minimum degree conditions. For example, a regular graph of degree \(\Delta\) may have degeneracy \(\Delta\), giving the trivial bound $$ \chi\le\Delta+1. $$ Brooks' Theorem improves this to $$ \chi\le\Delta $$ except in the exceptional cases. Thus Brooks' Theorem goes beyond ordinary greedy reasoning. ## 71.12 Relation to Perfect Graphs Perfect graphs satisfy: $$ \chi(H)=\omega(H) $$ for every induced subgraph \(H\). Brooks' Theorem instead relates chromatic number to maximum degree. These are different structural controls. | Quantity | Meaning | |---|---| | \(\omega(G)\) | Largest clique | | \(\Delta(G)\) | Largest degree | | \(\chi(G)\) | Coloring complexity | Brooks' Theorem shows that maximum degree almost determines chromatic number for connected graphs. Perfect graph theory studies when clique structure completely determines chromatic number. ## 71.13 Algorithmic Perspective Brooks' Theorem is constructive. It does not merely assert existence. The proof produces a coloring algorithm. Efficient algorithms based on Brooks' ordering ideas can compute a \(\Delta(G)\)-coloring for graphs satisfying the theorem. This is important because exact graph coloring is generally NP-hard. Brooks' Theorem identifies a broad graph class where strong coloring guarantees are achievable efficiently. ## 71.14 Examples ### Example 1: Petersen Graph The Petersen graph satisfies: $$ \Delta(G)=3. $$ It is connected, not complete, and not an odd cycle. Therefore Brooks' Theorem gives: $$ \chi(G)\le 3. $$ Indeed the Petersen graph is 3-colorable. ### Example 2: Complete Bipartite Graph Consider: $$ K_{m,n}. $$ Its chromatic number is: $$ \chi(K_{m,n})=2. $$ But its maximum degree is: $$ \Delta(K_{m,n})=\max(m,n). $$ Thus Brooks' bound may be far from sharp. ### Example 3: Wheel Graphs Let \(W_n\) be a wheel graph. If the rim cycle is even, then: $$ \chi(W_n)=3. $$ If the rim cycle is odd, then: $$ \chi(W_n)=4. $$ These examples show how parity and clique structure influence coloring behavior. ## 71.15 Summary Brooks' Theorem is one of the fundamental results of graph coloring. It states that connected graphs satisfy: \chi(G)\le\Delta(G) except for: - complete graphs, - odd cycles. The theorem sharpens the greedy coloring bound and explains exactly when the extra color is necessary. The main ideas are: | Concept | Meaning | |---|---| | Greedy bound | \(\chi\le\Delta+1\) | | Brooks' improvement | Usually \(\chi\le\Delta\) | | Exceptional graphs | Complete graphs and odd cycles | | Proof idea | Special vertex ordering | | Structural meaning | Local degree almost determines colorability | Brooks' Theorem is a bridge between algorithmic coloring methods and structural graph theory. It shows that the apparent complexity of coloring is often controlled by simple local constraints, except in a few highly constrained configurations. ## 71.16 Exercises 1. Verify Brooks' Theorem for paths. 2. Verify Brooks' Theorem for even cycles. 3. Explain why odd cycles are exceptional. 4. Explain why complete graphs are exceptional. 5. Compute \(\chi(K_5)\) and compare it with \(\Delta(K_5)\). 6. Compute \(\chi(C_7)\) and compare it with \(\Delta(C_7)\). 7. Show that every tree satisfies Brooks' bound. 8. Show that every bipartite graph satisfies Brooks' bound. 9. Give an example where equality $$ \chi(G)=\Delta(G) $$ holds. 10. Give an example where $$ \chi(G)<\Delta(G). $$ 11. Prove Brooks' Theorem for graphs with maximum degree 2. 12. Explain why the proof requires connectedness. 13. Determine whether the Petersen graph satisfies Brooks' bound. 14. Show that \(K_n\) requires \(\Delta+1\) colors. 15. Compare Brooks' Theorem with the greedy coloring bound.