Metraipolis › archive › dc_9659f8ebedfa
Snark (graph theory) — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Snark_(graph_theory)
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-06T12:51:48.556Z
- SHA-256 of the archived text
33f149e8cb4403c008ed1d33090da59aaddcaf4ec9616eef1afd3ceee0b6ab38- Stable URL of this page
https://metraipolis.com/documento/dc_9659f8ebedfa
How to cite
Snark (graph theory) — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Snark_(graph_theory) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_9659f8ebedfa (Metraipolis archive dc_9659f8ebedfa, sha256 33f149e8cb4403c008ed1d33090da59aaddcaf4ec9616eef1afd3ceee0b6ab38)
BibTeX
@misc{dc9659f8ebedfa,
title = {Snark (graph theory) — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Snark_(graph_theory)},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_9659f8ebedfa; sha256 33f149e8cb4403c008ed1d33090da59aaddcaf4ec9616eef1afd3ceee0b6ab38},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Snark_(graph_theory). Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist. One of the equivalent forms of the four color theorem is that every snark is a non-planar graph. Research on snarks originated in Peter G. Tait's work on the four color theorem in 1880, but their name is much newer, given to them by Martin Gardner in 1976. Beyond coloring, snarks also have connections to other hard problems in graph theory: writing in the Electronic Journal of Combinatorics, Miroslav Chladný and Martin Škoviera state that In the study of various important and difficult problems in graph theory (such as the cycle double cover conjecture and the 5-flow conjecture), one encounters an interesting but somewhat mysterious variety of graphs called snarks. In spite of their simple definition...and over a century long investigation, their properties and structure are largely unknown. As well as the problems they mention, W. T. Tutte's snark conjecture concerns the existence of Petersen graphs as graph minors of snarks; its proof has been long announced but remains unpublished, and would settle a special case of the existence of nowhere zero 4-flows. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»). Fonte: Wikipedia in inglese, voce «Snark (graph theory)» — https://en.wikipedia.org/wiki/Snark_(graph_theory) Wikidata Q6470127: «grafo cubico connesso, privo di ponti, con indice cromatico uguale a 4» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q6470127 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Snark_(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 1371204773, consultata il 2026-10-06T11:07:58.657Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 1c60f2a2337fe274f5fc2cb6c0493b2cd1c9a47df4ce90fd8565a972258f26d4