Answers 379It is now clear that, at each successive addition of a new country, all
the countries previously drawn must be contiguous each with each to prevent
the employment of a repeated color. We can draw four countries under
this condition, only one country must always be enclosed. Now, we can
make the fifth country contiguous with only one country (as in Figure 12),
with two countries (as in Figure 13), or with three countries (as in Figure 14).
In the first case the new country can be Y or B or R, in the second case
B or R, and in the third case 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 country the best we can do (in trying to up-
set the theorem) is to "bring out" G (as in Figure 15), and the result is that
we must enclose R. And so on into infinity. We can never avoid enclosing a
color at every successive step, and thus making the color available for the next
step. If you cannot artificially construct a map that will require a fifth color,
such a map cannot possibly occur. Therefore a fifth color can never be
necessary, and the truth of the theorem is proved.
[Dudeney correctly shows that no more than four regions can be drawn so
that each borders all the others, but his proof fails to show that four colors
are sufficient for all maps. It is true that if any four regions of a map are con-
sidered in isolation, 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 such a way that
five colors are demanded.
The difficulty is best seen by actually constructing a complicated map,
using the step by step procedure proposed by Dudeney. If each new region is
drawn so as to border three others, its color is determined automatically and
four-color maps can indeed be extended to infinity. But if many new regions
are added that touch only one, two, or no other previously drawn regions, the
choice of colors for these regions becomes arbitrary. As the map grows in size
and complexity, one suddenly discovers that it is possible to construct a new
region that will require a fifth color. By backtracking and altering previous
colors, it appears that it is always possible to rectify the mistake and take care
of the new region without going to a fifth color. But is it always possible? This
is the conjecture that remains unproved. For a discussion of the problem, and
a list of recent references, see the chapter on the four-color map theorem in
my New Mathematical Diversions from Scientific American.-M. G.]