Every finite connected simple graph that is neither complete nor an odd cycle can be vertex-colored using at most its maximum degree many colors.
Lean proofpassed
Unfinished proof stepsNone
Formal resultAccepted
Starting pointConnected graph, not complete or an odd cycle
→
RelationStructural decomposition and greedy extension
→
ConclusionColorable with Δ colors
Exact scope: Every finite connected simple graph that is neither complete nor an odd cycle is vertex-colorable with its maximum degree many colors.
Line counts exclude blank lines; comments and documentation count. The total is the commit-pinned first-party Lean import closure; Mathlib and other third-party dependencies are excluded.
The theorem at a glance
Brooks's Theorem at a glance
EnlargeOutside complete graphs and odd cycles, local degree controls the global palette.
Accessible transcript
χ(G) ≤ Δ(G)
The maximum-degree coloring bound, its two exception families, and the proof's forest, greedy, and regular-graph branches are gathered in one reference.
Read the complete poster transcript
GRAPH THEORY · VERTEX COLORING
BROOKS'S THEOREM
LOCAL DEGREE CONTROLS THE GLOBAL PALETTE
FINITE · CONNECTED · SIMPLE
χ(G) ≤ Δ(G)
Adjacent vertices receive different colors.
EXCEPTIONS
Complete graphs · Odd cycles
THE CHECKED ENDPOINT
G is colorable with Δ(G) colors.
HOW THE PROOF MOVES
COLOR FORESTS · RESOLVE MAXIMUM DEGREE TWO · GREEDY-COLOR THE NONREGULAR CASE · FIND A NONSEPARATING TWO-EDGE PATH · COLOR TWO ENDS ALIKE, THEN THE MIDDLE
EXACT SCOPE
An upper bound for finite connected simple graphs that are neither complete nor odd cycles. It does not assert χ(G)=Δ(G).
Theorem schematic
Maximum degree supplies the palette
EnlargeA connected graph is properly colored within its maximum-degree bound.
χ(G) ≤ Δ(G)
For a finite connected simple graph outside the complete and odd-cycle exceptions, Brooks's theorem constructs a proper coloring with at most the maximum-degree palette.
Proof architecture
How Brooks's Theorem is proved
7 curated stages
Follow the retained proof from the low-degree branches through the nonseparating-path construction to the final regular-graph coloring.
These source-anchored stages explain the retained proof route. They are not an extracted Lean proof-term dependency graph.
EnlargeThe low-degree cases separate forests, even cycles, and the odd-cycle exception.
01
Start with forests and degree two
Forests are colored along rooted components, while connected maximum-degree-two graphs reduce to paths or cycles; the odd cycles are exactly the exceptional branch.
EnlargeComponent attachments constrain the possible two-vertex cut.
04
Resolve the two-vertex-cut structure
The proof analyzes how components attach to a candidate cut pair, narrowing the hard case to two nonadjacent components under the minimum-degree conditions.
EnlargeThe surviving route proves the required pair deletion remains connected.
05
A nearer path survives the farther deletion
A shortest-path choice reaches the nearer side without using the farther deleted point, then joins the component regions in the final pair-deleted graph.
EnlargeThe recurring graph is colored with the middle vertex hollow and its nonadjacent neighbors equal gold.
06
Color the two nonadjacent ends alike
color(u)=color(v)
With w omitted, connectivity supplies an ordering of the remaining graph; u and v receive the same color while every visible edge remains properly colored.
Every finite connected simple graph that is neither complete nor an odd cycle is vertex-colorable with its maximum degree many colors.
The theorem excludes complete graphs and odd cycles rather than classifying their chromatic numbers.
It does not cover disconnected or infinite graphs.
About these visual explanations
These AI-generated visuals explain the theorem and proof route; they are not proof evidence. Their publication review was completed separately from review of the formal result. The exact Lean proposition and checked source remain authoritative.
Continue the mathematics
Start from the complete checked source
The pinned theorem and its complete local import closure let internal and external agents inspect the proof, compare an alternate route, isolate reusable lemmas, or formulate a stronger exact statement. Lean checks every proposed extension against its exact formal statement.
The ZIP contains the checked first-party Lean import closure, exact statements and boundaries, license, notice, evidence, source-footprint manifest, and an agent continuation file. Mathlib and other third-party dependencies are not bundled.
The formal theorem's publication gates are accepted
Lean checks the proof. Independent AI review separately accepted evidence completeness, statement alignment, result boundary, and the retained theorem wording. Those gates apply to the formal result; generated media is reviewed and promoted separately. Neither review replaces Lean's proof check or broadens the theorem.
01
Formal evidence
Independent review accepted the recorded build, exact declarations, unfinished-step scan, and axiom evidence.
02
Statement alignment
The formal declaration was accepted against the named theorem and its exact variant.
03
Result boundary
The accepted boundary keeps nearby stronger or commonly confused claims out of scope.
04
Public wording
Independent review accepted the retained theorem explanation and source presentation. Generated media follows a separate review and promotion gate.
05
Canonical source
The first-party source link is pinned to the checked package commit and exact Lean file.
06
Accepted result
A validated accepted-result record binds the four reviews to the checked formalization.
