## Map colouring
In 1852 a student of the University College in London, Francis
Guthrie, informed his brother Frederick that, to his knowledge,
any map can be painted with only four colours in such a way that
no two
Frederick Guthrie passed the problem on to one of his teachers,
Augustus de Morgan. De Morgan proved that there is no (plane)
map with five pairwise neighbouring countries. Unfortunately,
this is not enough to prove the non-existence of a map requiring
at least five colours (see Fig. 1) and it is not clear whether
de Morgan was conscious of this gap, when he mentioned the question
to Hamilton in a letter of October 23
Fig. 1. There are no four pairwise neighbouring countries
on this map, nevertheless four colours are indispensable for the
colouring.
The four-colours problem became truly famous, as it turned out,
for about one hundred years, in June 1878, when Arthur Caley presented
it to the London Mathematical Society, adding that he himself
knew of no solution to it. Shortly after ''proofs" of the
four-colours theorem were published by Arthur Bray Kempe, a professional
barrister (1879), and Peter Guthrie Tait (1880). Both papers were
greeted with vivid interest and favour (Kempe even became member
of the Royal Society in consideration for his achievement).
In the eighties of the 19
This accounts for the apologetical tone in which John Heawood
announced an essential error in Kempe's argument in 1890. Heawood's
short paper of six pages was published in the
Consider maps lying on a surface P
Fig. 2. The surface P
The number
(1)
Fig. 3. The cube with a hole inside:
The number
We will use the following simple lemma in the proof:
As for any other polyhedron, we have ,
so (1) implies . Let
(2) .
Consider now the quadratic polynomial .
The value of (3) .
By assumption
Now, to prove the theorem we will use induction on the number
Fig. 4. A fragment of the map
For a short while let's forget about one frontier between
It may be quite surprising that Heawood's estimation cannot be
sharpened: for any
Fig. 5. A map on a torus, with seven pairs of adjacent
countries. The torus is represented here on paper strip, which
can be transformed into a torus by gluing the borders as indicated
by the arrows.
The above example is due to Heawood, who unconcernedly declared
that similar examples can be found for every genus
You may have noticed that the proof of the Lemma fails in the
case of a sphere (when
Euler formula fans may try to find their own proof
(not too long and quite simple) of the fact that every map on
the plane can be coloured with 6 colours at most. It should be
observed first that no loss of generality is implied by the assumption
that at any point of the plane at most three different frontiers
meet.
There is more than one meaning to Appel and Haken's result. First
of all, they have solved a famous problem, left open for more
than a hundred years. But second, their work forced the mathematicians
to reconsider old questions: |