Henry Ernest Dudeney/Modern Puzzles/140 - The Four-Colour Map Theorem/Solution
Modern Puzzles by Henry Ernest Dudeney: $140$
- The Four-Colour Map Theorem
- 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.
Solution
The proof offered by Dudeney is offered below, complete with the obvious bits.
With $2$ or more contiguous regions, $2$ colours are obviously necessary, as seen in Figure $1$.
If $3$ regions are contiguous each with each, $3$ colours are necessary, as seen in Figure $2$.
With $4$ regions, $3$ colours will be required if the fourth is contiguous with each of two that are already contiguous, as in Figure $3$.
For, as in Figure $4$, $G$ may be contiguous with $2$ regions not contiguous with each other, when only $2$ colours are needed.
And $4$ colours will be necessary if the fourth region is contiguous with each of $3$ already contiguous each with each, as in Figure $5$.
With $5$ contiguous regions, three will be required if one region is contiguous with two already contiguous, as in Figure $6$.
And $4$ will be necessary if the $5$th region is contiguous with each of $3$ regions that are contiguous each with each, as in Figure $7$.
Yet $5$ colours would be needed if a fifth region were contiguous with each of $4$ that are contiguous each with each.
If such a map is possible, the theorem breaks down.
First, let us consider $4$ regions contiguous each with each.
We will use a simple transformation and suppose every $2$ contiguous regions to be connected by a bridge across the boundary line.
The bridge may be as long as we like, and the regions may be reduced to mere points, without affecting the conditions.
In Figures $8$ and $9$ I show four regions (points) connected by bridges (lines), each with each.
The relative positions of these points is quite immaterial, and it will be found in every possible case that one region (point) must be unapproachable from the outside.
The proof of this is easy.
If $3$ points are connected each with each by straight lines these points must either form a triangle or lie in a straight line.
First suppose they form a triangle, $YRG$, as in Figure $16$.
Then a fourth contiguous region, $B$, must lie either within or without the triangle.
If within, it is obviously enclosed.
Place it outside and make it contiguous with $Y$ and $G$, as shown.
Then $B$ cannot be made contiguous with $R$ without enclosing either $Y$ or $G$.
Make $B$ contiguous with $Y$ and $R$.
Then $B$ cannot be made contiguous with $G$ without enclosing either $Y$ or $R$.
Make $B$ contiguous with $R$ and $G$.
Then $B$ cannot be made contiguous with $Y$ without enclosing either $R$ or $G$.
Take the second case, where $RYG$ lie on a straight line, as in Figure $17$.
If $B$ lies within the figure it is enclosed.
Place $B$ outside and make it contiguous with $R$ and $G$, as shown.
Then $B$ cannot be made contiguous with $Y$ without enclosing either $R$ or $G$.
Make $B$ contiguous with $R$ and $Y$.
Then $B$ cannot be made contiguous with $G$ without enclosing either $R$ or $Y$.
Make $B$ contiguous with $Y$ and $G$.
Then $B$ cannot be made contiguous with $R$ without enclosing either $Y$ or $G$.
We have thus taken every possible case and found that if $3$ regions are contiguous each with each, a fourth region cannot be made contiguous with all three without enclosing one region.
Figure $10$ is Figure $8$ before the transformation.
Figure $11$ is the same as Figure $9$.
It will be seen at once that you cannot possibly reach $R$ from the outside.
Therefore $4$ regions cannot possibly be drawn so that a $5$th may be contiguous with every one of them.
Consequently the $5$th region may certainly repeat the colour $R$.
And if you cannot draw $5$ regions, it is quite obvious that you cannot draw any greater number contiguous each with each.
It is now clear that, at each successive addition of a new region, all the regions previously drawn must be contiguous each with each to prevent the employment of a repeated colour.
We can draw $4$ regions under this condition, only one region must always be enclosed.
Now, we can make the $5$th region contiguous with:
- only one region, as in Figure $12$
- two regions, as in Figure $13$
- three regions, as in Figure $14$.
In the first case the new region can be either $Y$ or $B$ or $R$.
In the second case the new region can be either $B$ or $R$.
In the third case the new region can be $R$ only.
We take the last case, Figure $14$, and bring out, or repeat, $R$.
But in doing so we have been compelled to enclose $G$.
In drawing a sixth region the best we can do in trying to upset the theorem is the bring out $G$, as in Figure $15$.
The result is that we must enclose $R$.
And so on into infinity.
We can never avoid enclosing a colour at each successive step, and thus making the colour available for the next step.
If you cannot artificially construct a map that will require a fifth colour, such a map cannot possibly occur.
Therefore a fifth colour can never be necessary, and the truth of the theorem is proved.
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.
Also see
Historical Note
- For just about $50$ years various mathematicians, including De Morgan, Cayley, Kempe, Heawood, Heffter, Wernicke, Birkhoff, Franklin and many others have attempted to prove the truth of this theorem,
- and in a long and learned article in the American Mathematical Monthly for July-August, $1923$, Professor Brahana, of the University of Illinois, states that "the problem is still unsolved."
Martin Gardner, in his $1968$ repackaging 536 Puzzles & Curious Problems, refutes Dudeney's claim to have proved it.
He goes on to advertise his own contribution in his $1966$ Martin Gardner's New Mathematical Diversions from Scientific American.
Sources
- 1926: Henry Ernest Dudeney: Modern Puzzles ... (previous) ... (next): Solutions: $140$. -- The Four-Colour Map Theorem
- 1968: Henry Ernest Dudeney: 536 Puzzles & Curious Problems ... (previous) ... (next): Answers: $442$. The Four-Color Map Theorem