SKEDSOFT

Brooks’ Theorem: We are now prepared to present bounds for the chromatic number of a graph. We give here several upper bounds, beginning with the best known and most applicable.
The bound (G) ≤ 1 Δ
(G) holds with equality for complete graphs and odd cycles. By choosing the vertex ordering more carefully, we can show that these are essentially the only such graphs. This implies, for example, that the Petersen graph is 3-colorable, without finding an explicit coloring. To avoid unimportant complications, we phrase the statement only for connected graphs. It extends to all graphs because the chromatic number of a graph is maximum chromatic number of its components. Many proofs are known; we present a modification of the proof by (Melnikov and Vizing 1969). For an alternative proof see (Lov´asz 1975).

Theorem. (Brooks’ Theorem) If a connected graph G is neither an odd cycle nor a complete graph, then (G) ≤
Δ(G).
Proof. If Δ
(G) ≤ 2, then G is either a path or a cycle. For a path G (other than K1 and K2), and for an even cycle G, (G) = 2 = Δ
(G). According to our assumption G is not an odd cycle. So let Δ(G) ≥ 3.

The proof is by contradiction. Suppose the result is not true. Then there exists a minimal graph G of maximum degree
Δ(G) ≥ 3 such that G is not
-Δcolorable, but for any vertex v of G, G − v is
Δ(G − v)-colorable and therefore
Δ-colorable.

Claim 1. Let v be any vertex of G. Then in any proper
-coloring of G − v, all the
Δ- colors must be used for coloring the neighbors of v in G. Otherwise, if some color i is not represented in NG(v), then v could be colored using i, and this would give a Δ
-coloring of G, a contradiction to the choice of G. Thus, G is a regular graph satisfying claim 1.
For v ∈ V (G), let N(v) = v1, v2, ..., vn. In a proper Δ
-coloring of G − v = H, let vi receive color i, 1 ≤ i ≤ Δ
. For i 6= j, let Hij be the subgraph of H induced by the
vertices receiving the ith and jth colors.
Claim 2. vi and vj belong to the same component of Hij . Otherwise, the colors i and j can be interchanged in the component of Hij that contains the vertex vj . Such an interchange of colors once again yields a proper Δ
-coloring of H. In this new coloring, both vi and vj receive the same color, namely, i, a contradiction to claim 1. This proves claim 2.

Claim 3. If Cij is the component of Hij containing vi and vj , then Cij is a path in Hij . As before, NH(vi) contains exactly one vertex of color j. Further, Cij cannot contain a vertex, say y, of degree at least 3; for, if y is the first such vertex on a vi − vj path in Cij that has been colored, say, with i, then at least three neighbors of y in Cij have the color j. Hence, we can recolor y in H with a color different from both i and j, and in this new coloring of H, vi and vj would belong to distinct components of Hij . (See Figure 3.3.) Note that by our choice of y, any vi −vj path in Hij must contain y. But this contradicts claim 2.

Claim 4. Cij ∩ Cik = {vi} for j 6= k. Indeed, if w ∈ Cij ∩ Cik,w 6= vi, then w is adjacent to two vertices of color j on Cij and two vertices of color k on Cik. (See Figure 3.4.) Again, we can recolor w in H by giving a color different from the colors of neighbors of w in H. In this new coloring of H, vi and vj belong to distinct components of Hij , a contradiction to claim 1. This completes the proof of claim 4.

We are now in a position to complete the proof of the theorem. By hypothesis, G is not complete. Hence, G has a vertex v, and a pair of nonadjacent vertices v1 and v2 in NG(v). Then the v1 − v2 path C12 in H12 of H = G − v contains a vertex y(6= v2) adjacent to v1. Naturally, y would receive color 2. Since
Δ ≥ 3, there exists a vertex v3 ∈ NG(v). Now interchange colors 1 and 3 in the path C₁₃ of H13. This would result in a new coloring of H = G − v. Denote the vi − vj path in H under this new coloring by C′ij . (See Figure 3.5). Then y ∈ C′₂₃, since v1 receives color 3 in the new coloring (whereas y retains color 2). Also, y ∈ C₁₂ − v1 ⊂ C′₁₂. Thus, y ∈ C′₂₃ ∩ C′₁₂. This contradicts claim 4 (since y 6= v2) and the proof is complete.