Log in to Mathigon

Google
Create New Account

Reset Password     

Share

Change Language

EnglishVietnamese

Send us Feedback

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

Are you sure that you want to reset your progress, response and chat data for all sections in this course? This action cannot be undone.

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.

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

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.