There's nothing that occupies a child like a colouring book and a box of crayons. They can spend hours happily turning the dullest of outline drawings into something which rivals a Jimi Hendrix album cover. Younger children may not always select the most appropriate colours for the job, but they will try to use different ones in adjoining regions, lest they lose the defined shape of what they're colouring in. They find it easier to do this – and it will yield the most psychedelic results – if they have a large box of crayons of every different shade. On the other hand, if they have only a few crayons, it may still be possible to colour the picture in this way; but how many do they need?

Colouring Maps

This is another of those problems which has interested mathematicians for many years. Now, there's not much benefit to mankind in knowing how many crayons you might need to colour a picture of a rabbit, but there are some slightly more relevant applications, one being the colouring of maps. Political maps divide an area of the world by country, state or county, and it's important to colour adjoining regions differently to make the borders clear. Cartographers supposedly want to keep their maps looking as simple as possible – and perhaps print them as cheaply as possible – by using the minimum number of colours. It's the same problem, though: how many colours do they actually need¹?

To some extent it depends on the map. If you have just a single region – an island, say – then you need only one colour, but then the surrounding sea will need a second colour – blue, presumably. Islands with two countries – like Ireland, for example, which is divided into the UK-administered North and the Republic of Ireland in the South – would need three colours, including the sea.

Sometimes you need four colours. Take the land-locked state of Nevada, USA (pictured in red to the right). This has borders with 5 other states, which, clockwise, are California, Oregon, Idaho, Utah and Arizona. Let's say we have only three crayons (red, yellow and blue). Now, we'll start by colouring Nevada red, and we'll use the other two colours for its neighbours. So, California is yellow, Oregon blue, Idaho yellow, Utah blue, but what about Arizona? It has borders with California, Nevada and Utah, all of which are different colours. We need a fourth, green crayon.

So, we know we need four colours for some maps, but do we ever need five or more for other, more complicated configurations? Well, it didn't seem so. All the maps we drew could indeed be coloured with no more than four crayons. There was a lingering doubt, though. Countries we know about are fairly straightforward in shape. Had we really tested ourselves with all manner of fiendishly shaped nations and twisty borders? Until someone proved otherwise, it was always possible that a super-Nevada was out there that needed a fifth, purple crayon. The thought of some poor cartographer being caught short was not one to be entertained. The world of mathematics needed an answer.

Guthrie's Conjecture and Kempe's 'Proof'

The first mathematician to go on record as stating that four colours looked sufficient for all maps was Francis Guthrie, a student at University College, London in the 1850s. Guthrie hadn't proved anything – it was just a conjecture. Once the problem became discussed in mathematical circles it captured the imagination of some of the finest mathematicians of the age, including Augustus de Morgan (who was tutoring Guthrie's brother Frederick) and Arthur Cayley. Other mathematicians, including Alexander Hamilton² wisely avoided it.

The first 'proof' was claimed in 1879 by Alfred Bray Kempe³, a London barrister. It was accepted by his peers, and published in both Nature and the American Journal of Mathematics. It even won this amateur mathematician a fellowship of the Royal Society. His elegant proof, as with any proof of this theorem, is too long and complicated to describe in full in this Entry, but it was based on the following principles.

Kempe tried to prove the four colour theorem by contradiction. If there were to exist a map which required five colours, then it would fail to follow a particular argument in mathematical logic. Therefore, such a map could not exist, so no more than four colours would be necessary to colour any map.

As a starting point, Kempe knew that it was impossible to have a map where every region has six or more neighbours⁴. Mathematically, this result followed from work by Leonhard Euler, who had established a formula connecting the numbers of sides, corners and edges for geometric figures.

Therefore, every map had to contain within it at least one of the following 'unavoidable set' of configurations:

• A region with two neighbours, or 'digon' (like Liechtenstein, landlocked between Austria and Switzerland);
• A region with three neighbours, or 'triangle' (like Luxembourg, nestled between France, Belgium and Germany);
• A region with four neighbours, or 'square' (like the Czech Republic, lying between Germany, Poland, Slovakia and Austria); or
• A region with five neighbours, or 'pentagon' (like Slovakia, which has Austria, Czech Republic, Poland, Ukraine and Hungary neighbouring it).

Kempe then argued that if there were to exist a map which required five colours, then there must be a simplest-possible version of it, having the minimum number of regions, such that when you removed any one of those regions, it would then need no more than four colours. All he needed to do, therefore, was to consider each of the above configurations (the digon, triangle, square and pentagon), one of which would have to appear in any such map. In each case, he did the following:

1. He removed the country from the map, by shrinking it to a point. By definition, this resulted in one fewer colour being required.

2. He reinstated the country, then attempted to show that the resulting map could be coloured with only four colours. If he could do this for every configuration in his unavoidable set, then this would contradict the logical argument and so prove the four colour conjecture to be true.

Kempe tackled each of the configurations in turn. Maps for the digon and triangle-shaped countries were very simple to reconstruct with four colours (Mathematicians say a configuration is 'reducible' if they can do this). The square country was a little more tricky, but by re-colouring the neighbouring countries and considering logical chains of outlying neighbours, he indeed showed the square was reducible. Finally, he tackled the pentagon, and, by recolouring two countries simultaneously, again showed that it could be reduced. Kempe had proved the four colour theorem by demonstrating with flawless logic that each configuration was reducible... or had he?

Percy Heawood: Party Pooper

Eleven years later, the mathematician Percy Heawood spotted a flaw. Using Kempe's logic, Heawood showed that for a pentagon-shaped country, if neighbouring countries were re-coloured simultaneously, then a certain configuration of regions would require a fifth colour. Neither Kempe nor any of the other mathematicians who had previously embraced his now-shattered proof had any answer to it. The four colour theorem became a conjecture once again.

Despite this flaw in his reasoning, Kempe had actually done a lot of good mathematical work. His ideas, particularly the unavoidable set of configurations and consideration of their reducibility, became standard techniques for those who would follow. Heawood also used Kempe's analysis to prove that no more than five colours were necessary to colour any map. Kempe's work was to inspire other mathematicians, including those who were eventually to solve the problem.

Yet, many years were to pass, as a succession of mathematicians attempted to define the Holy Grail of an unavoidable set of reducible configurations. The pentagon was clearly not good enough on its own, as Heawood had shown, but it could be split into a larger set of more specific combinations, for example: a pentagon flanked by a square, or one flanked by another pentagon alongside a triangle. The trouble was that there would turn out to be very many of these, each of which would have to be proven to be reducible. Countless attempts were made to do just this for much of the 20th Century, yet all claims of success failed under closer scrutiny.

Being such a simple problem to define, many mathematicians became obsessed by it, convinced that it would be easy to solve. One story involves the wives of American mathematicians George Birkhoff and Arthur Bernhart, who met at a mathematical society meeting. Said Mrs Birkhoff to the newly married Mrs Bernhart:

Did your husband make you colour maps on your honeymoon, too?

Map colouring also became a popular subject for so-called mathematical cranks, amateurs who flooded academic institutions with letters outlining their outlandish 'proofs', often refusing to accept the flaws subsequently pointed out in their logic.

Mathematicians were only able to finally prove the four colour theorem in the 1970s, using a very un-mathematical technique.

Appel and Haken

It became clear to many that the unavoidable set would be very large, possible including many thousands of configurations, each of which would need to be proven as reducible. It seemed that this could turn out to be simply too onerous a task. An advance came in the 1960s, when the German mathematician Heinrich Heesch from the University of Hannover used computers to classify certain configurations as reducible, using a technique from network theory known as discharging.

News of Heesch's technique then reached Kenneth Appel and Wolfgang Haken of the University of Illinois. They approached the problem from the other direction: they experimented with programming a computer to compile configurations, checking each in turn for reducibility using an improved version of Heesch's method, with the aim of eventually completing an unavoidable set. Every time the computer found an irreducible configuration, or if it spent too long in checking it⁵, then the attempt would be abandoned and the whole process would start again. Effectively, they were compiling their unavoidable set with an element of trial and error.

In June 1976, to cut a long story short, they achieved it. Appel and Haken's unavoidable set comprised just under 2,000 configurations, and the program took 1,000 hours of computer time to run. The news hit the headlines around the world:

Their proof, published today, runs to 100 pages of summary, 100 pages of detail and a further 700 pages of backup work. It contains 10,000 diagrams, and the computer printout stands four feet high on the floor.
— The Times, 23 July, 1976.

Almost 100 years after Kempe's ill-fated proof, the four colour conjecture was a theorem once again, but not everybody agreed. A fierce philosophical debate ensued about the nature of Appel and Haken's proof. This wasn't the kind of proof you could pick up and read. It wasn't an 'a priori deduction of a statement from premises'. There was a gaping hole in the middle of it which was filled with an experiment, one which had been performed by a large piece of tin with flashing lights, also known as an IBM 370-168. Deep Thought had provided the answer.

You have to take your hat off to the programmers, though. As we would later see with Fermat's Last Theorem, each mathematician tackling this problem had stood on the shoulders of the giants before them to arrive at the final result. We always thought the four colour conjecture was true, but now we knew it. Appel and Haken took the glory, and deservedly so.

It was terribly tedious, with no intellectual stimulation. There is no simple, elegant answer, and we had to make an absolutely horrendous case analysis of every possibility. I hope it will encourage mathematicians to realise that there are some problems still to be solved, where there is no God-given answer, and which can only be solved by detailed work. Some people might think they're best left unsolved.
— Kenneth Appel

Four Colour Trivia

• The University of Illinois celebrated Appel and Haken's breakthrough in 1976 by franking their outgoing mail with the enigmatic 'Four Colors Suffice'.

• From time to time, there exist countries that have outlying provinces or 'exclaves' on the same continent. Two well-known ones include Russia (Kaliningrad⁶) and the United States (Alaska). The state of Kentucky, USA also has an outlying region, the Kentucky Bend, surrounded by Missouri and Tennessee. If all politically-affiliated regions must be coloured the same, then four colours are not necessarily sufficient to colour their map.



• A similar problem arises where we have large bodies of water. The world's oceans are all interconnected and are conventionally coloured blue; it may not be possible, however, to also colour inland lakes and seas blue, if we are restricted to four colours. The imaginary island in the diagram on the right has a lake in the centre, but if we insist that it has the same colour as the surrounding ocean, then we need four further colours for the four states, ie five colours in all.

• Finally, mathematicians have come up with some other remarkable results. If you print a map on a sphere, then four colours are still sufficient, but if it's printed on a Mobius strip, then you may need up to six. If, on the other hand, you want to print a political map on a solid shape with a hole in it, like a doughnut⁷, then you may need as many as seven colours. Our old friend Percy Heawood devised a simple formula for the maximum number of colours we would need for maps printed on solid shapes with a given number of holes in them. In the following equation, N_u is the number of colours required⁸, and g represents the number of holes:

  N_u ≡ ½ ( 7 + √(48g + 1) )

  This result, known as the Heawood Conjecture, was proved in 1968 for all cases where there is at least one hole, eight years before Appel and Haken conquered the four colour theorem. It tells us that if we lived on a three-holed pretzel-shaped world, then we would need up to nine colours for our political maps. Food for thought, indeed.