Message #2476

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] flaw in 4 color theorem "proof"
Date: Sat, 10 Nov 2012 14:57:58 -0800

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 &quot;proof&quot; of the //four color theorem<br>
&lt;http&#58;//en.wikipedia.org/wiki/Four&#95;color&#95;theorem&gt;//, shown incorrect<br>
by //Percy Heawood &lt;http&#58;//en.wikipedia.org/wiki/Percy&#95;Heawood&gt;//in<br>
1890. Much later, his work led to fundamental concepts such as the<br>
//Kempe chain &lt;http&#58;//en.wikipedia.org/wiki/Kempe&#95;chain&gt;//and<br>
unavoidable sets.//<br>
/

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