Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1 Codex Max· openaiHugging Face Frontier Reasoning Traces

State Brooks' theorem on graph coloring. Chromatic number is at most max degree unless…

  1. User

    State Brooks' theorem on graph coloring. Chromatic number is at most max degree unless it's a complete graph or odd cycle. Prove the greedy strategy for non-exceptional cases.

  2. Assistant

    Recalling Brooks' theorem and greedy proof strategy

    Brooks' theorem states that any connected graph G with maximum degree Δ≥3 has chromatic number at most Δ unless G is a complete graph or an odd cycle. The greedy coloring proof hinges on finding a vertex ordering where each vertex—except possibly the first two—has at most Δ−1 earlier neighbors, enabling a Δ-coloring via greedy assignment.Completing Brooks' greedy coloring proof

    The standard greedy proof constructs a vertex ordering from a DFS or spanning tree in G-v, placing two nonadjacent neighbors of v just before v last; coloring in reverse order guarantees each vertex (except possibly the last two) has at most Δ−1 earlier-colored neighbors, enabling a Δ-coloring in all non-exceptional cases by induction.Clarifying final steps with DFS finishing and ear decomposition

    Coloring in DFS finishing order with two nonadjacent neighbors just before v ensures v can reuse a color, completing the greedy Δ-coloring. Alternatively, the ear decomposition approach incrementally colors the graph starting from a cycle, extending colors along ears using at most Δ colors, providing a constructive greedy method for non-exceptional cases.Summarizing standard induction with vertex ordering

    The standard proof uses induction removing low-degree vertices or decomposing at cut vertices, then in the 2-connected Δ-regular case orders vertices so two nonadjacent neighbors appear last before a chosen vertex. Coloring greedily in that order assigns Δ colors, as those neighbors can share a color, leaving a free color for the last vertex. Brooks’ Theorem.
    Let (G) be a connected graph with maximum degree (\Delta(G)). Then (\chi(G)\le\Delta(G)), except in the following two cases:

    • (G) is a complete graph (K_{\Delta(G)+1}).
    • (G) is an odd cycle (C_{2k+1}) (in which case (\Delta(G)=2) and (\chi(G)=3)).

    In all non-exceptional cases, there is a simple “greedy” way to color (G) using at most (\Delta(G)) colors:

    Proof (via a greedy strategy). We prove the theorem by induction on (|V(G)|).

    • If (\Delta(G) = 2), then (G) is a path or a cycle. A path is 2-colorable, and a cycle is 2-colorable unless it is an odd cycle (the exceptional case where 3 colors are needed).
    • If (\Delta(G)\ge 3) and there is a vertex (v) with degree strictly less than (\Delta(G)), remove (v) and color (G - v) by induction with (\Delta(G)) colors. Then color (v) with a color not used by its neighbors (this is possible because (v) has fewer than (\Delta(G)) neighbors).
    • Thus we may assume (G) is (\Delta(G))-regular. If (G) is disconnected or has a cut-vertex, we color each component (or each block of the graph) separately by induction and permute the color names so that the cut-vertex colors match up. This yields a (\Delta(G))-coloring of all of (G).
    • Finally, suppose (G) is (\Delta(G))-regular and 2-connected, and not a complete graph. Then any vertex (v) has two neighbors (x) and (y) that are not adjacent. Because (G) is 2-connected, there is a path (x = w_1,w_2,\dots,w_k = y) in (G - v). Order the vertices of (G) by listing the internal vertices of that path first ((w_1,\dots,w_{k-1})), then all other vertices of (G-v) in any order, then (x,y), and finally (v). Color the vertices in this order (from first to last). Each vertex has at most (\Delta(G)) neighbors and, with this ordering, no vertex except (v) has all (\Delta(G)) of its neighbors already colored. Thus each can be colored with one of at most (\Delta(G)) colors. Also, since (x) and (y) are not adjacent, we can force them to use the same color. Then (v) sees at most (\Delta(G)-1) colors among its neighbors, so it too can be colored with a remaining color.

    This completes the greedy construction of a (\Delta(G))-coloring whenever (G) is not complete or an odd cycle, proving Brooks’ theorem. (\square)

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.