One of maths' most elusive problems is easy to state but nearly impossible to prove: Are 4 colours enough to paint any map, so neighbouring countries have different colours?
Simon Singh's journey begins with the number 4, which for over a century has fuelled one of the most elusive problems in mathematics: is it true that any map can be painted with just 4 colours so that no two neighbouring countries have the same colour? This question has tested some of the most imaginative minds - including Lewis Carroll's - and the eventual solution has aided the design of some of the world's most complex air and road networks.
Most people's memories of geography at school will include two things. Firstly, there was learning by rote the groundnut crop yield figures for Senegal in the mid '70s, and secondly, there was colouring-in maps. Many hours were spent shading-in maps of Birmingham, scrounging around for different colour pens to distinguish Smethick from Oldbury. Now, a puzzle which owes more to maths than geography posits the question, how many different colour pens did you really need to pilfer from your mate's pencil-case in order to do Brum, so that no two adjacent suburbs had the same colour. Memories of youthful exuberance would suggest every pen in your pal's possession, but mathematically, the answer is 4.
The 4 colour map problem dates back to 1852 and Francis Guthrie, a student at University College London. He'd observed that every map drawn on paper could be filled in with just 4 colours so that no two neighbouring regions would be the same hue. Desperate for a proof, he sent word to the eminent mathematician Augustus De Morgan, who, unable to solve the problem himself, put out feelers to his peers.
The crux of the matter was that it wasn't enough to prove that hundreds or even billions of maps were 4-colourable. There could be just one map out there that wasn't. A proof was needed that could be applied to all maps.
This was seemingly supplied by Alfred Kempe in 1879. He argued that all maps came from a finite group, or 'unavoidable set', of 'simplified' maps that could be proved 4-colourable. Kempe's proof was warmly received by mathematicians who deemed the matter closed.
Then in 1890, Percy Heawood, a lecturer at Durham, discovered a flaw in Kempe's theory. When revised, it suggested that every map could be happily 5-coloured but not 4. The 4-colour problem was back, and this time it was personal.
For the best part of a century, it continued to tantalise the world of mathematics. Then in 1976, Americans Kenneth Appel and Wolfgang Haken postulated a ground-breaking theory, based on an elaboration of Kempe's work. They constructed an 'unavoidable set' with around 1500 4-colourable configurations that could be applied to any map. Their '4 Colour Theorem' got a mixed reception. It was the first major work of its kind to be proved using a computer, something that the old school mathematicians of the time found controversial.
Independent verification and the test of time have convinced most sceptics that Appel and Haken did crack it. But for some purists and mathematical romantics, the puzzle remains to come up with a non-computer solution to this very Victorian problem.
- Mon 27 Oct 2003 15:45