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?

If you are stumped by last issue's puzzle, here is the solution.

For some challenging mathematical puzzles, see the NRICH puzzles from this month or last month.