For a connected graph that is not a complete graph or an odd cycle, the chromatic number is at most equal to the maximum vertex degree. Proved by R. Leonard Brooks, it is a fundamental bound in graph coloring theory.
Facts
StatementIn a connected graph in which every vertex has degree at most delta, the vertices can be colored using only delta colors, except when the graph is a complete graph or an odd cycle, which require delta plus one colors. 2 Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Sources
1. Wikipedia: Brooks' theorem
WikipediaLead section, statement-form referenceQuote, Lead section, statement-form reference
According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors.
2. Brooks' Theorem (Wikipedia)
Wikimedia FoundationLead section
in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors.
Lead section, proof year
The theorem is named after R. Leonard Brooks, who published a proof of it in 1941.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.