Will an old problem yield a new insight? Perhaps an elegant proof of the 4 colour theorem?

The 4 colour problem is one of the most famous mathematical problems. It resisted proof for more than a hundred years before finally succumbing; in the end, there was a valid proof, but one that relied on more than a thousand hours of computer time. Jim Tilley’s research suggests that a dramatic simplification might ultimately be possible. He has discovered a property, Kempe-locking, that a minimum counterexample to the 4 colour theorem must exhibit and has formulated a conjecture, based on extensive investigations, that the Birkhoff diamond is the sole fundamental Kempe-locking configuration.

Graph colouring involves assigning labels, or colours, to the vertices of a mathematical object known as a graph. The 4-colour problem provided one of the original motivations for the development of algebraic graph theory. Graph colouring is used in many real-world problems, such as minimising conflicts when scheduling sports events, planning examination timetables and organising seating plans, even for CCTV camera placement in a building with many corners in order to minimise camera overlap. It also provides the foundation for Sudoku puzzles.

The 4 colour problem

Francis Guthrie, a student of the famous British mathematician and logician Augustus De Morgan, posed the 4-colour problem in 1852. He formulated the problem with respect to maps that satisfy certain conditions, such as not containing any holes and having every region (e.g. country or state) connected so that no region exists in two or more non-contiguous parts. Guthrie claimed that for such maps it would never take more than four colours to colour the map such that no two neighbouring regions were the same colour.

Nowadays, the 4-colour problem is expressed in terms of graphs, and instead of colouring regions in maps, one colours vertices in graphs. All existing proofs of the 4 colour theorem demonstrate that a minimum counterexample cannot exist. (A minimum counterexample is the smallest planar graph that requires more than four colours for a proper colouring of its vertices.) Only planar graphs that are triangulations need to be considered, as any graph that is not a triangulation can be turned into one by inserting edges. If the resulting triangulation is 4-colourable, then the original graph is also 4-colourable. It is highly useful to be able to restrict one’s scrutiny to triangulations.

4 colour theorem: early proof

Of those who offered a proof, Alfred Bray Kempe, an English barrister and amateur mathematician, was the person whose reputation was most tainted by his failed effort. He announced his success in 1879 and his ‘proof’ was published in the American Journal of Mathematics. Eleven years later, however, another English mathematician, Percy Heawood, created a map that he 4-colored up to the final region in such a way that Kempe’s method failed for that final region. Despite his failure, Kempe left a useful tool – a Kempe chain. It is a maximal, connected (every vertex reachable from any other by a path along edges) subgraph in which all vertices use exactly two colours. Kempe chains have proven instrumental in colouring and re-colouring graphs. See Figure 1.

It would be an astounding simplification
if the Birkhoff diamond alone is the key to 4-colourability.

4 colour theorem: proof at last

The first valid proof was announced in 1976 by Kenneth Appel and Wolfgang Haken. It required over a thousand hours of computer time to verify particular aspects of their argument. This notion of relying on computer code, potentially containing human-induced errors (and their code did!), rather than a ‘human’ proof, has not satisfied a great part of the mathematical community. Appel and Haken’s proof was elegant in its overall structure, but the details were ugly.

The proof was refined in 1996 by a team of four mathematicians: Robertson, Sanders, Seymour, and Thomas, but they still relied on computer code to complete their proof. In 2010, Steinberger offered another variation. However, there is still no completely satisfying answer as to why the 4-colour theorem is true. (Once the conjecture was proved, it gained the status of a ‘theorem.’)

The search for an alternative proof

The 4-colour problem is so easy to articulate and comprehend that it has attracted the interest of many thousands of amateur mathematicians, all believing they can find a simple classical proof and thus become famous. Jim Tilley’s father, a physicist and principal of Canada’s Royal Military College from 1978-1984, was one such dreamer. Whenever he felt that he had made a breakthrough, he would ask his son, Jim, to check his work. Jim always found a flaw. Yet, despite his initial scepticism that his father’s efforts would ever bear fruit, he became infected with an enthusiasm for the 4-colour problem and began to study it intensely.

Kempe-locking

Jim Tilley’s research led to his discovering a new property that a minimum counterexample to the 4-colour theorem must exhibit. He named it ‘Kempe-locking.’ He realised that it was likely to be incompatible with another property that a minimum counterexample must exhibit – viz., how connected a graph is (how many vertices must be removed from a graph before it falls apart).

Tilley’s Kempe-locking is a property associated with an edge in a triangulation. The notion starts with deleting an edge xy between adjacent vertices x and y. If for every 4-colouring of the resulting graph in which the colours of x and y are the same, there is no sequence of colour-interchanges on Kempe chains that causes the colour of x to differ from the colour of y, then the original triangulation is said to be Kempe-locked with respect to the edge xy. Tilley proved that a minimum counterexample to the 4-colour theorem has to be Kempe-locked with respect to every one of its edges; every edge in a minimum counterexample must have this colouring property.

Kempe-locking is a particularly restrictive condition that becomes more difficult to satisfy as a triangulation gets larger. Tilley set out to discover if there is anything common to triangulations that have Kempe-locked edges. His earliest search for Kempe-locking led him to the Birkhoff diamond.

The Birkhoff diamond

In 1913, G. D. Birkhoff discovered that a certain configuration of ten countries in a map (a boundary ring of six countries that encloses a set of four countries) has an important property. If that configuration is present in a map and if the submap with that configuration removed is 4-colourable, then the entire map will be 4-colourable. Thus, a minimum counterexample cannot contain that particular configuration. It has come to be known as the Birkhoff diamond. Tilley found that a Kempe-locked edge xy seems to arise only when x and y are also the endpoints of the graph version of a Birkhoff diamond. See Figure 2.

The conjecture is easily stated, understandable, and intriguing, and offers a compelling explanation for why all planar graphs are 4-colourable.

Not having encountered any Kempe-locking configuration without a Birkhoff diamond, he conjectured that the Birkhoff diamond is the only ‘fundamental’ Kempe-locking configuration, one that doesn’t contain a smaller Kempe-locking configuration as a subgraph. However, Tilley found that he could not prove his critical conjecture. It was frustrating because, if true, the conjecture would directly prove the 4-colour theorem. (To be a minimum counterexample, a triangulation would have to contain a Birkhoff diamond subgraph, but if it did, it couldn’t be a minimum counterexample.)

An overwhelming supporting case

Instead of proving his conjecture, Tilley did the next best thing. He decided to play the role of an experimentalist and build an overwhelming case to support his conjecture. He divided all relevant planar triangulations into two classes: those in which at least four vertices have to be removed before the graphs fall apart (4-connected) and those in which at least five vertices have to be removed before the graphs fall apart (5-connected). See Figure 3. Helpful in Tilley’s extensive search was that he had to examine only one member of each isomorphism class (graphs that are structurally identical). Tilley examined all 8,044 isomorphism classes of 4-connected planar triangulations on up to 15 vertices and all 9,733 isomorphism classes of 5-connected planar triangulations on up to 24 vertices. He found only three Kempe-locked triangulations. Each discovered Kempe-locked edge featured a Birkhoff diamond and each occurred in a 4-connected triangulation. There were none at all among 5-connected triangulations.

Tilley expanded his search among 4-connected triangulations by examining all 30,926 isomorphism classes on 16 vertices and all 158,428 isomorphism classes on 17 vertices. Computation-time limitations meant restricting his search to samples of 100,000 randomly generated non-isomorphic triangulations each for classes on 18,19, and 20 vertices. The expanded search turned up 45 additional Kempe-locked triangulations, but exactly the same results as the original search: each Kempe-locked edge in a triangulation featured an associated Birkhoff diamond.

Where from here?

Tilley’s extensive searches easily confirmed that the Birkhoff diamond is a fundamental Kempe-locking configuration. He has thoroughly tested his conjecture, but it remains unproven. If (or when) Tilley’s conjecture is proved true, i.e., that the Birkhoff diamond alone is the key to 4-colourability, it would be an astounding simplification of the problem: a single configuration that explains it all – mathematical elegance.

Proving the 4-colour conjecture required the efforts of many prominent mathematicians. Tilley’s conjecture that the Birkhoff diamond is the sole fundamental Kempe-locking configuration may be even more difficult to prove. However, the experimental evidence is strong. Theorists might say ‘why bother?’ Tilley’s answer is that insatiable curiosity will win out: “After all, the conjecture is easily stated, understandable, and intriguing, and offers a compelling explanation for why all planar graphs are 4-colourable.”