# Graphs and NetworksMap Colouring

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

### South America

### Germany

### England

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

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 *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

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