Four Colours Suffice?

Robin Wilson,
former Visiting Gresham Professor in the History of Mathematics

[Introduction]

In October 1852, Francis Guthrie, a former student of Augustus De Morgan (professor of mathematics at University College London), was colouring a map of England. He noticed that if neighbouring countries had to be differently coloured, then only four colours were needed. Do four colours suffice for colouring all maps, however complicated?, he wondered.

On 23 October of that year, 150 years ago this week, Guthrie's brother Frederick asked De Morgan, who immediately became fascinated with the problem and communicated it to his friends. De Morgan's famous letter of 23 October 1852 to the Irish mathematical physicist Sir William Rowan Hamilton included the following extract.

A student of mine asked me today to give him a reason for a fact which I did not know was a fact - and do not yet. [He then described the problem, and gave a simple example of a map for which four colours are needed.] Query: cannot a necessity for five or more be invented?

De Morgan also wrote about the problem to the philosopher William Whewell, Master of Trinity College Cambridge, and others. The problem first appeared in print in the middle of an unsigned book review (actually by De Morgan) of Whewell's Philosophy of Discovery. This review contained the following very strange passage:

Now, it must have been always known to map-colourers that four different colours are enough. Let the counties come cranking in, as Hotspur says, with as many and as odd convolutions as the designer chooses to give them; let them go in and out and roundabout in such a manner that it would be quite absurd in the Queen's writ to tell the sheriff that A. B. could run up and down in his bailiwick: still, four colours will be enough to make all requisite distinction…

After this, the problem was largely forgotten until 13 June 1878, some years after De Morgan's death, when Arthur Cayley, of Trinity College Cambridge, asked at a meeting of the London Mathematical Society whether the map colouring problem had been solved. Although Cayley was unable to solve it, he was able to explain where the difficulty lies, and he showed how the problem could be simplified by considering only maps in which exactly three countries meet at any point.

A well-known 'proof' that four colours are sufficient was given in 1879 by Alfred Kempe, a London barrister who had studied at Cambridge with Cayley and who was later Treasurer of the Royal Society for many years. This is probably the most famous fallacious proof in the entire history of mathematics, although it contained a number of good ideas.

Kempe's proof was essentially as follows. We assume that all but one of the countries of the map have been coloured with four colours, and then show how the colouring can always be extended to the final country. Since all maps with 1, 2, 3 or 4 countries can be coloured with four colours, we can extend the colouring to five, six, seven, … countries - that is, to all maps. Now, using a result known as Euler's polyhedron formula (which I won't go into), it's easy to show that every map has a country with at most five neighbours - a digon (two-sided country), triangle , square or pentagon. Let's look at these in turn.

If the map has a triangle or less, we shrink it to a point. There are then fewer countries, so we can four-colour the resulting map. Put the triangle back - it's surrounded by at most three countries, taking at most three colours, so there's a spare colour to colour the triangle - giving the required contradiction.

If, now, there's a square, we follow Kempe and look at just two of the colours - say, the red country immediately above the square and the green one immediately below the square - and ask the following question: is the red-green part of the map above the square connected to the red-green part of the map below the square? Let's look at the two cases that can arise.

If NO, then all the red and green countries above the square are not linked to those below the square, and we can interchange the reds and greens above the square (red becomes green, green becomes red, and so on), so that the countries immediately above and below the square are both green, and we can then colour the square red, so that the map can be coloured with four colours after all. But if YES, then interchanging the red and green colours as described above leaves us no better off than before - the square still has all four colours around it. But instead, let's look at the blue and yellow countries immediately to the left and right of the square. The blue and yellow countries to the left of the square cannot be linked to the blue and yellow countries to the right of the square, because the red-green ring of countries gets in the way. We can thus interchange the blues and oranges on the left of the square without affecting those on the right of the square. The square can then be coloured blue, again completing the colouring of the square in four colours.

Finally, if there's a pentagon, Kempe used a similar argument, this time involving two interchanges of colour, to produce just three colours around the pentagon. The pentagon is then coloured with the fourth colour, thereby completing the colouring of the map with four colours. This completes the proof.

For eleven years Kempe's proof was widely accepted - by Cayley and many others - so it was a great surprise when Percy Heawood of Durham dropped his 'bombshell' in 1890. In his paper he pointed out the fundamental error in Kempe's proof, showing that, in the case of the pentagon, we cannot always carry out two interchanges of colour simultaneously. However, he managed to salvage enough to prove that every map can be coloured with five colours - still a remarkable result.

Heawood also tried to generalise the idea of map colouring to other surfaces. Using projection from a globe to and from the plane, we can see that colouring maps on the plane is the same as colouring maps on a sphere - so what about colouring maps on a 'torus', a rubber ring or ring doughnut? Here the magic number turns out to be 7 - a torus version of Euler's polyhedron formula shows that seven colours suffice to colour all maps, and Heawood produced a torus map that needs all seven colours.
If we now put in more holes (such as in a pretzel), we need more colours. In fact, as Heawood showed, if we have a doughnut with h holes, then every map on the surface can be coloured with N colours, where N is given by the complicated expression [½{7 + v(1+48h)}]: for example, if h = 1 (for the torus), we deduce that every map on the torus can be coloured with [½{7 + v49}] = 7 colours, as before. What Heawood failed to show is that for any surface there are always maps that need this number of colours - and that took a further 78 years to prove. Proving the Heawood conjecture, as it came to be called, turned out to involve twelve completely separate cases.

By 1967 the German mathematician Gerhard Ringel and the American Ted Youngs had settled most of these cases. Ringel had a sabbatical year and went to California to work with Youngs on the remaining cases, and in a couple of months they finished the proof. Great rejoicing! Later that year, Ringel was driving up the California expressway when he was stopped by a traffic cop for speeding. The cop looked at his driving licence, and said 'Ringel, eh - are you the one who solved the Heawood conjecture?' Ringel, surprised, said 'yes'. It turned out that the traffic cop's son was in Professor Youngs' calculus class, and the result was that Ringel got let off with a warning - and if that doesn't show the uses of map colouring, I don't know what does!

Returning to the four-colour problem for maps on the plane or sphere, very little progress was made for many years - in fact it took 86 years after Heawood's paper to complete the proof. Kempe's error proved very difficult to patch up, but in fact the eventual solution used two important ideas that can be traced back to Kempe. We look at these in turn.

The first is that of an unavoidable set of countries. Since every map contains at worst a pentagon, we say that the configurations listed as {digon, triangle, square, pentagon} form an unavoidable set - in any map at least one of these must appear - you can't avoid them. As we've seen, we can deal with the first three of these, but the pentagon causes trouble, so we try to replace it by something else. In fact, we can show that any map without a digon, triangle or square must have, not only a pentagon, but either two adjacent pentagons or a pentagon joined to a hexagon - so we get a new unavoidable set: {digon, triangle, square, two adjacent pentagons, pentagon adjacent to a hexagon}.
We've also seen that the digon, triangle and square are all reducible configurations: this means that any colouring of the rest of the map in four colours can be extended to include any of them - but we were unable to deal with the pentagon. However, the American mathematician George Birkhoff showed in 1913 that a particular arrangement of four adjacent pentagons is reducible.

In order to prove that four colours are sufficient for any map, we need to find an unavoidable set of reducible configurations - to say that it is an unavoidable set means that every map must include at least one of them, and if whichever it is is then reducible, then we can complete the colouring of the map.

For the first two-thirds of the twentieth century the search was on to find both unavoidable sets of configurations and reducible configurations. The first person to try to combine these ideas was the German mathematician Heinrich Heesch, who spent forty years of his life looking for an unavoidable set of reducible configurations. Eventually, in 1976, following Heesch's ideas, two mathematicians from the University of Illinois, Kenneth Appel and Wolfgang Haken found an unavoidable set of 1936 reducible configurations, after a massive four-year search, making extensive use of the most powerful computers then available. Appel and Haken subsequently simplified their unavoidable set to 1482 configurations and published their solution twenty-five years ago, in late 1977.

Since then, a more structured proof has been obtained by four mathematicians - Neil Robertson, Dan Sanders, Paul Seymour and Robin Thomas. Their proof, obtained in 1994, still uses the Appel-Haken computer-based approach but involves only about 600 reducible configurations. However, as yet, there is still no generally accepted solution that makes no use of a computer . . .

© Robin Wilson, 21 October 2002