Editing Snark (graph theory) (section)

{{good article}}
{{Short description|3-regular graph with no 3-edge-coloring}}
{{About|a term in graph theory||Snark (disambiguation)}}

[[Image:Petersen1_tiny.svg|thumb|right|The [[Petersen graph]] is the smallest snark.]]
[[Image:Flower snarkv.svg|thumb|right|The [[flower snark]] J<sub>5</sub> is one of six snarks on 20 vertices.]]

In the [[mathematics|mathematical]] field of [[graph theory]], a '''snark''' is an [[undirected graph]] with [[cubic graph|exactly three edges per vertex]] whose [[edge coloring|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 (graph theory)|connectivity]] and on [[Girth (graph theory)|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 [[planar graph|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
{{cquote|In the study of various important and difficult problems in graph theory (such as the [[cycle double cover]] conjecture and the [[Nowhere-zero flow#Theory|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.{{r|chladny2010}}}}
As well as the problems they mention, [[W. T. Tutte]]'s ''snark conjecture'' concerns the existence of [[Petersen graph]]s as [[graph minor]]s of snarks; its proof has been long announced but remains unpublished, and would settle a special case of the existence of [[Nowhere-zero flows|nowhere zero 4-flows]].