A maths problem for the colouring in set

On a recent breakfast outing my five year old niece was handed an intricately designed paper place mat and four crayons to colour in the pattern.

“I think I’m going to need more colours,” she said. I know better than to argue with a five year old before 9 am and requested supplements. While she scribbled away with the extra crayons, I thought about Francis Guthrie.

In 1852, Francis wrote a letter to his brother Frederick containing a simple question about colouring maps. Francis had discovered he needed only four colours to colour a map of all of the counties in England so that no two adjacent counties shared the same colour. He asked his brother if he thought England was unique, or if the rule could apply to every map.

It was a seemingly simple question: in fact Francis was asking for a formal mathematical proof that remains unsolved by any human hand to this day.

Upon receiving the letter from his brother, Frederick asked one of the foremost mathematicians and logicians of the day, Augustus De Morgan, for help. De Morgan determined that certain simplified maps did not require more than four colours, but he was unable to demonstrate that this applied to all maps. The problem essentially languished unsolved for decades. Then at last in 1879 it looked like the problem was cracked. Alfred Kempe, a mathematician and barrister who went on to become president of the London Mathematical Society, published a proof.

Kempe’s proof stood for more than a decade, but could not stand interrogation by Percy Heawood, a mathematician who devoted nearly his entire life to the four-colour problem. Heawood discovered a flaw in Kempe’s analysis and alas, the four-colour problem arose once more. Although Heawood was able to disprove Kempe’s theorem, he could not find a new proof for the four-colour problem either. He was able to prove a five-colour theorem. But the quest for four did not die.

In the 1920s Philip Franklin narrowed the problem to maps containing 25 or fewer regions and was able to prove that no more than four colours are required. Like Kempe before him, Franklin’s work depended on reducing certain sections of the map that could easily be filled in using only three colours.

If the map that remained after removing this three-colour section could be filled in with four colours, then the original map could also be filled in with four colours. But it remained to be seen if all configurations could be so reduced.

Many mathematicians rejoiced at the ingenuity of using a computer to prove a mathematical theorem. But not everyone was impressed.

It would take another 50 years to get the answer. In 1976, Kenneth Appel and Wolfgang Haken developed a complete set of all possible irreducible configurations for the four-colour problem.

These configurations can be thought of as the basic building blocks of every possible map that can be drawn on a two-dimensional surface. If each one of these configurations could be checked to ensure that they could be filled with only four colours, then the theorem would be proved. The only problem? There were almost 2,000 irreducible configurations and checking them all by hand was impossible – for a human. Enter the computer.

Over almost two months, Appel and Haken eliminated configurations from the list with a computer. Eventually, after approximately 1,200 hours of non-stop computing, the job was complete and the four-colour theorem was proved at last. They published their work in a book-length paper entitled Every Planar Map is Four Colourable.

At the time many mathematicians rejoiced at their ingenuity in using a computer to prove a mathematical theorem. But not everyone was impressed. Although their results were not directly refuted per se, Appel and Haken’s proof was – and in some sense continues to be – controversial.

Many mathematicians consider such “brute force” attacks inelegant and unworthy of being called proofs. Appel and Haken themselves are even on record in a 1977 interview stating they knew of no proofs (including their own) that were “elegant and concise”.

Or course, tasking computers with the “heavy lifting” has gained wider acceptance in the intervening decades. Today, computers are considered indispensable in many areas of mathematics research. There have even been refinements to the four-colour theorem. But in the nearly 40 years since Appel and Haken’s work was first published their basic approach of using specialised software to check and eliminate every possible “map” is still being used.

In the meantime an elegant and concise solution to the four-colour problem is still up for grabs.

Maybe my niece, with her paper and crayons, will crack it.