Brooks' Theorem as a Tool for Regular Graphs
For a regular graph, every vertex has the same degree, so the maximum degree is immediately known. Brooks' theorem can then give a useful upper bound on the number of colors. The key is to check its exceptions first: complete graphs and odd cycles are not covered by the usual bound. A clique gives a complementary lower bound, and when the two bounds agree they certify the chromatic number exactly.
All graphs in this tutorial are finite and simple. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors; the chromatic number \(\chi(G)\) is the smallest number of colors in a proper coloring. A graph is \(d\)-regular if every vertex has degree \(d\). It is connected if every pair of vertices is joined by a path.
The theorem's conclusion is an upper bound, not automatically an exact value. To get a lower bound, recall that a clique is a set of pairwise adjacent vertices, and \(\omega(G)\) is the size of a largest clique.
Proof. Let \(C\) be a clique of size \(\omega(G)\). Every two distinct vertices in \(C\) are adjacent, so a proper coloring must assign a different color to each vertex of \(C\). Thus any proper coloring uses at least \(\omega(G)\) colors, which gives \(\omega(G)\leq\chi(G)\). \(\square\)
The Regular-Graph Cases
In a \(d\)-regular graph, \(\Delta(G)=d\), so Brooks' theorem gives \(\chi(G)\leq d\) when the graph is connected and neither exceptional type. The following case breakdown makes the hypotheses explicit.
- If \(d=0\), then \(G=K_1\) and \(\chi(G)=1\).
- If \(d=1\), then \(G=K_2\) and \(\chi(G)=2\).
- If \(d=2\), then \(G\) is a cycle. An even cycle has chromatic number \(2\), while an odd cycle has chromatic number \(3\).
- If \(d\geq3\), then either \(G=K_{d+1}\) and \(\chi(G)=d+1\), or \(G\) is not complete and \(\chi(G)\leq d\).
Proof. If \(d=0\), no vertex has a neighbor. Connectedness then forces there to be just one vertex, since two distinct vertices with no edges between them cannot be connected. This is \(K_1\), which requires one color. If \(d=1\), each vertex has exactly one neighbor; a connected graph with this property consists of one edge and its two endpoints, so it is \(K_2\), which requires two colors.
Suppose \(d=2\). Starting at any vertex and following edges without immediately reversing direction eventually revisits a vertex, since the graph is finite. This produces a cycle. Every vertex on that cycle already has its two incident edges within the cycle. Therefore no edge leaves the cycle, and connectedness implies that the cycle contains every vertex of \(G\). Hence \(G\) is a cycle. An even cycle can be colored by alternating two colors around it. An odd cycle cannot be colored with two colors: alternating around all but the final edge forces the endpoints of that edge to have the same color. Three colors suffice for an odd cycle, by alternating two colors along all but one edge and giving the last vertex a third color.
Finally, suppose \(d\geq3\). A complete graph in which every vertex has degree \(d\) has \(d+1\) vertices, so it is \(K_{d+1}\). Every pair of its vertices is adjacent, requiring \(d+1\) distinct colors. If \(G\) is not complete, it is also not an odd cycle, because every cycle has degree \(2\). Brooks' theorem therefore applies and gives \(\chi(G)\leq\Delta(G)=d\). \(\square\)
The corollary identifies the exception tests; it does not say that every nonexceptional regular graph has chromatic number exactly \(d\). A clique of size \(d\) would establish the matching lower bound, but a smaller clique may leave a gap between the lower and upper bounds.
Worked Example: A 3-Regular Graph with an Exact Bound
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,23,31,45,56,64,14,25,36\}\). The first three edges form a triangle, the next three form another triangle, and the final three join corresponding vertices.
Each vertex has two neighbors in its triangle and one neighbor across the two triangles. Thus every vertex has degree \(2+1=3\), so \(G\) is 3-regular and \(\Delta(G)=3\). It is connected: each triangle is connected, and the edges \(14,25,36\) join the triangles. It is not complete, since, for example, \(1\) and \(5\) are distinct and \(15\notin E\). Brooks' theorem applies and gives \(\chi(G)\leq3\).
The vertices \(\{1,2,3\}\) form a clique, since \(12,23,31\in E\). Therefore \(\omega(G)\geq3\), and the clique lower bound gives \(\chi(G)\geq3\). Combining the bounds yields \(\chi(G)=3\).
For a direct check of the upper bound, color \(1,2,3\) with colors red, blue, green, respectively, and color \(4,5,6\) with blue, green, red, respectively. The triangle edges \(12,23,31\) join red to blue, blue to green, and green to red. The edges \(45,56,64\) join blue to green, green to red, and red to blue. The remaining edges \(14,25,36\) join red to blue, blue to green, and green to red. Thus every edge has differently colored endpoints.
Check: There are \(9\) listed edges, and the six degrees sum to \(6\cdot3=18=2\cdot9\), as required by the handshake lemma. The explicit coloring uses three colors, while the triangle requires at least three, independently confirming \(\chi(G)=3\).
Worked Example: An Even Cycle
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,23,34,45,56,61\}\). Each vertex has two incident edges, so \(G\) is 2-regular. It is connected and is the cycle \(C_6\). It is not complete, and it is not an odd cycle, so Brooks' theorem gives \(\chi(G)\leq2\).
The edges \(12,23,34,45,56,61\) each join an odd-numbered vertex to an even-numbered vertex. Coloring \(\{1,3,5\}\) with one color and \(\{2,4,6\}\) with another is therefore proper. Since the graph has an edge, one color cannot suffice: the endpoints of that edge must differ. Hence \(\chi(G)\geq2\), and together the bounds give \(\chi(G)=2\).
The largest clique has size \(2\). There is at least one such clique because \(12\in E\); there is no clique of size \(3\), since the neighbors \(2\) and \(6\) of vertex \(1\) are not adjacent, and the cycle has no triangle. Thus \(\omega(G)=2\), and the clique lower bound agrees with the coloring and the Brooks upper bound.
Check: There are \(6\) edges and \(6\) vertices of degree \(2\), so the degree sum is \(6\cdot2=12=2\cdot6\). Each listed edge crosses the two stated color classes, confirming the coloring directly.
Worked Example: The Complete-Graph Exception
Let \(G=K_4\), with \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). Each vertex is adjacent to the other three, so \(G\) is 3-regular and \(\Delta(G)=3\). It is connected, but it is complete. The hypothesis of Brooks' theorem fails, so the conclusion \(\chi(G)\leq\Delta(G)\) is not available.
All four vertices form a clique. Therefore \(\omega(G)=4\) and \(\chi(G)\geq4\). Assigning a different color to each vertex is a proper coloring with four colors, so \(\chi(G)\leq4\) as well. Consequently \(\chi(G)=4\), which is one more than the degree.
Check: The edge list has \(6\) edges, and the degree sum is \(4\cdot3=12=2\cdot6\). Each pair of vertices appears as an edge, verifying both completeness and the need for four distinct colors.
Worked Example: An Odd-Cycle Exception
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,45,51\}\). Every vertex has two incident edges, so \(G\) is 2-regular. It is connected and is the odd cycle \(C_5\). Brooks' theorem does not give \(\chi(G)\leq2\), because \(G\) is an odd cycle.
The clique \(\{1,2\}\) shows that \(\omega(G)\geq2\); there is no triangle, so \(\omega(G)=2\). A two-coloring is impossible: starting with vertex \(1\) in one color, the successive cycle edges force \(2\) into the other color, \(3\) into the first, \(4\) into the other, and \(5\) into the first. But \(5\) is adjacent to \(1\), so this assignment fails. A proper three-coloring is \(1\) red, \(2\) blue, \(3\) red, \(4\) blue, \(5\) green. The five listed edges join red to blue, blue to red, red to blue, blue to green, and green to red, respectively. Thus \(\chi(G)=3\).
Check: The graph has \(5\) edges and five vertices of degree \(2\), giving degree sum \(5\cdot2=10=2\cdot5\). Its clique lower bound is \(2\), while the explicit coloring and the failure of every two-coloring establish the exact value \(3\).
Using the Bounds Carefully
For a connected \(d\)-regular graph that is neither complete nor an odd cycle, the immediate Brooks estimate is \(\chi(G)\leq d\). A clique of size \(d\) then gives \(\chi(G)=d\). If the largest known clique has size less than \(d\), the two bounds alone may not determine \(\chi(G)\); another argument, such as an explicit coloring or a stronger lower bound, is needed.
For disconnected graphs, Brooks' theorem must be applied component by component: its hypothesis is connectedness. A proper coloring of the whole graph can reuse colors between components because there are no edges between them. Thus the chromatic number of a graph with at least one vertex is the largest chromatic number of its components. Isolated vertices require one color if they are present, but contribute no greater requirement than a component containing an edge.
A common error is to substitute \(\Delta(G)\) into the conclusion without checking the exceptions. For \(K_4\), the incorrect calculation “\(\Delta(G)=3\), so Brooks gives \(\chi(G)\leq3\)” omits the hypothesis that the graph is not complete. In fact, all four vertices are pairwise adjacent, so \(\chi(K_4)=4\). The correction is to test completeness and odd-cycle status before using the bound.
Check Your Understanding
For each question, state the relevant hypotheses before using a bound.
- A connected 4-regular graph is not complete. What upper bound does Brooks' theorem give for its chromatic number?
- For a connected 3-regular graph, explain what additional information would make the Brooks upper bound an exact value.
- Why can the degree bound from Brooks' theorem not be applied to \(C_5\) to conclude that it is 2-colorable?
- Give a proper two-coloring of \(C_6\) from the edge list in its worked example, and state a lower bound that proves the coloring is optimal.
- A connected 2-regular graph has an odd number of vertices. Which exceptional case is it, and what is its chromatic number?