Do five suffice?

Until yesterday Queen Griselda's empire had an annoying hole right in the middle of it, due to a kingdom of small, but remarkably resistant, dwarves. The hole stuck out like a sore thumb in the magnificent map painted on the wall above her throne. Yesterday, though, the Queen's army finally forced the dwarves into submission.

Triumphant though she is, she now has a new problem. The map above her throne is coloured with the five colours of her coat of arms: silver, gold, purple, blue and red. The kingdom of dwarves is surrounded by exactly five countries of her existing empire, and these five countries each use one of the five favourite colours. Obviously, she doesn't want neighbouring countries to have the same colour, and so far she has been able to avoid this. Will she now have to find a sixth colour for the new country, thus breaking the pleasing colour correspondence between her map and her coat of arms?

Wurzel the Wizard reassures her: it's possible, he says, to recolour the countries so that five colours suffice for the new map. Can you prove that he is right?

The solution

The problem becomes easier when you replace each country by a coloured dot, with a line connecting two dots if the corresponding countries are neighbours. The resulting object is called a graph, and we note that no two lines in the graph cross. Now look at dots representing the five countries that are neighbours of the new one, and label them by the numbers 1, 2, 3, 4, and 5, in cyclical order.

Now dot 1 and dot 3 are not adjacent, so let's see what could possibly stop us from recolouring dot 3 (which is, say, red) with the colour of dot 1 (blue). If we recolour dot 3 in blue, then we have to recolour all other blue dots that are connected to dot 3, for otherwise we break the rule that adjacent dots must have different colours. So let's recolour these other blue dots in red. This in turn will force us to recolour a third generation of dots, namely those that are red and connected to those dots we've just recoloured in red.

You can see that this recolouring will effect all dots that are either blue or red and that are connected to dot 3 by some path in our graph. If dot 1 is not one of these, then we are done: we simply swap the colours of those dots that are blue or red and connected to dot 3 by some path.

If dot 1 is connected to dot 3 by some path that passes through blue and red dots only, then we turn our attention to dots 2 and 4. By the same argument, the only thing that could stop us from repainting dot 4 (which is gold) in the colour of dot 2 (purple) would be a path from dot 2 to dot 4 that passes though purple and gold dots only. But because of the nature of our graph, such a path would have to cross the path from dot 1 to dot 3. Since no lines in our graph are allowed to cross, such a path cannot possibly exist. We can therefore paint dot 4 in purple, make the corresponding changes to the gold and purple dots that are connected to dot 4, and use the colour gold for the new country in the middle.

If you have solved this puzzle, then you have almost proved the five colour theorem. The theorem states that any two-dimensional map can be coloured using at most five colours so that no two neighbouring countries have the same colour. To prove this, you start by assuming that there are maps that use six colours and choose one with the smallest number of countries. Now this map clearly contains a country with at least five neighbours that together use up five colours (otherwise you wouldn't need six colours). It's possible to show that in fact that country has exactly five neighbours. If you remove that country, you get a smaller map which, by our assumption, can be coloured by five colours. Now you're in the situation of our puzzle: using the arguments from above, you can show that the map can be recoloured using just five colours. This is a contradiction, because we assumed that the map needed six colours, so our original assumption must be false. QED.

This does of course beg the question of whether we can reduce the necessary number of colours to four. The answer is yes, we can, but the proof is nowhere near as easy as the one for five colours. In fact, some would argue that no one has as yet found a proof, as the existing one relies on computers checking a vast number of possible configurations. No human could ever verify the computer calculations, so there is doubt as to whether the proof is valid. To find out more about the four colour theorem, read The philosophy of proof and Plus 100 — the best maths of the last century.