Brooks' Theorem: Hypotheses and Exceptions

The Maximum-Degree Bound and Its Exceptions

A proper vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The maximum-degree bound says that every finite simple graph can be colored with at most one more color than its maximum degree. Brooks' theorem improves this bound for connected graphs: apart from two specific families, the maximum degree itself suffices. The exceptions matter because each really does require more colors than its maximum degree.

Throughout, graphs are finite and simple. A graph $G=(V,E)$ is connected if every two vertices are joined by a path; we take a connected graph to have at least one vertex. The maximum degree is $\Delta(G)=\max_{v\in V(G)}\deg(v)$. A proper coloring is an assignment of colors to the vertices such that the endpoints of each edge have different colors, and $\chi(G)$ is the smallest number of colors in any proper coloring. The complete graph $K_n$ has an edge between every pair of distinct vertices.

Theorem (Brooks' theorem): Let $G$ be a finite, simple, connected graph. If $G$ is neither a complete graph nor an odd cycle, then $$ \chi(G)\le \Delta(G). $$ The complete graphs and odd cycles are the exceptions: each has chromatic number greater than its maximum degree. The proof of the general bound is given in the later treatment of Brooks' theorem.

The exclusions are part of the theorem, not optional qualifications. For $K_n$, every pair of vertices is adjacent, so all $n$ vertices need different colors, although the maximum degree is only $n-1$. For an odd cycle, two colors cannot alternate consistently all the way around the cycle, even though every vertex has degree two. The next result verifies both claims, including the smallest complete graph.

Proposition: For every $n\ge 1$, $\chi(K_n)=n$ and $\Delta(K_n)=n-1$. For every odd cycle $C_{2k+1}$, where $k\ge1$, $\chi(C_{2k+1})=3$ and $\Delta(C_{2k+1})=2$.

Proof. In $K_n$, every two distinct vertices are adjacent, so a proper coloring must give all $n$ vertices different colors. This proves $\chi(K_n)\ge n$; assigning a different color to each vertex uses $n$ colors, so $\chi(K_n)=n$. Each vertex is adjacent to the other $n-1$ vertices, hence $\Delta(K_n)=n-1$. This includes $n=1$: the one vertex needs one color and has degree zero.

Now consider $C_{2k+1}$, with vertices in cyclic order $v_0,v_1,\ldots,v_{2k}$. Every vertex has degree two. If a proper coloring used only two colors, then along the cycle the colors would have to alternate: $v_0$ and $v_2$ would have the same color, as would $v_0$ and $v_{2k}$, because both indices are even. But $v_{2k}$ is adjacent to $v_0$, a contradiction. Thus at least three colors are required.

Three colors suffice: color $v_i$ with color 1 for even $i<2k$, color 2 for odd $i<2k$, and color 3 for $v_{2k}$. Consecutive vertices among $v_0,\ldots,v_{2k-1}$ have different colors; $v_{2k}$ has color 3, different from both its neighbors $v_{2k-1}$ and $v_0$. Therefore $\chi(C_{2k+1})=3$ and $\Delta(C_{2k+1})=2$. $\square$

Consequently, in both exceptional families the proposed bound fails by exactly one: $\chi(K_n)=\Delta(K_n)+1$, and $\chi(C_{2k+1})=\Delta(C_{2k+1})+1$. The odd cycle $C_3$ is also $K_3$, so the two exceptional families overlap there.

Why Connectedness and the Exceptions Matter

The theorem is stated for connected graphs. If a graph is disconnected, its chromatic number is the largest chromatic number among its connected components: color each component using its own colors, reusing colors on different components. But the maximum degree is also taken over all components, so applying the theorem as though the entire disconnected graph were one connected graph can fail. In particular, a complete component can require one more color than the maximum degree of the whole graph.

Before considering larger graphs, it is useful to see exactly what the theorem says at maximum degree at most two. The following elementary classification explains why paths and even cycles obey the bound, while odd cycles are excluded.

Lemma: Every finite, simple, connected graph with maximum degree at most two is a single vertex, a path, or a cycle.

Proof. Let $G$ be such a graph. If it has one vertex, it is a single vertex. Suppose it has at least two vertices. If some vertex has degree one, start there and extend a path by taking, at each step, a neighbor other than the vertex just visited whenever such a neighbor exists. There is at most one choice at each step because every degree is at most two. The extension cannot revisit an earlier vertex: the starting vertex has degree one, and any other earlier vertex already has its two path neighbors, so an additional edge back to it would give degree at least three. Since the graph is finite, the extension stops, giving a path. Its endpoints have no unused neighbor, and its internal vertices already have degree two. Thus no vertex outside the path can be adjacent to it; connectedness implies that there are no outside vertices.

It remains to consider the case where every vertex has degree two. Starting at any vertex and following edges without immediately retracing the previous edge must eventually revisit a vertex, since the graph is finite. The resulting closed route contains a cycle. Every vertex on that cycle already has its two cycle neighbors, so it has no edge to a vertex outside the cycle. Connectedness then implies that the cycle contains every vertex of $G$. Hence $G$ is a cycle. $\square$

For the single vertex and for $K_2$, the graph is complete. A path on at least three vertices has maximum degree two and can be colored with two alternating colors. An even cycle can also be colored with two alternating colors; an odd cycle needs three, as proved above. Thus the small-degree cases match the theorem's bound and its stated exceptions.

Worked Examples

Worked Example: A Complete Graph

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,13,14,23,24,34\}$. This is $K_4$. Find its maximum degree and chromatic number, and compare them.

Vertex 1 is incident to edges $12,13,14$, so $\deg(1)=3$. The same count gives $\deg(2)=3$, $\deg(3)=3$, and $\deg(4)=3$. Hence $\Delta(G)=3$. Since every pair of vertices is adjacent, a proper coloring must assign four different colors. Assigning one distinct color to each vertex works, so $\chi(G)=4$.

Check: The computed values give $\chi(G)=4=3+1=\Delta(G)+1$. This graph is excluded from Brooks' bound because it is complete.

Worked Example: An Odd Cycle

Let $G=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45,51\}$. This is $C_5$. Determine $\Delta(G)$, $\chi(G)$, and whether the Brooks bound applies.

Each vertex is incident to two listed edges: vertex 1 to $12,51$; vertex 2 to $12,23$; vertex 3 to $23,34$; vertex 4 to $34,45$; and vertex 5 to $45,51$. Thus all degrees are two and $\Delta(G)=2$. Two colors cannot suffice: if vertex 1 has color A, then 2 must have B, 3 must have A, 4 must have B, and 5 must have A; but 5 is adjacent to 1. Three colors suffice, for example $1,3,5$ receiving colors A, B, C respectively and vertices 2, 4 receiving B, A respectively. Checking the five edges gives different colors at both ends of each edge. Therefore $\chi(G)=3$.

Check: The result is $\chi(G)=3=2+1=\Delta(G)+1$. The graph is connected but is an odd cycle, so it is exactly an excluded case.

Worked Example: A Connected Graph That Meets the Bound

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$, the path $P_4$. Compute its maximum degree and chromatic number, then apply Brooks' theorem.

Vertices 1 and 4 each have degree 1, while vertices 2 and 3 each have degree 2. Hence $\Delta(G)=2$. Color vertices 1 and 3 with color A, and vertices 2 and 4 with color B. The edges $12,23,34$ each have one endpoint of each color, so this is a proper two-coloring. Since the graph has an edge, one color cannot suffice; thus $\chi(G)=2$.

The graph is connected, is not complete (for example, 1 and 3 are not adjacent), and is not a cycle. Brooks' theorem applies and gives $\chi(G)\le\Delta(G)$, which here reads $2\le2$. The explicit coloring also verifies the value exactly.

A Common Mistake: Dropping Connectedness

A tempting but incorrect statement is: “Every graph that is neither complete nor an odd cycle satisfies $\chi(G)\le\Delta(G)$.” The missing hypothesis is connectedness. For a concrete counterexample, let $G=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,13,14,23,24,34\}$. Vertices 1 through 4 form a $K_4$, and vertex 5 is isolated. The four vertices in the complete component have degree 3, while vertex 5 has degree 0, so $\Delta(G)=3$. The complete component requires four colors, and the isolated vertex can reuse one of them, so $\chi(G)=4$. Thus $\chi(G)=4>3=\Delta(G)$, even though the whole graph is neither connected nor a complete graph nor an odd cycle.

The correction is to check the hypotheses before using Brooks' theorem. For a disconnected graph, inspect its connected components separately. A component that is complete or an odd cycle is not covered by the bound in the theorem, and may determine the chromatic number of the whole graph.

How to Read the Theorem Precisely

Brooks' theorem gives a sufficient condition for the bound; it is not a claim that every graph outside the exceptions has chromatic number exactly $\Delta(G)$. The $P_4$ example has $\chi(G)=\Delta(G)=2$, but other graphs can have a strict inequality. Nor does the theorem say that complete graphs and odd cycles are the only graphs whose chromatic number is greater than the maximum degree without its connectedness hypothesis: the disconnected counterexample shows why that hypothesis must stay in view.

When applying the result, check these points in order:

The graph is finite and simple.
The graph is connected.
The graph is not complete and is not an odd cycle.
The quantity on the right is the maximum degree $\Delta(G)$, not one more than the maximum degree.

If all four conditions hold, Brooks' theorem guarantees a proper coloring using at most $\Delta(G)$ colors. The theorem does not, by itself, exhibit that coloring; establishing the general bound requires its proof. The examples here show how to verify the hypotheses and compare the bound with an explicitly established chromatic number.

Check Your Understanding

For each question, state the relevant hypotheses and justify the numerical or structural conclusion.

For $K_5$, compute $\Delta(K_5)$ and $\chi(K_5)$. Why does Brooks' bound not apply?
Explain why a proper two-coloring of an odd cycle would force its first and last vertices to have the same color.
Let $G$ be connected, noncomplete, and have maximum degree at most two. Which graph forms can $G$ have, and which of them can be an exception to Brooks' bound?
Give the maximum degree and chromatic number of the path $P_5$, and check the Brooks inequality.
Why is the graph consisting of a $K_4$ and an isolated vertex not a counterexample to Brooks' theorem?