Snark (graph theory)

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.^[1]

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.