26

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?

Ilmari Karonen
  • 26,117
Mohammad Al-Turkistany
  • 952
  • 4
    It's on MO, too. – J. M. ain't a mathematician Nov 03 '10 at 13:27
  • 3
    The question presupposes that Cahit's claimed proof is actually correct. – Robin Chapman Nov 03 '10 at 13:52
  • 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.pdf – Bob Durrant Nov 03 '10 at 14:07
  • 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) –  Nov 03 '10 at 17: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.) – futurebird Nov 04 '10 at 15:38
  • 22
    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. – Gadi A Nov 04 '10 at 16:40
  • 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. – Blue Nov 04 '10 at 17:21
  • 6
    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. – Noah Snyder Nov 04 '10 at 23:07
  • I believe I have a partial proof somewhere that we discussed in class. I will try to find that and get that to you. – Tyler Clark Dec 04 '10 at 21:07
  • The the graphs in the paper by Isaacs mentioned below are all non-planar. – Joseph Malkevitch Jul 05 '11 at 17:56
  • @GadiA, you have a fair point. We should be asking for an insightful proof for the Four Colour Theorem. I am not sure whether Apel and Haken's proof or its revised version is satisfactory on this front. It could be. I don't agree with Noah's comment here. If the 'insight' is only that a particular technique (discharging in this case) solves the problem, it is not an insight at all (as to why the result is tree). Whether the proof is computer assisted or not, a version of the proof(or a survey on 4CT) that explicitly points out the insights in the proof for Four Colour Theorem would be great. – Cyriac Antony May 20 '19 at 05:35

1 Answers1

6

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.

Cahit
  • 61
  • Link to George Spencer-Brown paper: http://www.omath.org.il/image/users/112431/ftp/my_files/GSB%20-%20vienna_paper.pdf?id=7979137 – Cahit Jul 06 '11 at 06:42
  • 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. – Cahit Jul 07 '11 at 09:41
  • 1
    Where is this paper [3] published? If not yet published, why ? – Cyriac Antony Jun 21 '19 at 06:47