What is a snark in graph theory?

In graph theory, a snark is an undirected graph where every vertex has exactly three edges, and its edges cannot be colored using only three colors. Research into these graphs dates back to Peter G. Tait's work in 1880, though the name itself was coined by Martin Gardner in 1976. Despite their simple definitions, their overall structure and properties remain largely mysterious and connected to difficult problems in the field.

What we know

• A snark is a connected, bridgeless cubic graph with a chromatic index equal to 4. [1, 2]
• Every snark is a non-planar graph, which is an equivalent form of the four color theorem. [2]
• The name snark was given to these graphs by Martin Gardner in 1976, originating from Peter G. Tait's 1880 work on the four color theorem. [2]
• A Descartes snark is a specific type of snark with 210 vertices and 315 edges, discovered by William Tutte under a pseudonym. [5]

Still open

• Despite over a century of investigation, the properties and structure of snarks remain largely unknown.
• W. T. Tutte's snark conjecture has had a proof long announced, but it remains unpublished.

Where to go next

• a case in pointWhat is a Descartes snark?
• the bigger pictureHow does the four color theorem relate to graph coloring?
• whoWho was Peter G. Tait and what was his contribution?
• what followedWhat is the cycle double cover conjecture?
• compared withHow do cubic graphs differ from other graph families?
• an unexpected connectionHow is a mathematical graph named after a fictional hunting creature?Martin Gardner named snarks after the mysterious creature in Lewis Carroll's nonsense poem The Hunting of the Snark because they were similarly elusive and hard to find.

Sources

• [1]snark (Wikidata Q6470127) · CC0 1.0
• [2]Snark (graph theory) · CC BY-SA 4.0
• [3]Snark · CC BY-SA 4.0
• [4]List of graphs · CC BY-SA 4.0
• [5]Descartes snark · CC BY-SA 4.0