Message #2477

From: Eduard Baumann <baumann@mcnet.ch>
Subject: Re: [MC4D] flaw in 4 color theorem "proof"
Date: Sun, 11 Nov 2012 11:39:03 +0100

Nice. Thanks very much. Ed.

—– Original Message —–
From: Melinda Green
To: 4D_Cubing@yahoogroups.com
Sent: Saturday, November 10, 2012 11:57 PM
Subject: Re: [MC4D] flaw in 4 color theorem "proof"

On 11/10/2012 2:13 PM, Eduard wrote:

Please tell me the flaw in 4 color theorem "proof" http://www.superliminal.com/4color/4color.htm

Hello Eduard,

I’m really happy that you worked on this puzzle. It may be the hardest and most beautiful math problem that I know of and only two people have found the flaw in our treatment in the 18 years or so since we published it. I’ll make readers scroll way down to read it for those who want to take a stab at it before reading the answer.
.
.
.

All of the logic in the text is correct up to the penultimate step. The flaw is that steps 14 and 15 are mutually exclusive. You can perform either one of them just fine but you can’t do the second one after doing the first because the first color swapping might affect the other, and that subtle fact kills the proof. The reason the loops can affect each other is because both loops contain green regions. That allows one chain pass through the other chain’s loop and have its other color changed, destroying the chain. It’s natural to want to say "Well that’s an extremely unlikely thing to happen in a random map", but that’s what happens in math. It needs to 100% correct or it doesn’t count.

In my opinion this is a crying shame because the basic idea and the logical flow are truly beautiful and elegant. It was discovered by Kempe which is why the loops are called "Kempe chains". It was widely accepted until the flaw shattered it. From Wikipedia:

In 1879 Kempe wrote his famous "proof" of the four color theorem, shown incorrect by Percy Heawood in 1890. Much later, his work led to fundamental concepts such as the Kempe chain and unavoidable sets.

Kempe (I think) was able to use it to prove that all maps can be colored with at most 5 colors, so at least something good came of it. You can now understand why adding a fifth color works. You simply use the extra color to replace all the green regions in one of the two loops. That way they can’t intersect and the proof holds. Pretty neat, don’t you think?

-Melinda