Metraipolis › archive › dc_d475c3142807

Grötzsch graph — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T22:33:03.490Z
SHA-256 of the archived text
ac3593684784a1cb9ada65c806415766fe89d54e6d98b2c22b516ebf40b2540b
Stable URL of this page
https://metraipolis.com/documento/dc_d475c3142807

How to cite

Grötzsch graph — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_d475c3142807 (Metraipolis archive dc_d475c3142807, sha256 ac3593684784a1cb9ada65c806415766fe89d54e6d98b2c22b516ebf40b2540b)
BibTeX
@misc{dcd475c3142807,
  title = {Grötzsch graph — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_d475c3142807; sha256 ac3593684784a1cb9ada65c806415766fe89d54e6d98b2c22b516ebf40b2540b},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable. The Grötzsch graph is a member of an infinite sequence of triangle-free graphs, each the Mycielskian of the previous graph in the sequence, starting from the one-edge graph; this sequence of graphs was constructed by Mycielski (1955) to show that there exist triangle-free graphs with arbitrarily large chromatic number. Therefore, the Grötzsch graph is sometimes also called the Mycielski graph or the Mycielski–Grötzsch graph. Unlike later graphs in this sequence, the Grötzsch graph is the smallest triangle-free graph with its chromatic number.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Grötzsch graph» — https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph
Wikidata Q3115494 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q3115494
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph?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 1326415016, consultata il 2026-10-07T22:11:36.219Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: b76715107d0cef0b9ae4a06bb494fba5fa279ef1fdee4a2a9301d1bae3aa48fb