Metraipolis › archive › dc_01ca2131a918

De Bruijn–Erdős theorem (graph theory) — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory)
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T23:19:35.863Z
SHA-256 of the archived text
008d8735635ed64655c8ce796d4dce075a0345fa69477ce35197d36d8d4f363f
Stable URL of this page
https://metraipolis.com/documento/dc_01ca2131a918

How to cite

De Bruijn–Erdős theorem (graph theory) — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_01ca2131a918 (Metraipolis archive dc_01ca2131a918, sha256 008d8735635ed64655c8ce796d4dce075a0345fa69477ce35197d36d8d4f363f)
BibTeX
@misc{dc01ca2131a918,
  title = {De Bruijn–Erdős theorem (graph theory) — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_01ca2131a918; sha256 008d8735635ed64655c8ce796d4dce075a0345fa69477ce35197d36d8d4f363f},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory). Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with c {\displaystyle c} colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named. The De Bruijn–Erdős theorem has several different proofs, all depending in some way on the axiom of choice. Its applications include extending the four-color theorem and Dilworth's theorem from finite graphs and partially ordered sets to infinite ones, and reducing the Hadwiger–Nelson problem on the chromatic number of the plane to a problem about finite graphs. It may be generalized from finite numbers of colors to sets of colors whose cardinality is a strongly compact cardinal.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «De Bruijn–Erdős theorem (graph theory)» — https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory)
Wikidata Q3527054 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q3527054
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory)?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1375818976, consultata il 2026-10-07T22:56:38.176Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: b43ef179b0114574cee065f5d5b0770a52ee49fd6af4bbb9948f309f276940d5