Math Detours · Grade 6 · Around the corner · 25

Four colours are always enough

Grab four crayons. Whatever map anyone draws, you can colour it so no two neighbours match. Nobody could prove that for 124 years, and then a computer did.

Name ____________________Date ____________

Tonight's idea

Map-makers colour countries so that two countries sharing a border never get the same colour. In 1852 a student called Francis Guthrie noticed that four colours always seemed to be enough, however complicated the map. Proving it took 124 years. In 1976 Kenneth Appel and Wolfgang Haken reduced the Four Colour Theorem to 1,936 special cases and had a computer check every one.

There are two things to show. Four are sometimes needed: easy, here is a map where every region touches every other, so all four must differ.

1234
Regions 1, 2 and 3 all touch each other, and region 4 wraps around and touches all three. Four colours, no way round it.

Four are always enough is the part that took a century. It helps to redraw the map as a graph: a dot for each region, a line between dots whose regions share a border (the same trick as the bridges sheet). Then colouring the map is colouring the dots so that no line joins two dots of the same colour.

A sensible first method is greedy: go through the regions in some order, giving each the first colour not already used by a coloured neighbour. Greedy always finishes, but with a bad order it can waste colours. The four colour theorem says a colouring with four always exists, even when greedy misses it.

Watch one: greedy on a wheel

(Maps A and B are printed in questions 1 and 2.) Take a map with a central region surrounded by a ring of four others, like map A. Colour the centre red. Go round the ring: N cannot be red, so blue. E touches the centre and N, so green. S touches the centre and E, so blue is free again. W touches the centre, S and N, which used red, blue, blue, so green. Three colours.

Now a ring of five around a centre (map B). Centre red, then round the ring: blue, green, blue, green, and the fifth region touches the centre (red), the fourth (green) and the first (blue). Nothing left. You need a fourth colour. An odd ring around a centre always forces four, and an even ring never does.

Your turn

  1. Colour map A with as few colours as possible. Write the colour name in each region, or use crayons.
    NESWC
  2. Colour map B with as few colours as possible, and say why fewer is impossible.
    123456
  3. Draw a map of your own that needs four colours, different from the one in tonight's idea. Check every pair of regions you want to force apart really shares a border, not just a corner.
  4. Draw six straight lines right across a sheet of paper, any directions. Colour the regions with only two colours so neighbours differ. Then explain why two colours always work for any number of straight lines. (Hint: count how many lines you cross to reach each region from the edge. The parity sheet is relevant.)
  5. Draw the graph of map B: one dot per region, a line for each shared border. Write the degree (number of lines) at each dot. What is the total of all the degrees, and how is it related to the number of borders?

Stretch: doughnuts and five friends

Try to draw five regions that all touch each other on a flat page. You will fail. Explain what goes wrong when you try to add the fifth region to the four-region map from tonight's idea: where would it have to go to touch all of regions 1, 2, 3 and 4?

On the surface of a doughnut (a torus) things change. Regions can wrap around the hole and reach neighbours they could not reach on a flat page, and maps there can need up to seven colours. Why does the extra tunnel through the middle let regions touch in more ways?

Answers

  1. Three colours: C one colour, N and S a second, E and W a third. Two is impossible because C, N and E all touch each other.
  2. Four colours: 6 one colour, then 1 to 5 alternate between two colours, but with five regions the first and last clash, so one of them needs a fourth colour. Three cannot work because regions 6, 1 and 2 all touch, and the odd ring forces the fourth.
  3. Any drawing with four mutually bordering regions, for example a triangle split into three pieces meeting at the centre, with a fourth region drawn around the outside.
  4. Count the lines crossed to reach each region from outside the paper. Crossing one line into a neighbouring region changes that count by exactly one, so neighbours always have opposite parity. Colour even-count regions one colour and odd-count regions the other.
  5. Region 6 has degree 5; regions 1 to 5 each have degree 3 (the centre and two ring neighbours). Total 5 + 5 × 3 = 20, which is twice the number of borders (10), because each border is counted once from each side.

Stretch. In the four-region map, the fifth region would have to touch 1, 2 and 3, which are all inside the ring 4. Put it in the middle and regions 1, 2 and 3 wall it off from 4. Squeeze it in between the inner regions and the ring and it walls one inner region off from 4. Either way some pair stops touching, and it can be proved that every flat map fails like this. On a torus a region can go through the hole and come back round, so it can reach regions that were walled off on the flat page. The maximum there is seven, and a map that needs all seven exists.

← PreviousNext: Counting without double counting →