What Is The Four Color Map Theorem?

The four color map theorem states that the minimum number of colors needed to color any map is four. Four colors are always enough to color every region so that no two regions sharing a border have the same color, no matter how complex the map. It was proven in 1976 by Kenneth Appel and Wolfgang Haken using a computer.

Among the many theorems in mathematics, a few stand out from the rest. One such theorem is the four color map theorem, also called the four color theorem. The four color map theorem is exactly as it sounds: you only ever need four colors to color all the regions of any map so that no two regions sharing a border end up with the same color. The beauty of this theorem lies in the fact that it applies to all maps, regardless of their complexity or density of demarcations. Before we get into the nuances of understanding it, let’s briefly review the history of the theorem.

History

As far as credible sources go, the first proposal of such a conjecture was made by Francis Guthrie on October 23, 1852. The proposal occurred while trying to color the map of England, when it was noticed that only four different colors were needed. At the time, Guthrie’s brother was a student of the famous mathematician Augustus De Morgan at University College London.

The problem, which is so simple, proved itself to be tantalizingly difficult. In 1860, De Morgan publicized the problem in a note in the Athenaeum, which carried it across the Atlantic to the United States. There, Benjamin Peirce (1809-1880), a famous mathematician and astronomer, took it up 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.

First Attempt At A Concrete Proof

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 took particular interest in the problem, and in 1879 published a short paper on the coloring 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, ‘if a particular map is already successfully colored with four colors, and we add another area, can we still keep the same coloring?’, opened another line of inquiry that led to the application of mathematical induction to the problem.

Arthur Cayley was able to show that if four colors had already been used to color a map, and a new region was added, that it was not always possible to keep the original coloring. Above, all four colors have been used on the original map, and a new region is drawn to surround it. In this case, a red area is changed to blue so that that red can be used on the new surrounding region. Cayley was able to observe 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 colored with four colors, only three colors will appear on the border.

The Patch demonstration.

Imagine that at some place in a map, some countries meet at a point. Now, put a patch over the meeting point, and all the new meeting points will have three borders emanating from them. These are cubic maps, and a fourth color can be used for the central region. Upon removing the patch, we can return to the original coloring.

Understanding The Basics

In order to work on a more concrete proof for the four-color problem, we will need to build an understanding of certain terminologies, ideas and techniques that mathematicians have developed to solve it. The first concept is “Every country has five or fewer neighbors”. Now, to understand this statement, imagine a map of an island surrounded by a sea. In the coloring 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.

When False Becomes True

Another way to approach proving the four color problem is to assume that it is false from the onset, and see where it leads. Suppose there is a map that needs five or more colors and the map we have picked contains the smallest number of countries present in it. The name for such a map is known as the minimal counter example or even more interestingly, minimal criminals!

The above paragraph now implies that the minimal criminal cannot be colored with four colors. This implies that any map with fewer countries than the minimal criminal can be colored in four colors. So if we can prove that the minimal criminal does not exist, that leads to some substantial progress in the proof. The first thing we can state conclusively is that a minimal criminal cannot be a digon. From the original map, if one were to take away the boundaries of the digon, we get a new map with fewer countries. The resultant map can be colored with four colors from our assumption. When we color the map, we observe that we need only two colors.

Now, if we reinstate the border we removed and recolor the map, we observe that we have only used three colors so far, and still have one color in the reserve. We have used three colors, and since there is still one more color available, this shows that our map can be colored with four colors. 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 be using all four colors, so the proof procedure fails. Once this has happened, it becomes obvious that it won’t work for pentagons, and so on.

There are more substantial and rigorous methods one can use to prove the four color theorem, such as graph theory and so on. The first famous attempt at a full proof came in 1879, when Alfred Kempe published an argument that convinced mathematicians for over a decade. In 1890, however, Percy Heawood found a flaw in Kempe’s reasoning. Kempe’s work was not a total loss: Heawood salvaged enough of it to prove that five colors are always sufficient, but the four color question stayed stubbornly open.

The breakthrough finally arrived in 1976, when Kenneth Appel and Wolfgang Haken at the University of Illinois proved the theorem with the help of a computer. They reduced the infinity of possible maps to an unavoidable set of 1,834 configurations (later trimmed to 1,482) and then checked, by machine, that each one could be safely colored with four colors. It was the first major theorem ever proven using a computer, which sparked a long debate about whether a proof no human could check by hand should really count. In 1997, Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas published a simpler computer-assisted proof that trimmed the case analysis down to 633 configurations. Either way, the verdict stands: any map can be colored with only four colors!