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 MathOverflow as Human checkable proof of the Four Color Theorem?

$\endgroup$
  • 4
    $\begingroup$ It's on MO, too. $\endgroup$ – J. M. is a poor mathematician Nov 3 '10 at 13:27
  • 3
    $\begingroup$ The question presupposes that Cahit's claimed proof is actually correct. $\endgroup$ – Robin Chapman Nov 3 '10 at 13:52
  • 15
    $\begingroup$ 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) $\endgroup$ – anon Nov 3 '10 at 17:03
  • 18
    $\begingroup$ 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. $\endgroup$ – Gadi A Nov 4 '10 at 16:40
  • 5
    $\begingroup$ 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. $\endgroup$ – Noah Snyder Nov 4 '10 at 23:07
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Link to George Spencer-Brown paper: omath.org.il/image/users/112431/ftp/my_files/… $\endgroup$ – Cahit Jul 6 '11 at 6:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Cahit Jul 7 '11 at 9:41
  • 1
    $\begingroup$ Where is this paper [3] published? If not yet published, why ? $\endgroup$ – Cyriac Antony Jun 21 at 6:47

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.