English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGraphs 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
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.
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.