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.

Topology

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).

 

{ 2 comments… read them below or add one }

Julius Mazzarella September 25, 2018 at 3:08 pm

Interesting article …using computers to compete proofs!

On the other hand the data at the LHC is reduced by computers making what I imagine to be very similar calculations and scientists take them to be correct at face on a daily basis.

Reply

Nicholas Mee September 27, 2018 at 2:01 pm

No one doubts the conclusion of the computer program and that is why it is a problem.

Mathematicians worship at the Temple of Rationality. If there are true statements whose proof cannot be understood by anyone, this threatens the whole enterprise of mathematics. Euclid’s Elements epitomises mathematics. It consists of rational proofs of simple propositions that are then used to prove ever more sophisticated results. What counts to a mathematician is not so much whether a particular statement is true, but how we know it to be true. Only by understanding why mathematical results are true is it possible to continue building the edifice of mathematics.

The problem of a statement that can be shown to be true, but whose proof cannot be understood reminds me of a simple result of Euclid’s known as the pons asinorum about the angles of an isosceles triangle. The proof is illustrated with a diagram that looks rather like a wooden medieval bridge, but the name alludes to the proof as a bridge to the rest of geometry. Anyone who could not understand the proof would be unable to cross the bridge and explore the wonders of mathematics.

Even if mathematical puzzles such as the Four Colour Problem do not keep us awake at night, there are philosophical issues that everyone wrestles with at one time or another. Imagine a computer that could definitively answer such questions, but we could never know why the answer was true. For instance, take a computer, rather like the one envisaged by Douglas Adams in The Hitchhikers Guide to the Galaxy. If such a computer could definitively determine whether or not God exists, but we could never understand how it reached its conclusion this would seriously threaten our status as rational beings. How would humanity respond? This is, of course, just a colourful analogy. I’m not suggesting that should a computer program is possible.

Reply

Leave a Comment

Previous post:

Next post: