The Cut-Vertex Reduction in Brooks' Theorem

Why Cut Vertices Help in Brooks’ Theorem

A graph with a cut vertex separates into pieces that meet only at that vertex. This separation is useful in a coloring proof: color each piece, then rename its colors so that all pieces assign the same color to the shared vertex. The key point is that color names can be permuted without changing whether a coloring is proper.

All graphs here are finite and simple. A proper \(k\)-coloring of a graph \(G=(V,E)\) is a function \(c:V\to\{1,\dots,k\}\) such that \(c(u)\ne c(v)\) for every edge \(uv\in E\). The chromatic number \(\chi(G)\) is the least \(k\) for which \(G\) has a proper \(k\)-coloring. A graph is connected if every pair of its vertices is joined by a path.

If \(v\) is a cut vertex, let \(C_1,\dots,C_s\) be the components of \(G-v\). There are at least two of them. For each \(i\), define \(G_i=G[V(C_i)\cup\{v\}]\), the subgraph induced by the vertices of \(C_i\) together with \(v\). Each \(G_i\) is connected: connectedness of \(G\) ensures that \(v\) has a neighbor in \(C_i\), and every vertex of \(C_i\) can reach that neighbor inside \(C_i\).

Aligning the Colors at the Cut Vertex

Proof. Choose a proper \(k\)-coloring \(c_i\) of each \(G_i\). Set \(a=c_1(v)\). For every \(i\ge2\), choose a permutation \(\pi_i\) of \(\{1,\dots,k\}\) with \(\pi_i(c_i(v))=a\). Such a permutation exists: if the two colors already agree, take the identity; otherwise, interchange \(c_i(v)\) and \(a\), leaving the other colors fixed. Replace \(c_i\) by \(\pi_i\circ c_i\). A permutation preserves inequality of colors, so this is still a proper coloring of \(G_i\), and now every coloring assigns color \(a\) to \(v\).

Define a coloring of \(G\) by using the adjusted coloring on each \(G_i\). The definitions agree on overlaps, because \(G_i\cap G_j=\{v\}\) for \(i\ne j\), and all give \(v\) color \(a\). Every edge of \(G\) lies in one of the \(G_i\): an edge not incident with \(v\) has both endpoints in the same component of \(G-v\), and an edge incident with \(v\) has its other endpoint in one such component. Thus every edge has differently colored endpoints. This gives a proper \(k\)-coloring of \(G\). \(\square\)

The shared palette is essential to the statement: all pieces must be colorable with the same upper bound \(k\). A coloring that uses fewer than \(k\) colors is still a coloring from this palette, so unused colors cause no difficulty. The theorem does not require the separate colorings to agree initially; the permutations arrange that.

How the Reduction Fits an Induction

Brooks’ theorem concerns connected graphs and, apart from complete graphs and odd cycles, gives a coloring with at most \(\Delta(G)\) colors. The cut-vertex step reduces the coloring of a graph to the coloring of smaller connected graphs. To see exactly when this step works in an induction on the number of vertices, write \(\Delta=\Delta(G)\) and suppose \(G\) is connected, has a cut vertex, and is neither complete nor an odd cycle.

Each \(G_i\) has fewer vertices than \(G\), since at least one other component of \(G-v\) is nonempty. Also, \(\Delta(G_i)\le\Delta\), because deleting vertices and edges cannot increase any degree. If \(G_i\) is neither complete nor an odd cycle, the inductive coloring bound gives it a proper coloring with at most \(\Delta(G_i)\le\Delta\) colors. The exceptional types need to be checked because their chromatic numbers can exceed their maximum degrees.

Proof. For each subgraph \(G_i\) that is neither complete nor an odd cycle, apply the inductive bound as described above. If \(G_i\) is complete, say \(G_i=K_r\), then \(v\) has \(r-1\) neighbors in \(G_i\) and at least one neighbor in another component of \(G-v\). Therefore \(\deg_G(v)\ge r\), so \(\Delta\ge r\). The complete graph \(K_r\) can be colored with \(r\le\Delta\) colors by giving its vertices distinct colors.

If \(G_i\) is an odd cycle, then \(v\) has two neighbors in that cycle and at least one neighbor in another component of \(G-v\). Hence \(\deg_G(v)\ge3\), so \(\Delta\ge3\). An odd cycle can be colored with three colors: color successive vertices alternately with colors 1 and 2 until the last vertex, then give the last vertex color 3. The last vertex is adjacent to the first, whose color is 1, and to the preceding vertex, whose color is 2; all other edges join different colors as well. Thus this piece also has a coloring from \(\{1,\dots,\Delta\}\).

Every \(G_i\) now has a coloring from the common palette \(\{1,\dots,\Delta\}\). The theorem aligns these colorings at \(v\) and combines them into a proper coloring of \(G\). This proves the cut-vertex step, conditional only on the inductive bound for the smaller nonexceptional graphs. It does not prove the remaining case of Brooks’ theorem, where a connected graph has no cut vertex. \(\square\)

Common Pitfall: Combining Without Relabeling

A proper coloring of each piece does not automatically define a coloring of the whole graph. In the two-triangle example, the first piece gave \(v\) color 1 and the second gave it color 2. Writing both assignments together would give the shared vertex two colors, so it would not define a function on \(V(G)\) at all. The correction is to permute the colors of one piece so that the two assignments at \(v\) match, then use the resulting colorings on their union.

A second point is that a cut vertex is a vertex whose deletion disconnects the graph; it is not an edge whose deletion disconnects the graph. The reduction here relies on the pieces having only the vertex \(v\) in common and on there being no edges between different components of \(G-v\). For a graph with no cut vertex, this particular decomposition is unavailable, so a different part of the Brooks proof is needed.