I'm trying to find out whether Tutte's conjecture (that every snark has the Petersen graph as a minor) has been satisfactorily proved. Wikipedia claims that Robertson, Saunders, Seymour and Thomas announced a proof but that it has not been published. Indeed, I cannot find a published paper which confirms the proof of the theorem.

Does anyone know what the status of this conjecture and proof are? Thanks!

  • 2
    $\begingroup$ It may be worth noting that my motivation for asking this question is to ascertain whether there is a non-computer-aided proof of the Four Colour Theorem. So, if the above proof does exist, is it computer-aided or not? $\endgroup$ – J Collins Jun 13 '17 at 6:45
  • $\begingroup$ There is an other proof for four-colour theorem (aproximately 44 pages) which is done by Robertson, Saunders, Seymour and Thomas. But again they used computer for this proof. $\endgroup$ – Shah Rooz Jun 13 '17 at 9:12
  • $\begingroup$ A very readable account of the 4CT is Wilson's book "Four Colours Suffice". I believe the only major innovation since then is Steinberger's proof that uses only D-reducible configurations: ams.org/journals/tran/2010-362-12/S0002-9947-2010-05092-5/… $\endgroup$ – Oliver Nash Jun 13 '17 at 11:42

Theorem 10.21 (see page 268) of the book "Chromatic Graph Theory" (which is written by Gary Chartrand and Ping Zhang), confirm that this conjecture is proved and in $2001$, Robertson, Saunders, Seymour and Thomas announced they verified this conjecture.

This conjecture is known as $4$-flow conjecture, and Seymour showed that the $4$-flow conjecture is equivalent to the following more general conjecture:

Each bridgeless matroid without $F_7^*$, $M^*(K_5)$, or $M(P_{10})$ minor has a nowhere-zero flow over $GF(4)$, where $P_{10}$ denotes the Peterson graph.

For cubic graphs, this conjecture is verified in the paper "Tutte’s Edge-Colouring Conjecture", which is written by the above authors. Also, note that most conjectures about flows can be easily reduced to the case of cubic graphs by splitting arguments.

Anyway, I could not find any paper which states the proof of this conjecture. Maybe, you can ask to someone which know the authors or email directly to one of these people. It seems that the conjecture is verified since it is stated in famous book as theorem.

The following link maybe useful: $4$-flow conjecture

$\textbf{Added later}:$ At the page 183 of the book "Topics in Chromatic Graph Theory" by Lowell W. Beineke and Robin J. Wilson (published in 2015), it is stated that (Conjecture B) this conjecture is still open.

$\textbf{Added later}(6/21/2017):$ The valuable book "Graph Theory: 5th edition" by Reinhard Diestel, published in 2017 and I prepared a copy of this book. In part 6.6 of this book (Tutte’s flow conjectures), there is a detailed information about $4$-flow conjecture. In this part, it is stated that this conjecture is still open. Some part of this book:

$\ldots$ Even if true, the $4$-flow conjecture will not be best possible: a $k^{11}$, for example, contains the Petersen graph as a minor but has a $4$-flow, even a $2$-flow. The conjecture appears more natural for sparser graphs; a proof for cubic graphs was announced in 1998 by Robertson, Sanders, Seymour and Thomas $\ldots$.

  • 1
    $\begingroup$ So the conjecture is proved and also is not proved? $\endgroup$ – Gordon Royle Jun 18 '17 at 4:30
  • $\begingroup$ It seems that we have a paradoxical evidences. Maybe you can ask the original authors for clarifying. $\endgroup$ – Shah Rooz Jun 18 '17 at 12:19

I think this is considered proved at this point. A list of relevant papers can be found at http://people.math.gatech.edu/~thomas/FC/generalize.html.

In this paper, the conjecture is reduced to proving it for two classes of graphs- apex and doublecross. The doublecross case has been published. I'm not sure if the apex paper has been published yet.

Note that the proof does indeed make use of a computer program that is no less complex than the one Robertson et al. used for their proof of the four-colour theorem. To my knowledge there is no accepted proof of 4CT that isn't computer assisted.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.