Four Colours Suffice

Four Colours Suffice: how the Map Problem was solved, Robin Wilson, 2002. 014100908X (Blackwell’s, amazon.com, amazon.co.uk).

Robin Wilson taught me algebra and topology in my first year at Oxford. I despised him because (in no particular order)

  • He was the son of the loathed Prime Minister.
  • He had been borrowed from the Open University.
  • He wore fluorescent socks.
  • He adapted songs from The Sound of Music for didactic purposes (“G, a group, an abstract group”, and “My Favourite Rings”) and made a horrible pun about the distinguishing characteristic of Hausdorff spaces.

He, on the other hand, told the Master of my college I was “arrogant and difficult to teach”.

Robin Wilson’s field is graph theory, and since the controversial proof of the Four-Colour Theorem is the most famous result in that field, he was the logical person to write this book.

The Four-Colour Problem (Theorem, now that it’s been proved) is one of those delightful things that it’s possible to describe on the back of a napkin. Take an outline map – of the counties of England or the countries of the world – and colour it so that no two adjacent regions have the same colour. How many colours do you need? Obviously at least three (just draw three regions that meet at a point) and almost obviously at least four (replace that point with a tiny region that touches each of the other three). But are four enough?

The problem has exercised mathematicians for a century and a half. It is so simple that the solution surely must be simple too. It was solved for the surface of a bagel (seven are enough and sometimes seven are needed) and the surface of a three-holed pretzel (nine) but the plane or sphere resisted all attacks.

A lot of mathematical proof consists of taking the obvious-but-unproved bit of the proposition you’re looking at and restating it in various ways until you get it into a form where you can prove it (although by then it often isn’t obvious any more) – a bit like pushing around an air bubble under the wallpaper you’ve just hung up until you get to a seam and the air can escape. Only in maths you can’t see the seams and sometimes you think you’ve got rid of the bubble when you’ve only pushed it into a corner out of sight. The thing is that it’s hard, when a result is obviously true, to recognise that one of the steps in your proof “ain’t necessarily so”. Often someone else has to do it for you.

A friend of mine says he wishes maths was taught on historical principles. He says that seeing how people discovered what everyone now knows, seeing what they tried and why they tried it, what worked and what didn’t, makes it all far more understandable then if you simply present the finished article, seamless and gleaming, with all the screw-holes filled in and all the scratches polished out; and I think he’s right. It’s like looking at the Old Masters’ drawings rather than their paintings. If he is right, then this is the book for him.

Robin Wilson gives us all the history we need to know – the personalities, the squabbles, the successes, the failures, the wrong turnings. In parallel with the history, he takes us through the proofs so that we can see for ourselves what was going on. Let me put this to the test with a restaurant-napkin summary of the whole grand strategy.

Minimal criminals

Let us assume that there exist maps that can’t be coloured with four colours (“uncolourable maps”), and try to derive a contradiction.

Let’s list all the uncolourable maps and label each one with the number of countries it contains. Among those numbers there will be a smallest number. Uncolourable maps with that number of countries are called “minimal criminals”.

To put it another way, a minimal criminal is an uncolourable map with the property that every smaller map is colourable.

Not minimal or not a criminal

with-31.gifSuppose (which isn’t actually true) that every map must have a country with exactly three neighbours. In that case some small part of our minimal criminal must look like this.

no-3.gifSo let’s remove the three-sided country in the middle. This gives us a smaller map. This is either colourable or it isn’t.

If the smaller map isn’t colourable, then our minimal criminal isn’t minimal because it isn’t the smallest uncolourable map after all.

no-3c.gifIf the smaller map is colourable, let’s colour it. The three countries in the part we’re looking at will take one colour each.

with-3c.gifSo then let’s put back the country we removed. Can we colour it? Yes, we can, because it has only three differently coloured neighbours, so we can use the fourth colour.

So if the smaller map is colourable then our minimal criminal isn’t a criminal.

So a minimal criminal is either not minimal or not a criminal – which is a contradiction, so minimal criminals can’t exist – so every map can be coloured with at most four colours, Q.E.D.

The whole story

Colouring cubeThe snag is, it’s not true about every map needing to have a country with three neighbours. On the other hand, it is true that every map has to contain at least one country that has three or four or five neighbours. Wilson shows us the proof, so if you just give me another napkin… (and as a result of this, he shows us that we have proved the Six-Colour Theorem, that every map can be coloured with at most six colours, which at least takes us one step towards our goal).

In 1879 the London barrister Alfred Bray Kempe proved the Four-Colour Theorem by using the same kind of “take-it-out-and-put-it-back” approach that I’ve described for three-sided countries. For a country with four neighbours he devised an ingenious way of flipping the colours round so that when the four-sided country was put back, a free colour was available for it. Countries with five neighbours were handled in the same sort of way.

Kempe’s proof was universally accepted, but in 1890 a mathematics lecture at Durham called Percy Heawood (who was also a noted scholar in Latin, Greek and Hebrew) found a defect in it which meant that the argument for five-sided countries didn’t work. He was embarrassed at having to wreck such a beautiful proof but in mathematics proving the right result for the wrong reasons is simply WRONG; so he had to do it, and Kempe admitted defeat. At least, as Wilson shows us, applying Kempe’s methods gives us a proof of the Five-Colour Theorem, which is a step in the right direction.

The rest of Wilson’s book traces the 80 years it took to take that final step. The concepts were just the ones I have already described: on the one hand, finding a set of configurations such that every map has to contain at least one of them (“an unavoidable set”) and on the other hand making sure that each one of those configurations was susceptible to the “minimal criminal” argument.

I had never realised before what appalling courage a mathematician needs. As he works, he has no way of knowing if his approach is going to work; whether someone else is going the same way; or whether some completely different approach will yield a far, far simpler proof – and he may risk years of his life on this enterprise.

Wolfgang Haken, for example, was famous for his painstaking approach to big unsolved problems (“Mathematicians usually know when they have gotten too deep into the forest to proceed any further: that is the time Haken takes out his penknife and cuts down the trees one at a time”). He solved a long-standing problem in topology (the knot problem), then went on to the next (the Poincaré Conjecture), which he split into 200 distinct cases. He completed the proof for 198 of these cases, then struggled for 13 years on the final two; then gave up, defeated. What do you do after you have been defeated in a thirteen years’ war against an intractable topological problem? You declare war on another one. This time it took nine years and the help of a collaborator, Kenneth Appel, and in the end it turned out to be a race as much as a war, with two rivals just months behind.

Suddenly, in 1978, Haken and Appel found they had both won the race and won the war. Their main competitors swallowed their disappointment and threw themselves into checking the proof, which was hundreds of pages long and listed 1,482 unavoidable sets, each one of which had been checked by a computer to be usable in the “minimal criminal” argument.

The Four-Colour Theorem was proved.

Is it a proof? Philosophers have argued over whether something so dependent on computer programs can be considered a proof, but on the whole the answer seems to be Yes. Is it the proof? No-one really knows, but most people hope not. Answering “why did you choose to divide the problem into those particular 1,482 parts?” with “because they happen to fit together well enough to give us a proof” is profoundly unsatisfactory to anyone who believes that the steps in a mathematical proof must have some reason for having been chosen; or indeed to anyone who believes that truth and beauty go together in mathematics. Some years later another group did a Haken-and-Appel-type proof with only 633 parts instead of 1,482, but also with no reason other than “it seems to work”. There is a feeling that this cannot be the end of the story; but it will take a century or so before anyone comes back to the problem and tries to see how the story really ends.

Books about mathematics have a tendency to condescend to their readers, often exacerbated by publishers’ insistence that mathematical formulae should be avoided. Robin Wilson does not condescend, and the very few equations he shows us are simple, and necessary. The whole book is limpid, clear and enjoyable.

In Plato’s Meno Socrates talks a slave through the proof of a geometrical proposition without doing more than asking questions, and argues that this shows that knowledge is not something put into us from outside but something that is already in us and simply needs to be remembered. If Socrates was right, Wilson has shown us that the proof of the Four-Colour Theorem is also something that is already in every one of his readers, and that all he had to do was help us remember it.

But I bet he still wears fluorescent socks.