Maps often use different colours for neighbouring regions so that their borders are easy to see.
But how many colours do you really need?
How many colours do you need?
Colour the five regions so that any two regions sharing a side have different colours.
First choose a colour, then click a region.
💡
In this lesson, we’ll turn map colouring into a graph problem — and meet one of the most famous theorems in mathematics.
Turn the map into a graph
What happens if we forget the shapes of countries and remember only which countries are neighbours?
We’ll use the 27 countries of the European Union. Two countries will be connected if they share a land border on the European map shown here.
💡
The European Union becomes a graph
Start with the map of the 27 EU countries.
Map boundaries: Natural Earth. Overseas territories are not included in the neighbour relationships used here.
What is a proper colouring?
We’ve been colouring maps by making sure neighbouring regions have different colours.
On a graph, the same rule applies to vertices joined by an edge.
The EU example showed us two separate ideas. Let’s give them their mathematical names.
Proper colouring
A proper colouring of a graph gives colours to the vertices so that two vertices joined by an edge never have the same colour.
Every pair of connected vertices has different colours.
The two pink vertices are joined by an edge.
Chromatic number
The chromatic number of a graph is the smallest number of colours needed for a proper colouring.
Colour the Northeast USA
This graph represents nine states in the northeast of the USA. Two vertices are joined when the states share a land border.
💡
Click any state to choose your starting vertex. Then choose one of the four colours. Continue until every state is coloured.
Practice
For each graph, find its chromatic number: the smallest number of colours needed for a proper colouring.
A square
What is the smallest number of colours you need?
Add one diagonal
Now one extra edge has been added. What is the chromatic number?
Can three colours possibly work?
Every vertex in this graph is joined to every other vertex.
The Four Colour Theorem
Something remarkable happens here.
The Four Colour Theorem
Every flat map can be coloured using at most four colours, so that any two regions sharing a border have different colours.
The statement is wonderfully simple, but proving it turned out to be extremely difficult.
Mathematicians worked on the problem for more than a century. In 1976, Kenneth Appel and Wolfgang Haken produced the first accepted proof, using extensive computer calculations.
Can you invent a map that really needs four colours?
We know that four colours are always enough. But can you draw your own map for which three colours are not enough?
Your challenge: create four regions arranged so that every region is a neighbour of each of the other three.
What have we learned?
A map can be turned into a graph by making each region a vertex and joining neighbouring regions.
Map colouring then becomes vertex colouring.
Some graphs need only two colours. Some need three. Some maps genuinely need four.
But every ordinary flat map can always be coloured with at most four colours.
In the next lesson, we’ll use graphs for a very different problem:
How do we find the shortest route through a network?
Come back to it later
When you learn something new, it is important to come back to it later. Revisiting an idea after some time has passed helps you discover what you remember, what needs another look, and often makes the idea clearer the second time around. Our handouts are a perfect excuse to do exactly that.
Printable Graphs course
Prefer paper, a tablet, or studying offline? Open the printable version of the whole Graphs course, including this lesson.
Open printable PDF →Additional practice
Extra problems and investigations for this lesson are being prepared. Come back later for another chance to practise the ideas.
What did you think?
Whether you explored this together or worked independently, we would love to hear from both learners and parents. Tell us what you enjoyed, what was confusing, or what you would like to see next.
Share your feedback
The form is short and you do not need to give your name.