Editing Snark (graph theory) (section)

==Properties==
Work by Peter G. Tait established that the [[four-color theorem]] is true if and only if every snark is non-planar.{{r|tait}} This theorem states that every planar graph has a [[graph coloring]] of its the vertices with four colors, but Tait showed how to convert 4-vertex-colorings of [[maximal planar graph]]s into 3-edge-colorings of their [[dual graph]]s, which are cubic and planar, and vice versa. A planar snark would therefore necessarily be dual to a counterexample to the four-color theorem. Thus, the [[four color theorem#Proof by computer|subsequent proof of the four-color theorem]]{{r|4color}} also demonstrates that all snarks are non-planar.{{r|belcastro}}

All snarks are non-[[Hamiltonian graph|Hamiltonian]]: when a cubic graph has a Hamiltonian cycle, it is always possible to 3-color its edges, by using two colors in alternation for the cycle, and the third color for the remaining edges. However, many known snarks are close to being Hamiltonian, in the sense that they are [[hypohamiltonian graph]]s: the removal of any single vertex leaves a Hamiltonian subgraph. A hypohamiltonian snark must be ''bicritical'': the removal of any two vertices leaves a three-edge-colorable subgraph.{{r|steffen}} The ''oddness'' of a cubic graph is defined as the minimum number of odd cycles, in any system of cycles that covers each vertex once (a [[Graph factorization|2-factor]]). For the same reason that they have no Hamiltonian cycles, snarks have positive oddness: a completely even 2-factor would lead to a 3-edge-coloring, and vice versa. It is possible to construct infinite families of snarks whose oddness grows linearly with their numbers of vertices.{{r|oddness}}

The [[cycle double cover conjecture]] posits that in every bridgeless graph one can find a collection of cycles covering each edge twice, or equivalently that the graph can be [[graph embedding|embedded]] onto a surface in such a way that all faces of the embedding are simple cycles. When a cubic graph has a 3-edge-coloring, it has a cycle double cover consisting of the cycles formed by each pair of colors. Therefore, among cubic graphs, the snarks are the only possible counterexamples. More generally, snarks form the difficult case for this conjecture: if it is true for snarks, it is true for all graphs.{{r|jaeger}} In this connection, [[Branko Grünbaum]] conjectured that no snark could be embedded onto a surface in such a way that all faces are simple cycles and such that every two faces either are disjoint or share only a single edge; if any snark had such an embedding, its faces would form a cycle double cover. However, a counterexample to Grünbaum's conjecture was found by Martin Kochol.{{r|kochol2009}}

Determining whether a given cyclically 5-connected cubic graph is 3-edge-colorable is [[NP-complete]]. Therefore, determining whether a graph is a snark is [[co-NP-complete]].{{r|kochol2010}}