# 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 "proof" of the //four color theorem<br>
<http://en.wikipedia.org/wiki/Four_color_theorem>//, shown incorrect<br>
by //Percy Heawood <http://en.wikipedia.org/wiki/Percy_Heawood>//in<br>
1890. Much later, his work led to fundamental concepts such as the<br>
//Kempe chain <http://en.wikipedia.org/wiki/Kempe_chain>//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