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)

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.

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)

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: