Henry Ernest Dudeney/Modern Puzzles/140 - The Four-Colour Map Theorem/Mistake

Source Work

1926: Henry Ernest Dudeney: Modern Puzzles:

Geometrical Problems

Various Geometrical Puzzles

$140$ -- The Four-Colour Map Theorem

1968: Henry Ernest Dudeney: 536 Puzzles & Curious Problems:

Combinatorial & Topological Problems

Map Coloring Puzzles

$442$. The Four-Color Map Theorem

Mistake

In colouring any map under the condition that no contiguous countries shall be coloured alike,

not more than four colours can ever be necessary.

Countries only touching at a point ... are not contiguous.

I will give, in condensed form, a suggested proof of my own

which several good mathematicians to whom I have shown it accept it as quite valid.

Two others, for whose opinion I have great respect, think it fails for a reason that the former maintain will not "hold water".

The proof is in a form that anybody can understand.

It should be remembered that it is one thing to be convinced, as everybody is, that the thing is true,

but quite another to give a rigid proof of it.

Correction

Dudeney's analysis of this problem does not constitute a proof.

Martin Gardner explains it in his $1968$ repackaging 536 Puzzles & Curious Problems as follows:

Refutation

Dudeney correctly shows that no more than $4$ regions can be drawn so that each borders all the others.

However, his proof fails to show that four colors are sufficient for all maps.

It is indeed true that if any four regions of a map are considered in isolation, then no fifth color is necessary for any fifth region.

What is required, however, is a proof that on a map with a large number of regions, these various sets of five will never conflict with each other in a way that five colors are demanded.

The difficult is best seen by actually constructing a complicated map, using the step by step procedure proposed by Dudeney.

Suppose that each new region is drawn so as to border three others.

Then its color is determined automatically, and four-color maps can indeed be extended indefinitely.

However, suppose that many new regions are added that touch either one, two, or even no previously drawn regions.

Then the choice of colors for these regions suddenly becomes arbitrary.

As the map grows in size and complexity, it is suddenly discovered that it is possible to add a new region that will require a fifth color.

By backtracking and altering previous decisions as to what color to be used, it appears that it is always possible to correct the mistake and accommodate the new region without needing that fifth color.

But using this process it cannot be certain that it is always possible.

Sources

• 1926: Henry Ernest Dudeney: Modern Puzzles ... (previous) ... (next): Geometrical Problems: Various Geometrical Puzzles: $140$. -- The Four-Colour Map Theorem
• 1968: Henry Ernest Dudeney: 536 Puzzles & Curious Problems ... (previous) ... (next): Combinatorial & Topological Problems: Map Coloring Puzzles: $442$. The Four-Color Map Theorem