24
$\begingroup$

Four Color Theorem is equivalent to the statement: "Every cubic planar bridgeless graphs is 3-edge colorable". There is computer assisted proof given by Appel and Haken. Dick Lipton in of his beautiful blogs posed the following open problem:

Are there non-computer based proofs of the Four Color Theorem?

Surprisingly, While I was reading this paper, Anshelevich and Karagiozova, Terminal backup, 3D matching, and covering cubic graphs , the authors state that Cahit proved that "every 2-connected cubic planar graph is edge-3-colorable" which is equivalent to the Four Color Theorem (I. Cahit, Spiral Chains: The Proofs of Tait's and Tutte's Three-Edge-Coloring Conjectures. arXiv preprint, math CO/0507127 v1, July 6, 2005).

Does Cahit's proof resolve the open problem in Lipton's blog by providing non-computer based proof for the Four Color Theorem? Why isn't Cahit's proof widely known and accepted?

Cross posted on cstheory.stackexchange.com as Human checkable proof of the Four Color Theorem?

  • 4
    [It's](http://mathoverflow.net/questions/44673) on MO, too.2010-11-03
  • 3
    The question presupposes that Cahit's claimed proof is actually correct.2010-11-03
  • 1
    In fact, a quick scan of the references in the paper cited by OP gives the following reference in which the 4CP is directly tackled by Cahit: http://arxiv.org/ftp/math/papers/0408/0408247.pdf2010-11-03
  • 15
    I don't understand why is there so much appeal for a human checkable proof of this result? Why aren't people demanding a human checkable proof that 615789648168*54681684648 = 33672415350625446924864? (If you can actually do that yourself then triple the number of digits.., it's just an example to illustrate my question anyway)2010-11-03
  • 1
    It's historic, Muad. Many people felt like this was the "first" proof of a major theorem that used computers to produce the proof in a prominent. Simply checking every case works, but presumably a human check-able proof would tell us deeper things about the problem. (Or perhaps not, but it is worth a shot.)2010-11-04
  • 17
    Muad, I think that what people want most of the time is *insightful* proof - proof that not only tells us "it's correct" but also helps us understand WHY it is correct. A human-verifiable proof is not, of course, always an insightful proof; but it's a start.2010-11-04
  • 3
    To @Gadi's point: "If your solution breaks into cases, then you don't understand the problem." ;) I was given this as a rule of thumb many years ago, but I don't have an attribution.2010-11-04
  • 5
    I don't think it's fair to think of all computer verified proofs as non-insightful. The Appel-Haken proof of the 4-color theorem is insightful: it says all you need to use is discharging. I don't see why thousands of cases is any less insightful than 4 cases.2010-11-04
  • 0
    I believe I have a partial proof somewhere that we discussed in class. I will try to find that and get that to you.2010-12-04
  • 0
    The the graphs in the paper by Isaacs mentioned below are all non-planar.2011-07-05

1 Answers 1

5

After reading the papers by Rufus Isaacs [1] and George Spencer-Brown [2], I have reached to the conclusion that spiral chain edge coloring algorithm [3] gives answer to the question in affirmative.

[1] Rufus Isaacs, "Infinite families of nontrivial trivalent graphs which are not tait colorable", American Math Monthly 73 (1975) 221-239.

[2] George Spencer-Brown, "Uncolorable trivalent graphs", Thirteenth European Meeting on Cybernetics and Systems Research, University of Vienna, April 10, 1996.

[3] I. Cahit, Spiral Chains: The Proofs of Tait's and Tutte's Three-Edge-Coloring Conjectures. arXiv preprint, math CO/0507127 v1, July 6, 2005.

  • 0
    Link to George Spencer-Brown paper: http://www.omath.org.il/image/users/112431/ftp/my_files/GSB%20-%20vienna_paper.pdf?id=79791372011-07-06
  • 1
    Actually Tutte-conjecture asserts that "Every 2-connected cubic graph with no Petersen minor is 3-edge colorable" and extends Tait-conjecture to all 2-connected cubic graphs. Robertson, Seymour and Thomas (RST) conjecture that (1) Every 2-connected apex cubic graph is 3-edge colorable and (2) every 2-connected doublecross cubic graph is 3-edge colorable strengthened Tutte-conjecture that the only possible counter-examples are either apex or doublecross cubic graph. In [3] by using spiral chain edge coloring algorithm we have shown that this is not the case.2011-07-07