A Cartographic Conundrum

by Nicholas Mee on September 10, 2018

In the Victorian era the British were fond of watching the pink of their empire spread outwards across maps of the world. A rather perceptive young student Francis Guthrie noticed something rather surprising while colouring the counties on a map of England. It seemed that no more than four colours were ever required to colour the regions on a map so that no border separated two regions of the same colour. Even when he drew maps with the most convoluted boundaries four colours were always enough. But he could find no explanation for why this was true. Guthrie later became Professor of Mathematics at the University of Cape Town. A four-colour map of the United States is shown here.

A four-coloured map of the United States.

Francis mentioned this cartographic conundrum to his brother Frederick who told Augustus de Morgan, Professor of Mathematics at University College, London. Francis’s simple observation is known as the four colour problem. It can be stated succinctly as:

Can every map be coloured with at most four colours, in such a way that neighbouring countries are coloured differently?

The oldest surviving account of the puzzle is in a letter of 23 October 1852 from de Morgan to the Irish mathematician Sir William Rowan Hamilton. The problem sounds so simple that we might expect it should be quite easy to prove. However, finding a water-tight proof turned out to be incredibly difficult. The four colour problem became notorious because on several occasions eminent mathematicians supplied ingenious proofs only for other mathematicians to shoot holes through them. The London barrister and amateur mathematician Alfred Bray Kemp published his proof in 1879 and it was believed correct for eleven years until Percy John Heawood found its flaws in 1890.


A Klein Bottle

If it were possible to prove the four colour problem on a sphere, this would automatically solve the problem on the plane, as a map on a sphere can always be projected onto a plane and vice versa.

But one curious feature of the problem is that it is much easier to determine the maximum number of colours for maps on other surfaces.

It might seem that any problem on a sphere or a plane must be much simpler than the equivalent problem on a surface as strange as a Klein bottle shown here, but not in this case. We know that six colours are required to colour every map on a Klein bottle.

The Torus

The torus, which is shaped like a car tyre, is another example. If we take a rectangular strip of paper and glue one pair of opposite edges we can form a cylinder. If we then bend the cylinder round and glue it two circular ends together we obtain a torus, as shown in the image on the right.

Heawood proved in 1890 that any map on a torus can be coloured with at most seven colours.

Another way to think of the torus is to consider it as a rectangle with opposite edges identified, which means that if an object, such as a line or even a spaceship, crosses the top edge of the rectangle it reappears across the bottom edge, just like in old video arcade games such as Asteroids.

We can use this idea to see a seven-colour map on a torus. The image below shows such a map on a square with opposite edges identified. The animation shows the torus that is produced by gluing the opposite edges of the square together.

A square with opposite edges identified representing a torus. This is a map on a torus that requires seven colours.

By the 1970s mathematicians had solved the problem on every surface apart from the sphere and plane.

A seven-coloured map on a torus.

Computer Aided Mathematics

About 120 years passed between the initial interest in the map-colouring problem and its eventual conquest. Kenneth Appel, Wolfgang Haken and John Koch finally demonstrated that four colours are sufficient, but their proof is one of the most controversial in the whole of mathematics. This is because only part of the proof was completed in the traditional fashion with pencil and paper. Appel and Haken actually showed that all maps can either be coloured with four colours or they are equivalent to almost two thousand ‘irreducible’ maps. They then turned the problem over to a computer. With the assistance of John Koch, they programmed the computer to check through these irreducible cases. On 21 June 1976 they announced the four colour problem had been solved. No one doubts the computer analysis shows the truth of the four colour theorem, but some mathematicians remain uncomfortable about a proof so unwieldy that a machine is required to scrutinize many more exceptional cases than a human could check. Following the original proof, the number of irreducible cases has been reduced, but the proof still requires a computer to test these cases.

Since Plato, many mathematicians have regarded themselves as intrepid explorers of an abstract realm of ideal mathematical objects. Computer aided proofs raise important philosophical questions about the nature of mathematical proof and challenge the status of pure mathematics.

Further Information

For more information about the four colour theorem, see Four Colours Suffice by Robin Wilson (Penguin 2002).


Previous post:

Next post: