???
Well done!
Archie

## Glossary

Select one of the keywords on the left…

# Graphs and NetworksMap Colouring

Reveal All Steps

We have already used graph theory with certain maps. As we zoom out, individual roads and bridges disappear and instead we see the outline of entire countries.

When colouring a map – or any other drawing consisting of distinct regions – adjacent countries cannot have the same colour. We might also want to use as few different colours as possible.

Some simple “maps”, like a chessboard, only need two colours (black and white), but most complex maps need more.

When colouring the map of US states, 50 colours are obviously enough, but far fewer are necessary. Try colouring the maps below with as few colours as possible:

### United States

Number of colours: 0

### South America

Number of colours: 0

### Germany

Number of colours: 0

### England

Number of colours: 0

All of these maps can be coloured with only four different colours, but it is not hard to imagine that other, very complicated maps might need many more colours. In fact, some maps need at least four colours, whenever they contain four countries all connected to each other.

Like before, we can convert a map with countries and borders into a planar graph: every country becomes a vertexan edgea face, and countries which share a borderhave the same colour get connected by an edge:

Now we want to colour the vertices of a graph, and two vertices must have a different colour if they are connected by an edge.

In 1852, the botany student Francis Guthrie had to colour a map of counties in England. He observed that four colours seemed to suffice for any map he tried, but he was not able to find a proof that worked for all maps. This turned out to be an extremely difficult problem, and became known as the four colour theorem.

During the following 100 years, many mathematicians published “proofs” to the four colour theorem, only for mistakes to be found later. Some of these invalid proofs were so convincing that it took more than 10 years to discover errors.

For a long time, mathematicians were unable to either prove that four colours are enough, or to find a map that needed more than four colours.

Little progress was made on the four colour problem until 1976, when Wolfgang Haken and Kenneth Appel used a computer to finally solve it. They reduced infinitely many possible maps to 1936 special cases, which were each checked by a computer taking over 1000 hours in total.

The four colour theorem is the first well-known mathematical theorem to be proven using a computer, something that has become much more common and less controversial since. Faster computers and a more efficient algorithm mean that today you can solve the four colour theorem on a laptop in just a few hours.

The four colour theorem only works for maps on a flat plane or a sphere, and where all countries consist of a single area.

However mathematicians have also looked at maps of empires, where countries can consist of multiple disconnected components, and at maps on differently-shaped planets, such as a torus (doughnut shape). In these cases you may need more than four colours and the proofs become even more difficult.

This map on a torus requires seven colours.