Editing Snark (graph theory) (section)

==Snark conjecture==
[[W. T. Tutte]] conjectured that every snark has the Petersen graph as a [[minor (graph theory)|minor]]. That is, he conjectured that the smallest snark, the Petersen graph, may be formed from any other snark by contracting some edges and deleting others. Equivalently (because the Petersen graph has maximum degree three) every snark has a subgraph that can be formed from the Petersen graph by [[homeomorphism (graph theory)|subdividing some of its edges]]. This conjecture is a strengthened form of the [[four color theorem]], because any graph containing the Petersen graph as a minor must be nonplanar. In 1999, [[Neil Robertson (mathematician)|Neil Robertson]], [[Daniel P. Sanders]], [[Paul Seymour (mathematician)|Paul Seymour]], and [[Robin Thomas (mathematician)|Robin Thomas]] announced a proof of this conjecture.{{r|thomas}} Steps towards this result have been published in 2016 and 2019,{{r|doublecross|rst2019}} but the complete proof remains unpublished.{{r|belcastro}} See the [[Hadwiger conjecture (graph theory)|Hadwiger conjecture]] for other problems and results relating graph coloring to graph minors.

Tutte also conjectured a generalization to arbitrary graphs: every bridgeless graph with no Petersen minor has a [[Nowhere-zero flows|nowhere zero 4-flow]]. That is, the edges of the graph may be assigned a direction, and a number from the set {1, 2, 3}, such that the sum of the incoming numbers minus the sum of the outgoing numbers at each vertex is divisible by four. As Tutte showed, for cubic graphs such an assignment exists if and only if the edges can be colored by three colors, so the conjecture would follow from the snark conjecture in this case. However, proving the snark conjecture would not settle the question of the existence of 4-flows for non-cubic graphs.{{r|garden}}