## Countries, empires and lunar colonies

**By Jane Tan, Australian National University
**

Many readers may be familiar with the famous four-colour theorem. It runs thus: suppose we have a map divided into connected regions, each one being a different country, and we would like to colour these so that no two neighbouring countries have the same colour. One can find quite simple maps for which four colours are necessary to achieve this, but is four colours always enough? This question was asked in 1852, and it was not until 1976 that Appel and Haken proved, with computer assistance, that the answer is yes. At least, that’s the short version of the story.

It should not come as a surprise that a conjecture which evaded proof for so long did not do so quietly – many mathematicians made attempts in the intervening years, endowing it with quite an eventful history and creating a fascinating family of problems along the way. Notably, Kempe published a proof of the theorem in 1879. That settled the matter for about eleven years, after which time Heawood discovered that the argument was flawed. Not all was lost, however; Heawood was able to salvage enough ideas from it to give a tidy proof of the five-colour theorem, which is precisely the same result except that we allow the use of five colours instead of four.

At the same time, Heawood introduced the following problem. Say the countries on our map are united into *m*-pires (empires), each of which consists of *m* non-neighbouring countries where *m* is some fixed number. This time, we want to colour the map so that all countries in an empire are given the same colour, but as before any two neighbouring countries have different colours. For each *m*, what is the minimum number of colours that allows us to colour every map of *m*-pires in this way? When *m*=1, this is just the original problem and the answer was 4, though we have noted that the proof is very difficult. For larger *m*, it turns out that the answer is 2*m*. Heawood gave a splendidly simple argument to show that 2*m* colours is always sufficient, and Jackson and Ringel finished the proof in 1983 by exhibiting *m*-pire maps that require all 2*m* colours, thereby showing that we cannot do any better.

Ringel posed another variation in 1959. What if, sometime in the future, each country on Earth also had a colony on the moon and we want to simultaneously colour the maps of the Earth and the moon (together, an Earth-moon map) so that each country and its lunar colony is given the same colour, but on both maps any two neighbouring regions have different colours? This is closely related to the 2-pire problem, and in fact Heawood’s argument shows that 12 colours is still enough here. However, we don’t know that this is the *minimum* number of colours needed to guarantee that any Earth-moon map can be so coloured. In 1974, Sulanke found a map (pictured) requiring 9 colours, so the answer is 9, 10, 11, or 12. Which of these it is precisely is still an open problem.

- Gardner,
*Mathematical Games: The Coloring of Unusual Maps Leads Into Uncharted Territory*, Sci. Amer.**242**(1980), 14-21. - J. Heawood,
*Map Colour Theorem*, Quart. J. Math*.***24**(1890), 332-338. - Jackson and G. Ringel,
*Solution of the Heawood’s empire problem in the plane*, J. Reine. Angew. Math.**347**(1984), 146-153.