Re: Four color theorem: why this is not a proof and pointer to simple explanations

Amateur a écrit :
On 14 jun, 17:32, Andre <andre.robe...@xxxxxxxxx> wrote:
A few weeks ago, I gave my 15 year old son a book on mathematical
puzzles that included a description of the 4 color theorem. After
spending some time drawing colored maps, he made a connection with
another problem, that of the impossibility of connecting 3 houses with
3 different utilities (gas, water, electricity) without having two
lines crossing.

In doing so, he came up with a "proof" for the 4 color theorem. I
know it is not a proof, and I believe I know where it fails, but I
can't explain it in a convincing way.

Here's the "proof"; I suspect that the problem is right with the first
step.

1. If there is a map where 5 colors are needed, it must be because 5
different countries are touching each other.

2. Countries touching each other can be represented as (labeled)
points linked by lines; two countries touching each other can be
linked by a line which is not crossing any other line.

3. A map representing 4 countries touching each others can be drawn as
follows

A -- B
| \ |
C --D

with the addition of a line joining B to C going on the "outside" of
the square ABDC.

4. A map representing 5 countries, some of them touching each other
can be drawn as follows:

A -- B
| \ |
C D
| |
E /

An additional line can be drawn "inside" the ABDEC polygon joining A
to E.
A line can be drawn on the "outside" joining B to C. A similar one
can be drawn joining B to E.

The result is that all countries are touching each other _except_ D
and C. However, no line can be drawn joining D and C without
crossing an existing line (A to E "inside", or B to E "outside").

Hence, we cannot have 5 countries touching each other - and we don't
need 5 different colors.

Any _simple_ explanation (or links) that I could pass along to my son
would be greatly appreciated.

A.R.

Your problem is known in graphic theory as "the four colours problem".
It`s an open problem. There is a "proof" but with computers; nobody is
satisfied with such "proof" because isn`t a math proof (isn`t a
deductive proof). I read this information in 1996. Maybe your
exposition isn`t a proof because this.

Nice "maybe", justifying fully the "Amateur" signature. No, step 1 is indeed wrong (but not really of the same order that Kempe's mistake), and it is not hard to see where is the mistake : there are maps needing 4 colors with no 4 countries touching each other...




.

Relevant Pages