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

On Thu, 14 Jun 2007 22:32:44 -0000, Andre <andre.roberge@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.

Right, you can't have 5 countries bordering on each other, but you can
have _one_ country with 4 (or more) neighbors.

Suppose country A has 4 neighbors, and suppose those 4 neighbors are
_forced_ by external considerations to use 4 different colors. Then
country A is forced to use a 5th color.

What kind of external considerations could there be to force the 4
neighbors to use all different colors? Well, in light of the 4 color
theorem, there can be no such forcing, but the proof is not easy.

quasi
.

Relevant Pages
Loading