Message #2480

From: Eduard Baumann <>
Subject: Re: [MC4D] Re: flaw in 4 color theorem "proof"
Date: Mon, 12 Nov 2012 09:28:56 +0100

A perfect recapitulation!

—– Original Message —–
From: Melinda Green
Sent: Monday, November 12, 2012 3:36 AM
Subject: Re: [MC4D] Re: flaw in 4 color theorem "proof"

Both Andrey and Norbert are correct and have now doubled the number of solvers. Norber’s was sent to me privately and included a nice counterexample. He was surprised with the dearth of solvers, but I think that our group is much better equipped for this sort of puzzle than the general puzzling community. Maybe one of you who also participate in the speedsolving forums would like to post the puzzle there and we will see if my guess is right? I have gotten lots of wrong answers over the years and even fooled myself a few times in the first few years. Very few people know much about topology, but we have seen a fair bit of it here, especially in the last couple of years. If any of our younger members have been interested in those message threads, I encourage you to take a class in topology if you get the chance.

To Andrey’s point, I think I can safely say that the flaw cannot be easily fixed. Pretty much all the great mathematicians over the last 350 years have tried and failed. That is not to say that it can’t be done; it just can’t be done easily. The first real proof of the 4-color conjecture relied very heavily on computer assistance and the result was so long that it could never be checked by humans. Even if someone succeeded in following the entire proof, the likelihood that they made a mistake somewhere is so high that their result couldn’t be trusted. The best they could do is examine the source code for holes or bugs. To make matters worse, the form of the proof is called a statistical proof. I had never heard the term before but it is like "deductive" and "inductive", or like our false proof "by contradiction". My understanding is that a proper statistical proof asserts that the odds that there is a counterexample is vanishingly small. Such proofs are so unpleasant that nobody really wants to use or accept them. They are the weakest form of proof but they are definitely considered to be valid.

That proof by Appel and Haken was a landmark in mathematics which split the mathematics community regarding the use of computers compared to the traditional pencil and paper methods. These days everyone agrees that computers play an essential role in pure mathematics, but many people including myself feel a bit sad that such a beautiful problem didn’t have an equally beautiful solution. There is still a great deal of fame awaiting the first person who can find an elegant solution that can be verified the old-fashioned way. The problem is that the goal of being the first to solve it has already been reached, reducing the fame you might get if you succeed. Personally, I believe that there will be plenty of fame for doing that because the purists will be so happy to see this beautiful problem wrapped up properly.

For a little background showing even more irony, it is helpful to know that the problem is the same in the plane as it is on the sphere which are equivalent. These surfaces have genus 0. The one holed torus has genus 1, two holed 2, etc. for all of the orientable surfaces. Then there are the non-orientable surfaces like the Klein bottle with genus 1 which are sort of like the negative integers assigned to the one holed Klein bottle, the two holed bottle, etc. In modern history, little by little people found solutions to the coloring problem for all of of this infinite set of surfaces except for genus zero! A lot of really important results came from that effort, but the one last surface simply wouldn’t yield to those methods, and of course this was the one surface that everyone cared about the most. I think that Appel and Haken deserve far more credit than they got, but I still hope and even expect that someday some hero will finish the job in a way that will satisfy everyone. I will even offer a $5,000 prize right here and now to anyone in our group who succeeds in fixing this false proof before anyone else finds a proof that doesn’t require computers. If any of you do take the prize, the money will probably be the least interesting that happens to you as a result. Good luck!


On 11/11/2012 11:35 AM, Norbert Hantos wrote:

Dear Melinda, 

I surprised that such a few solutions you get for the false proof of the 4-color theorem. Therefore I tried to find the flaw. I think I successed. :)

I draw a counter-example graph, where you can not execute the recoloring described in 14) and 15).

On 11/11/2012 3:07 AM, Andrey wrote:

Hi Melinda,
I haven’t read bottom of your message, but in the proof I don’t like items 14-15: what if blue-green chain will intersect with red-green? In that case you can’t isolate both yellow areas, but I’m not sure if this case can be fixed easily.