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 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 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 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 detail.

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 g=3.

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) colours, where

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.

(2) .

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:

(3) .

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 picture.

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 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: 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...

Pawel Strzelecki