Článek z gauče

The map-colouring problem asks whether is it possible to colour any map (or any plane separated into regions) with just four different colours so that every two adjacent countries have different colours. Here we define two countries to be adjacent if they share a border, not just one point.

The problem was first stated by Francis Guthrie in 1852 and in 1879, a proof that it is always possible to colour a map with just four colours was presented by Alfred Kempe. In this proof, Kempe was assuming that more than four colours are needed for some maps. But if such maps existed then there would be at least one such map with the smallest number of countries. He showed in his proof that such a minimal map could not exist using two ideas – unavoidable sets and reducible configurations.

An unavoidable set is a set of countries or various configurations of countries and every map must contain at least one of the items from the set - this result follows from Euler’s formula. One example of such a set is a set containing a digon, a triangle, a square and a pentagon (or a region with two, three, four or five boundaries) – this set was used by Alfred Kempe in his proof. A reducible configuration is such an arrangement of countries that if the rest of the map can be coloured with just four colours than the entire map can be coloured with four colours. If there is such a reducible configuration in a map, the map cannot be the minimal counterexample.

Kempe showed that all the types of countries in the unavoidable set containing a digon, a triangle, a square and a pentagon are reducible and so any minimal map which needs five or more colours cannot contain any of these regions – which is a contradiction since the set is unavoidable. Eleven years later, it was shown by Percy Heawood that the proof was not correct because Kempe did not in fact prove that a pentagon was reducible.

The problem was finally solved using computers and a proof was presented in 1976 by two mathematicians, Kenneth Appel and Wolfgang Haken. They used the main ideas from Kempe’s proof and again were trying to prove that a minimal map which needs five or more colours cannot exist. To prove it, they had to construct an unavoidable set of reducible configurations.

Computers were used to find many reducible configurations and some properties were identified that helped to recognise whether a configuration was likely to be reducible. Then they used a method called the principle of discharging to look for unavoidable sets of configurations with such properties. They created a sophisticated computer program which allowed them to study many discharging procedures generating unavoidable sets in a reasonable time. At this point, unavoidable sets of configurations which were likely to be reducible could be found and even if the sets contained thousands of configurations their reducibility could be checked with the help of computers.

Finally, the procedures were used to generate configurations for the unavoidable set which were each immediately tested for reducibility and if the configuration wasn’t found reducible the procedure was modified. This process produced an unavoidable set of almost 2000 reducible configurations in June 1976.

The existence of the unavoidable set of reducible configurations proved that a minimal map needing five or more colours could not exist and so the map-colouring problem was finally solved.