Copyright © University of Cambridge. All rights reserved.
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.
The conjecture that any map could be coloured using only four colours first appeared in a letter from Augustus De Morgan (18061871), first professor of mathematics at the new University College London, to his friend William Rowan Hamilton (18051865) 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).
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 (18091880) 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.
In 1878 Arthur Cayley (18211895) 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.
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.
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.
'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.
In 1813, Euler's formula for polyhedra was adapted for two dimensions by Augustin Cauchy (17591857) 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.
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!
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 counterexamples 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 recolour 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 threesided 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.
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!
In 1879 Alfred Kempe (18491922), 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 (18611955) showed there was an important error in the proofmethod that Kempe had used.
In 1880 P.G. Tait (18311901) 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 187677 Tait became wellknown 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 18241907) inspired by the experiments of the German Physicist Hermann von Helmholtz (18211894) 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 (18311879) 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 ]
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 fourcoloring of a map. It was not until 1946 that William Tutte (19172002) found the first counterexample to Tait's conjecture.
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 nonplanar 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 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. 
The Hunting of the Snark is a poem written by Lewis Carroll, and Martin Gardner named these graphs Snarks, because they were so elusive.
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 nontriangular 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 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 4coloring maps and by 1994, the unavoidable set of configurations had been reduced to 633.
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.
Use the notes tab at the top of this article or click here .
The very best popular, easy to read book on the Four Colour
Theorem is:
Wilson, R. (2003)
Four Colours Suffice
.
London. Penguin Books.
For a more detailed and technical history, the standard
reference book is:
Biggs, N.; Lloyd, E. & Wilson, R. (1986) (1998)
Graph Theory,
17361936
Oxford. Oxford University Press.
This one brings us up to date, with more recent foundations and
philosophy.
Fritsch, R and Fritsch, G (2000)
The Four Color Theorem: History,
Topological Foundations, and Idea of Proof
New York. SpringerVerlag.
Hardly any general history book has much on the subject, but the last chapter in Katz called 'Computers and Applications' has a section on Graph Theory, and the Four Colour Theorem is mentioned twice.
Polya G. How to Solve
It.
This is the classic book about Problem Solving. There have been
many editions of this book since it first appeared in the 1950s and
it is still easily available. Curiously, recent editions have been
given the subtitle 'A new aspect of Mathematical Method'.
Lakatos, I. (1976) Proofs and
Refutations: The Logic of Mathematical Discovery.
Cambridge. C.U.P.
This is another important book which led to the research into
Problem Solving and Investigations in the 1970s. It begins as a
classroom discussion between a teacher and a group of students
about the proof of Euler's formula, and ranges through the ideas,
objections and possibilities that were actually discussed by
mathematicians and scientists in the nineteenth century. It raises
some of the most important issues about teaching and learning
problem solving and about mathematical methods and proof.
I have had a little book on String Games for some time. When I was at school it was called Cat's Cradle, and we played it in our break time.
Recently, a French journal has published a paper on the 'algebra' of string figures! If you go to Amazon you will find a nice book by Ann Swain and Michael Taylor called Finger Strings: A Book of Cats Cradles and String Figures to be published by Floris books in September 2008. There are some 80 figures described with coloured diagrams. It's spiral bound, so it will stay open while you follow the instructions. It also comes with a couple of string loops!
For knot experts, The Ashley Book of Knots is a classic for anyone interested in the hundreds of different kinds of knots and their uses. Amazon has various editions available at different prices.
For a general overview and links to many people and topics, the
MacTutor website is
http://wwwhistory.mcs.stand.ac.uk/HistTopics/The_four_colour_theorem.html
And of course MacTutor biographies of those involved in developing all the different mathematical aspects can be found at the MacTutor Biographies Index.
The Four Colour Theorem and Three Proofs. For the mathematically persistent the following website has an intriguing new approach to attacking the problem of constructing a new algorithm for solving the problem, and tying to reduce the reliance on a computer. http://www.emu.edu.tr/~cahit/the%20four%20color%20theorem%20%20three%20proofs.htm
For Graph Theory, Wikipedia gives a good overview, and you can
skip the really technical stuff. It shows the kinds of modern
applications of this area of mathematics. If you go to Graph
Colouring and click on the Four Colour Theorem, then you will find
a lot more information.
http://en.wikipedia.org/wiki/Graph_theory
An interesting, and not too technical History of Knot Theory 
how an idea from Kelvin's Physics returns to Atomic Theory
today.
http://www.math.buffalo.edu/~menasco/Knottheory.html
The Association of Teachers of Mathematics have Celtic Knot
design posters. Go to their website and browse the alphabetical
list of resources.
http://www.atm.org.uk/
Find out all about Knots on the Knot Atlas! If you are not an
expert  just enjoy the variety and complexity of the database "in
the spirit of wiki"
http://katlas.math.toronto.edu/wiki/Main_Page
More artistic and colourful  but no less mathematical is the
Knot Plot Site.
http://www.knotplot.com
For those who want some of the original stuff and historical
detail go to the History of Knot Theory on:
http://www.maths.ed.ac.uk/~aar/knots/index.htm