The De Bruijn-Erdos theorem, in graph theory, states that if every finite subgraph of an infinite graph can be properly colored with c colors, then the whole graph can also be colored with c colors. Proved by Nicolaas Govert de Bruijn and Paul Erdos, the theorem depends essentially on the axiom of choice in every known proof, and it is used to extend results such as the four color theorem and Dilworth's theorem from finite to infinite graphs, and to reduce the Hadwiger-Nelson problem to a question about finite graphs. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Classification
Statement FormCharacterization Theorem 1 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.
Sources
1. De Bruijn-Erdos theorem (graph theory) (Wikipedia)
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.