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 neighbouring countries (i.e. which have a common frontier segment) share the same colour. Indeed, as Francis had noticed, four colours are sufficient to paint the counties on the map of England, so why wouldn't they be sufficient in all other cases, for arbitrary maps drawn on paper (i.e. on the plane) or on a globe (i.e. on a sphere)? To make things precise, let's assume the frontier of each country consists of one closed curve (which is not always the case with modern states).
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 23rd , 1852.
Fig. 1. There are no four pairwise neighbouring countries
on this map, nevertheless four colours are indispensable for the
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 19th century there was a general
belief in England that the four-colours problem had been solved
and the only possible thing to do is to simplify the proof. For
instance, in 1887 the Journal of Education announced a
competition organised by the Headmaster of the Clifton College
to provide a proof of the theorem in less than thirty manuscript
lines. Among many other participants, the Bishop of London and
the future Archbishop of Canterbury, Frederick Temple, joined
in with his own "proof".
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 Quarterly Journal
of Mathematics and contained a counterexample making away
with Kempe's proof, together with a proof of the fact that five
colours are indeed always sufficient, and with still one more
astonishing result, which we will now proceed to explain in more
Consider maps lying on a surface Pg
(Fig.2) obtained from a sphere by gluing g "handles"
to it. Equivalently, you may think of Pg
as the surface of a cracknel with g holes made by the baker.
Fig. 2. The surface Pg for
The number g is called the genus of the surface Pg. If you make a cardboard polygon to model Pg (for g=1 this could be a cube with a hole inside, as in Fig. 3), you will easily notice that the number E of its edges, the number V of its vertices and the number S of its sides always satisfy the equality
(1) V - E + S = EP = 2 - 2g.
Fig. 3. The cube with a hole inside: V = S
= 16, E = 32.
The number EP = 2 - 2g is the so-called Euler-Poincaré characteristic of the surface Pg. It turns out that the following holds:
Theorem (Heawood, 1890). For positive
g, any map lying on the surface Pg
can be coloured with at most h(g)
We will use the following simple lemma in the proof:
Lemma. If g is positive and the number of countries on the map M lying on Pg is greater than h(g), then there is at least one country with at most h(g)-1 neighbours.
Proof of the Lemma. Let's assume the map M placed on the surface Pg is a deformed polyhedronal model of Pg. Then the number of countries S, the number E of frontiers between nieghbouring countries and the number V of "vertices", i.e. meet-points for several frontiers, satisfy Euler's equality (1).
As for any other polyhedron, we have , so (1) implies . Let a be the mean number of neighbours of a country on M; then aS=2E, since by multiplying the number of countries by the mean number of neighbours we count twice every frontier between two countries. Thus , i.e.
Consider now the quadratic polynomial . The value of EP=2-2g being non-positive, the polynomial has two real roots x1 and x2 with x1>0. Using the well-known school formula for the roots of a quadratic polynomial you can see that the integral part of x1 is precisely the strange number h(g) which made its first appearance in Heawood's theorem. Let's put the condition in the following form:
By assumption S>h(g)=[x1], so S>x1 (S is a natural number!) and EP being non-positive, we have . The conditions (2) and (3) now yield , and therefore However, there is a country on the map M that has at most [a] neighbours, of course, and this observation completes the proof.
Now, to prove the theorem we will use induction on the number
S of countries. The claim is obvious for ,
since each country can be painted with a different colour. So,
assume that the claim holds true for some S not less than
h(g) and consider a map M with S+1 countries.
It follows from the Lemma that there is a country M0
with at most h(g)-1 neighbours (fig. 4).
Fig. 4. A fragment of the map M with k
not greater than h(g)-1.
For a short while let's forget about one frontier between M0
and one of its neighbours on the original map M, say, M1
(the frontier is drawn with a different colour in Fig. 4). The
new map has S countries now and thus, by inductive assumption,
can be painted with at most h(g) colours. However, at most
h(g)-1 colours are required to paint all the neighbours
of M0, so we can restore the frontier
between M0 and M1
and use for M0 that one of all the
h(g) available colours that was not assigned to any of
its neighbours. This completes the proof.
It may be quite surprising that Heawood's estimation cannot be
sharpened: for any g there is a map on the surface Pg
for which h(g)-1 colours are not sufficient. For example,
for a torus g=1, h(1)=7, whereas Fig. 5 exhibits
a map on a torus, with 7 countries any two of which are adjacent;
thus indeed 7 colours are needed to colour the map as required.
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 g. The
task of providing a proof for this statement turned out to be
by far more difficult. That Heawood was right was only known by
the end of the sixties in our 20th century, thanks
to many years of hard efforts by numerous mathematicians, amateurs
among them too: in February 1968 Jean Mayer, a professor of French
literature at the University of Montpellier, proved that Heawood's
estimation cannot be sharpened for the genus g=59 and it
so happened that this was the last case missing to complete the
You may have noticed that the proof of the Lemma fails in the
case of a sphere (when g=0, EP=2). Nevertheless,
h(0)=4, so Heawood's formula gives the right number of
colours for the sphere too! We are now safe to say so, since the
four-colours theorem was finally proved by Kenneth Appel and Wolfgang
Haken in 1976, after six years of joint work. Their proof cannot
be checked "by hand" by any human being. Not only does
the final version extend over 100 pages of text and 400 microfilms
with pictures, but the verification of several thousand particular
cases was made by a computer program designed by Haken and Appel
and the computer took several hundred hours to check all of them.
Incidentally, isn't it astonishing that the proof of the map-colouring
theorem is so simple for a torus and so complex for a sphere?
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
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: What is a proof? Can every
proof be understood and checked? In any case, the cartographers
do not seem to be bothered by the four-colours theorem: in the
newest Encyclopaedia published by PWN (Polish Scientific Publishers)
not less then five colours are used to distinguish the different
voivodships on the map of Poland...