Brooks' Theorem

Graph Theory · Axiom Academy

A Tight Upper Bound on Graph Chromatic Number 1. Statement of Brooks' Theorem Brooks' Theorem (1941): For any connected graph G that is neither a complete graph nor an odd cycle: This improves upon the greedy coloring bound of χ(G) ≤ Δ(G) + 1 by identifying exactly when equality can occur. Complete graphs K n : χ(K n ) = n = Δ(K n ) + 1 Odd cycles C 2k+1 : χ(C 2k+1 ) = 3 = Δ(C 2k+1 ) + 1 = 2 + 1 These are the only connected graphs requiring Δ + 1 colors. 2. Improvement Over Greedy Bound The greedy coloring algorithm guarantees χ(G) ≤ Δ(G) + 1. Brooks' Theorem shows we can do better: Greedy Bound: χ(G) ≤ Δ(G) + 1 for all graphs Brooks' Bound: χ(G) ≤ Δ(G) except for K n and odd cycles Example: Consider the 4-regular Petersen graph. The greedy bound gives χ ≤ 5, but Brooks' Theorem guarantees χ ≤ 4. In fact, χ(Petersen) = 3, showing Brooks' bound is closer but not always tight. The proof uses a clever vertex ordering that ensures no vertex has all Δ available colors already used by its neighbors. For Δ-regular graphs: Find two non-adjacent vertices u, v with a common neighbor w Ordering: Place u and v first (coloring them with color 1), then w, then remaining vertices in reverse BFS order Guarantee: Each vertex (except possibly w) has at least one uncolored neighbor when its turn comes Result: At most Δ - 1 neighbors are already colored, leaving color available from 1, 2, ..., Δ

This is the written version of the interactive lesson above. See the full Graph Theory course.