The Four Colour Theorem

The Four Colour Conjecture was first stated just over 150 years ago, and finally proved conclusively in 1976. It is an outstanding example of how old ideas combine with new discoveries and techniques in different fields of mathematics to provide new approaches to a problem. It is also an example of how an apparently simple problem was thought to be 'solved' but then became more complex, and it is the first spectacular example where a computer was involved in proving a mathematical theorem.

1. In the Beginning

The conjecture that any map could be coloured using only four colours first appeared in a letter from Augustus De Morgan (1806-1871), first professor of mathematics at the new University College London, to his friend William Rowan Hamilton (1805-1865) the famous Irish mathematician in 1852. It had been suggested to De Morgan by one of his students, Frederik Guthrie, on behalf of his elder brother Francis (who later became professor of mathematics at the University of Cape Town).

Augustus De Morgan (1807-1871) and William Rowan Hamilton (1805-1865)

The problem, so simply described, but so tantalizingly difficult to prove, caught the imagination of many mathematicians at the time. In the late 1860s De Morgan even took the problem and his proof to America where among others, Benjamin Peirce (1809-1880) a famous mathematician and astronomer, became interested in it as a way to develop his logical methods.

De Morgan used the fact that in a map with four regions, each touching the other three, one of them is completely enclosed by the others. Since he could not find a way of proving this, he used it as an axiom , the basis of his proof.

A copy of De Morgan's original sketch in his letter to Hamilton and a simple four colour map.

In 1878 Arthur Cayley (1821-1895) at a meeting of the London Mathematical Society asked whether anyone had found a solution for De Morgan's original question, but although there had been some interest, no one had made any significant progress. Cayley became interested in the problem and in 1879 published a short paper On the colouring of maps where he explained some of the difficulties in attempting a proof and made some important contributions to the way the problem was approached. His question that, 'if a particular map is already successfully coloured with four colours, and we add another area, can we still keep the same colouring?' began another line of enquiry which led to the application of mathematical induction to the problem.

Arthur Cayley (1821-1895)

Cayley also observed that it was possible to solve a version of the problem by restricting the way the boundaries met. For example, maps where just three countries met have three edges meeting at a vertex. These are called 'cubic maps', and the maps used in the following discussion are all cubic maps. Also, if a map can be coloured with four colours, only three colours will appear on the border.

2. Some old techniques, new conditions and more problems!

In order to follow the developments of the problem, we need to investigate briefly some of the ideas, procedures and techniques that mathematicians developed in their attempts to solve it.

The Only Five Neighbours Conjecture [see note 1 below ]

'If you can't solve a particular problem, find an easier one that you can solve.' (Polya. How to Solve It )

'Every map has at least one country with five or fewer neighbours.'

Imagine a map of an island surrounded by the sea. In the colouring of the countries of the island, we count the sea as one region. Some countries may have only two borders (a digon), some three (as in a triangle), some four (a square) and some five (a pentagon) or more.

The simplest possible configurations for surrounding a central region.
Note that in all of these configurations each node has only three edges.

In 1813, Euler's formula for polyhedra was adapted for two dimensions by Augustin Cauchy (1759-1857) by projecting the polyhedron onto a plane thus forming the net of the solid. In this way the formula became $f + v - e = 1$, because Cauchy did not count the 'outside' region of the net.

Augustin Cauchy (1759-1857)

We can assume there are at least three border lines (edges) emerging from each meeting point (vertices).

So, from Euler's formula we get $3v$ edges in total. But, each edge has a vertex at the other end, and might be counted twice, so the total number of edges is at least $\frac{3}{2} v$. So $e \geq\frac{3}{2}v$ or, $v \leq \frac{2}{3}e$.

The proof that the map has at least one country surrounded by five or fewer neighbours proceeds by contradiction . If this leads to an absurdity, we have a proof.

Assume there is a map where every country ($f$) is surrounded by at least six neighbours. If we select one country, and count all the border lines ($e$) of the countries surrounding that one, we have six borders. This will occur for all the countries in the map, so the total number of borders will be $6f$ (where $f$ is the total number of countries in the map). However, each border line has been counted twice, so we need $\frac{6}{2}f$ which means $e \geq3f$ or $f \leq\frac{1}{3}e$.

Now put these values into Euler's formula: $$f + v - e = 2$$ and we have $$1/3(e) + 2/3(e) - e$$ which is zero!

This is the absurdity, so our original assumption was false. This means that there must be at least one country with five or fewer neighbours!

Minimal Criminals!

Another way to tackle the four colour problem is to assume it is false, and see where this leads. Suppose there are maps that need five colours or more, and we pick the maps with the smallest possible number of countries. These maps are called minimal counter-examples or minimal criminals !

So this means that a minimal criminal cannot be coloured with four colours, but any map with fewer countries can be coloured with four colours. If we can show that minimal criminals cannot exist, then we might be able to make some progress.

For example, we can show that a minimal criminal cannot contain a digon.

From the original map, take away a boundary from the digon, and we get a new map with fewer countries. This map can be coloured with four colours (from our assumption). We then colour this new map, (we only need two colours). Now replace the border we removed, and re-colour the map. We have used three colours, and since there is still one more colour available, this shows that our map can be coloured with four colours. But this is against our assumption, so a minimal criminal cannot contain a digon.

This procedure can be repeated to show that a minimal criminal cannot contain a three-sided country (a trigon), but it breaks down when we try the technique on a square, because when we replace the square, the countries next to it may well be using all four colours, so the proof procedure fails. Once this has happened, it becomes obvious it won't work for pentagons, and so on.

The Six Colour Theorem

A similar technique can be applied to show that the six colour theorem is true. First, we assume there are no maps that can be coloured with six colours. Some of the maps can be coloured with seven colours, so selecting one of these (a minimal criminal), if we can show that it is possible to colour it with less than seven colours, we have achieved our aim.

From the proof of the five neighbours theorem, it is possible to proceed using the minimal criminal idea to show that any map can be coloured with six colours!

3. From Regions to Knots, Networks and Topology

In 1879 Alfred Kempe (1849-1922), using techniques similar to those described above, started from the 'five neighbours property' and developed a procedure known as the method of 'Kempe Chains' to find a proof of the Four Colour Theorem. He published this proof in the American Journal of Mathematics. He found two simpler versions that were published in the next year, and his proof stood for ten years before Percy Heawood (1861-1955) showed there was an important error in the proof-method that Kempe had used.

Alfred Kempe (1849-1922), Peter Guthrie Tait (1831-1901) and Percy Heawood (1861-1955)

In 1880 P.G. Tait (1831-1901) a mathematical physicist, offered a solution to the problem. Independently, Tait had established that maps where an even number of boundary lines meet at every point, could be coloured with two colours, although this result had appeared earlier in Kempe's papers.

During 1876-77 Tait became well-known for his study and classification of knots. At that time there were a number of different theories about the structure of atoms. William Thompson (Later, Lord Kelvin 1824-1907) inspired by the experiments of the German Physicist Hermann von Helmholtz (1821-1894) proposed a theory that atoms were knotted tubes of ether. Kelvin's theory of 'vortex atoms' was taken seriously for about twenty years, and it inspired Tait to undertake a classification of knots. Tait, Thomson and James Clark Maxwell (1831-1879) invented many topological ideas during their studies. However, Kelvin's theory was fundamentally mistaken and physicists lost interest in Tait's work.[see note 2 below ]

Hermann von Helmholtz (1821-1879), Lord Kelvin (1824-1907) and James Clark Maxwell (1831-1879)

One of the outcomes of Tait's study was his Hamiltonian graph conjecture.

A map is regarded as a polyhedron drawn on a sphere, and it can then be projected onto a plane. Tait proposed that any cubic polyhedral map has a Hamiltonian cycle [see note 3 below ]. Tait's method focused on the edges of the graph and he showed that a Hamiltonian cycle could produce a four-coloring of a map. It was not until 1946 that William Tutte (1917-2002) found the first counterexample to Tait's conjecture.

Tait and the connection with knots

Tait initiated the study of snarks in 1880, when he proved that the four colour theorem was equivalent to the statement that no snark is planar. A planar graph is one that can be drawn in the plane with no edges crossing. It looks as if Tait's idea of non-planar graphs might have come from his study of knots and Hamiltonian paths .

The first known snark was the Petersen graph discovered in 1898, and mathematicians began to hunt for more of these kinds of graphs but it was not until 1946 that another snark was found.

Snarks are projections of three dimensional graphs onto the plane. There are no vertices where the blue edges appear to cross each other. Snarks have the following properties: The graph is cubic - three edges meet at every vertex. The graph is bridgeless - it is impossible to cut the graph into two separate pieces by deleting one edge. Using three colours, there is no proper edge colouring for the graph. All the edges meeting at a vertex cannot be coloured with three different colours.

The edges meeting the vertices of this snark are coloured blue, green and brown, but we always reach a stage where this process cannot be continued.

Julius Peterson (1839-1910)

The Hunting of the Snark is a poem written by Lewis Carroll, and Martin Gardner named these graphs Snarks, because they were so elusive.

4. Transforming the problem and finding new methods.

Although Heawood found the major flaw in Kempe's proof method in 1890, he was unable to go on to prove the four colour theorem, but he made a significant breakthrough and proved conclusively that all maps could be coloured with five colours.

Heawood made many important contributions to the problem, shifting the focus of attention from the areas of a map, to the borders between them. By 1898 he had proved that if the number of edges around each region is divisible by 3 then the regions could be coloured with four colours.

Cauchy's proof of Euler's formula also included the idea that any net of a polyhedron can be triangulated by adding edges to make non-triangular faces into triangles. He then developed a procedure whereby he deleted the edges one by one, showing that Euler's formula could be maintained at each step.[see note 4 below ]

Cauchy's Proof of Euler's Formula

Cauchy's 1813 proof of Euler's Formula began with the idea of a projection of a polyhedron to obtain a plane net. He further demonstrated (a) that any net could be triangulated, and his proof (b) of Euler's Formula was accepted at the time.

(a)	In principle, every polygonal net can be triangulated. In this net of a cube (a), $f + v - e$ is $10 + 8 - 17 = 1$, and Euler's formula still holds.
(b)	Cauchy's argument was to remove the external edges from diagram (a) one by one, and when he reached a stage as in diagram (b) removed the whole triangle T, thus preserving Euler's formula. Many mathematicians of the early nineteenth century agreed that this procedure demonstrated a proof of Euler's formula for all polyhedra.

By 1900, mathematicians knew that a planar graph can be constructed from any map using the powerful concept of duality [see note 5 below ]. In the dual, the regions are represented by vertices and two vertices are joined by an edge if the regions are adjacent. In these graphs, the Four Colour Conjecture now asks if the vertices of the graph can be coloured with 4 colours so that no two adjacent vertices are the same colour.

During the first half of the twentieth century, mathematicians focused on modifying these kinds of techniques to reduce complicated maps to special cases which could be identified and classified, to investigate their particular properties and developed the idea of a minimal set of map configurations that could be tested.

In the first instance, the set was thought to contain nearly 9,000 members which was an enormous task, and so the mathematicians turned to computer techniques to write algorithms that could do the testing for them. The algorithms used modified versions of Kempe's original idea of chains together with other techniques to reduce the number of members of the minimal set.

After collaborating with John Koch on the problem of reducibility, in 1976 at the University of Illinois, Kenneth Appel and Wolfgang Haken eventually reduced the testing problem to an unavoidable set with 1,936 configurations, and a complete solution to the Four Colour Conjecture was achieved. This problem of checking the reducibility of the maps one by one was double checked with different programs and different computers. Their proof showed that at least one map with the smallest possible number of regions requiring five colours cannot exist.

Since the first proof, more efficient algorithms have been found for 4-coloring maps and by 1994, the unavoidable set of configurations had been reduced to 633.

Is a 'Proof' Done on a Computer a Proper Proof?

Because the proof was done with the aid of a computer, there was an immediate outcry. Many mathematicians and philosophers claimed that the proof was not legitimate. Some said that proofs should only be 'proved' by people, not machines, while others, of a more practical mind questioned the reliability of both the algorithms and the ability of the machines to carry them out without error. However, many of the proofs written by mathematicians have been found to be faulty, so the argument about reliability seems empty. Whatever the opinions expressed, the situation produced a serious discussion about the nature of proof which still continues today.

For pedagogical notes:

Use the notes tab at the top of this article or click here .