Snark (graph Theory) - Snark Theorem

Snark Theorem

W. T. Tutte conjectured that every snark has the Petersen graph as a 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 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, Robertson, Sanders, Seymour, and Thomas announced a proof of this conjecture. As of 2012, their proof remains largely unpublished. See the Hadwiger conjecture for other problems and results relating graph coloring to graph minors.

Tutte also conjectured a generalization of the snark theorem to arbitrary graphs: every bridgeless graph with no Petersen minor has a 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 follows from the snark theorem in this case. However, this conjecture remains open for graphs that need not be cubic.