The Four-Color Theorem 1852–1976

History

The Four-Color Theorem 1852–1976 Robin Wilson Communicated by Notices Associate Editor Adrian C. Rice

The four-color problem asks whether the regions of every map drawn on a plane or sphere can be colored with just four colors in such a way that any two regions sharing a common boundary line receive different colors. First posed by Francis Guthrie in 1852, it was eventually answered in 1976 by Kenneth Appel and Wolfgang Haken, when it became known as the four-color theorem. To mark its 50th anniversary, this article recounts the story of the proof, focusing particularly on the individuals involved.

1 . Augustus De Morgan Figure 1 . Augustus De Morgan (1806–1871). Augustus De Morgan was the first professor of mathematics at the newly founded University College in London. Widely known for his contributions to mathematics, logic, and philosophy, he is remembered for “De Morgan’s laws” in set theory. He was also a prolific writer of mathematics for the general public, and his Budget of Paradoxes, compiled from his voluminous writings in The Athenaeum, a literary and scientific publication of the time, appeared in 1872. In 1865 he became the first president of the London Mathematical Society. For many years De Morgan enjoyed a correspondence with the Irish mathematician Sir William Rowan Hamilton, sharing their news, mathematical gossip, and family information. On October 23, 1852, he wrote to Hamilton saying: A student of mine asked me today to give him a reason for a fact which I did not know was a fact—and do not yet. He says that if a figure be anyhow divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured—four colours may be wanted, but not more…Query cannot a necessity for five or more be invented … As an example of a map where four colors are required, De Morgan drew four mutually neighboring regions. It later transpired that the “student of mine” was Frederick Guthrie, subsequently a physicist and the founder of the Physical Society of London. In 1880 he wrote a note for the Proceedings of Edinburgh’s Royal Society, crediting the problem to his older brother Francis, a former student of De Morgan’s, who was coloring a map of England and had asked whether four colors are sufficient for all maps. Francis Guthrie eventually became a professor of mathematics in South Africa and an acknowledged expert on botany; several plants are named after him, including the heather Erica Guthriei. Even though he never considered it further, the four-color problem is still sometimes called “Guthrie’s problem.” Figure 2 . Francis Guthrie (1831–1899). The four-color problem has also been wrongly credited to the German mathematician and astronomer August Möbius, who in 1840 set his students a problem about a dying king who bequeathed his land to his five sons on the condition that they divided it into five parts with each part bordering the other four. Such a partition into five mutually neighboring regions in the plane would have produced a map requiring five colors, but a proof of its nonexistence does not prove the four-color theorem—a misunderstanding that has arisen several times throughout the problem’s history. De Morgan was fascinated by the challenge and asked his friends and colleagues whether its solution was known, but no answer was forthcoming. From the start, he mistakenly believed that a proof would depend crucially on the observation that if a map includes four mutually neighboring regions, then one of them must be enclosed by the other three. On mentioning this to Hamilton, inventor of the algebraic system known as quaternions, he received the curt but appropriate reply, “I am not likely to attempt your ‘quaternion of colours’ very soon.” The earliest known printed description of the four-color problem appeared in 1854, when a paragraph headed “Tinting Maps” featured in the columns of The Athenaeum. Signed “F. G.”, it may have been sent by Frederick or Francis Guthrie, or possibly by the geographer and polymath Francis Galton who was then seeking admittance to London’s Athenaeum club. A later mention in the same periodical appeared in 1860 in an unsigned book review written by De Morgan, and as a result of his note the four-color problem reached America, coming to the attention of Charles Sanders Peirce; later a distinguished logician and philosopher, he was then studying at Harvard University where his father, Benjamin Peirce, was the most distinguished American mathematician of his time. The young Charles presented a solution to Harvard’s mathematical society, but it is not known what form this took.

2 . Arthur Cayley De Morgan died in 1871, unaware of whether the four-color theorem was true, and the problem seemed to have died with him. But it resurfaced seven years later at a meeting of the London Mathematical Society, when it was raised by the Cambridge mathematician Arthur Cayley. Figure 3 . Arthur Cayley (1821–1895). Arthur Cayley was born in London, but spent his earliest years in Russia where his father was a merchant trader. On returning to England he was schooled in London, before attending Trinity College, Cambridge, at the age of 17. After graduating with distinction in 1840, he was appointed a Fellow of the College, but being required to take Holy Orders of the Church of England he left Cambridge in 1844 to work for 19 years as a successful lawyer in London’s Inns of Court. During his time there he wrote over 300 mathematical papers and met his friend and collaborator James Joseph Sylvester, with whom he developed the new algebraic topic of invariant theory. In 1863 he returned to Cambridge as the first Sadleirian professor of pure mathematics, a position that he would occupy for the rest of his life. Following De Morgan, Sylvester and Cayley became successive presidents of the London Mathematical Society. In the 1870s Cayley became involved with the enumeration of chemical molecules, while Sylvester explored supposed connections between molecules and algebraic invariants, leading to his introduction of the word “graph” (in the sense of graph theory) in 1878. In 1875 Sylvester, who had retired from the Royal Military Academy in Woolwich five years earlier, was appointed the first professor of mathematics at the newly created Johns Hopkins University in Baltimore. While there he built up a research school of mathematics and helped to found the American Journal of Mathematics; this contained articles by upcoming American mathematicians as well as by established European ones. On June 13, 1878, Cayley attended a meeting of the London Mathematical Society, where he queried whether the problem of coloring maps with four colors had been solved. He soon developed an interest in the problem and, invited by his friend Francis Galton, he wrote a short note for the Royal Geographical Society’s Proceedings entitled “On the colouring of maps.” In this note Cayley admitted that he was unable to find a proof, and tried to explain where the difficulty might lie. More usefully, he explained how the general problem is easily reduced to the case of cubic maps—those with exactly three regions at each meeting point. For wherever more than three regions meet, we can stick a “patch” over that point, leading to a cubic map (see Figure 4). If this map can be colored with four colors, we can then shrink every patch to a point to produce a coloring of the original map. This was an important advance: from then on, map-colorers could restrict their attention to cubic maps alone. Figure 4 . The four-color problem for cubic maps.

3 . Alfred Kempe Figure 5 . Alfred Kempe (1849–1922). One of the people attending the June 13 meeting was Alfred Bray Kempe, a barrister and former mathematics student of Cayley’s at Trinity College. Kempe believed that he could prove the four-color theorem, and after working on it for a few months he produced a paper 9 which, at the invitation of Sylvester as editor-in-chief, he submitted to the American Journal of Mathematics, where it duly appeared. He also sent a preview of it to the science journal Nature. In his paper Kempe showed that every cubic map must contain at least one region with at most five boundary edges—that is, a digon, triangle, square, or pentagon. To see why, we use Euler’s polyhedron formula, which implies that $N - E + R = 2$ for any plane map with $R$ regions, $E$ edges, and $N$ meeting points of regions. If $c_{k}$ is the number of regions with $k$ edges, then $3N = 2E$ (because each edge connects two points), and so $$\begin{gather*} R = c_{2} + c_{3} + c_{4} + c_{5} + c_{6} + c_{7} + c_{8} + \dots \, , \\ 2E = 3N = 2c_{2} + 3c_{3} + 4c_{4} + 5c_{5} + 6c_{6} + 7c_{7} + 8c_{8} + \dots \, . \end{gather*}$$ Substituting these expressions into Euler’s formula yields the counting formula $$\begin{equation*} 4c_2 + 3c_3 + 2c_4 + c_5 - c_7 - 2c_8 - \dots = 12. \end{equation*}$$ So if there were no regions with at most five boundary edges, the left-hand side would be negative and we would have a contradiction. If the map contains a digon or triangle, then a proof by induction is immediate: we simply color the rest of the map, and there is then a spare color to color it. But if the map contains a square , $S$ it may be surrounded by regions of all four colors (say, red, blue, green, and yellow, in that order). To deal with this case, Kempe produced an effective argument involving interchanges of color, later known as the method of Kempe chains. Figure 6 . The method of Kempe chains. Kempe looked at the red–green parts of the map adjacent to $S$ (see Figure 6). If these do not link up, then interchanging the reds and greens in one part leaves a spare color for . $S$ But if they are linked by a red–green chain of regions, then interchanging the reds and greens does not improve the situation. But in this case, the blue–yellow parts adjacent to $S$ are separated by the red–green chain, and so the blues and yellows in one part can be interchanged, again leaving a spare color for . $S$ So in either case the square $S$ can be colored, and again the result follows by induction. Kempe then turned to the remaining case where the map contains a pentagon . $P$ If the rest of the map has been colored, and if $P$ is surrounded by all four colors with one color appearing twice, then carrying out two color interchanges will remove both appearances of that color. There would then be a spare color for , $P$ and the proof would be complete. This seemed to deal with all possible cases but, as we shall discover, Kempe’s last step was flawed, and his argument would come to be recognized as one of the best-known fallacious proofs of all time. More profitably, Kempe also introduced another idea. Any coloring of the regions of a map produces a coloring of their capital cities (see Figure 7). If we then join the capitals in every pair of neighboring regions, we obtain what Kempe called a linkage. The four-color problem then becomes one of coloring these capitals with four colors so that any two linked capitals receive different colors. As we shall see, this dual version of the problem, with colorings of the regions of a map replaced by colorings of the vertices of a planar graph, would later become the standard formulation. Figure 7 . Coloring linkages. When Kempe submitted his proof, Sylvester was out of town during a summer visit to England, and the paper was processed by his Johns Hopkins colleague William Story, the Journal’s cofounder and associate editor. While failing to spot Kempe’s main error, Story saw how to fill some minor gaps in Kempe’s arguments, and he wrote a short “Note on the preceding paper” to follow Kempe’s proof. Story’s fascination with the four-color problem continued for many years, and after Kempe’s error was discovered he corresponded with C. S. Peirce on the matter. In the meantime, Alfred Kempe had written several notable papers on the geometrical properties of mechanical linkages, and for these, and for his supposed solution to the four-color problem, he was elected in 1881 to a Fellowship of the Royal Society of London. He later became the Society’s treasurer, and in this role he funded an important expedition to Antarctica where the Kempe glacier and Mount Kempe would later be named after him.

4 . Peter Guthrie Tait Kempe’s “proof” was widely accepted as a solution to the four-color problem. But in Scotland the mathematical physicist Peter Guthrie Tait published a note in the Royal Society of Edinburgh’s Proceedings for 1880, criticizing Kempe’s argument for being unnecessarily complicated and showing little insight into the problem. In response, Tait produced some shorter and simpler proofs, all of which were deficient. Figure 8 . Peter Guthrie Tait (1831–1901). Later in the same year, Tait presented a more constructive idea when he showed that coloring the regions of a cubic map with four colors is equivalent to coloring its boundary edges with just three colors in such a way that the three edges at each meeting point are colored differently (see Figure 9). He believed this alternative formulation to be much easier to prove than the original version. Although he was mistaken in this, the subject of edge-colorings would later become an important topic for research. Figure 9 . Tait’s reformulation. With Kempe’s proof assumed to be the last word on the subject, other mathematicians became interested in the problem. The Oxford mathematics lecturer Charles L. Dodgson (better known as Lewis Carroll, author of Alice’s Adventures in Wonderland) cast it as a game for two players. And in Clifton College, a private school near Bristol, the headmaster, perhaps recalling Tait’s short “proofs,” proposed it as a challenge problem for the school, where “No solution may exceed one page, 30 lines of manuscript, and one page of diagrams.” He also sent it to the Journal of Education for its readers to attempt. One reader who did so was Frederick Temple, Bishop of London, a former mathematics lecturer at Oxford University and later Archbishop of Canterbury, who found a solution while his mind wandered during a tedious meeting. But all he had done was to prove that in the plane five neighboring regions cannot exist, which (as we noted earlier) does not prove the result.

5 . Percy Heawood In 1890, a groundbreaking paper entitled “Map-colour theorem” 10 appeared which would throw open the question for a further 86 years. Its author was Percy John Heawood, who had learned about the four-color problem while studying mathematics at Oxford University. After his Oxford degree, he moved to the Durham Colleges (later the University of Durham), where he spent the rest of his life. A well-loved but somewhat eccentric figure, he set his watch just once a year on Christmas Day and considered a day as wasted if he failed to attend at least one committee meeting. Figure 10 . Percy Heawood (1861–1955). Having been fascinated by the four-color problem since his Oxford days, Heawood was surprised to discover a fundamental flaw in Kempe’s attempted proof. In his paper he pointed out that, when dealing with the pentagon, Kempe had assumed that one could carry out two simultaneous interchanges of color, but Heawood presented a specific example in which this cannot be done. In his example (see Figure 11), where the uncolored pentagon is in the center, one can carry out a red–green color interchange above the pentagon, or a red–yellow color interchange below the pentagon, but if both are done simultaneously then the green and yellow regions on the right of the figure both become red, which is forbidden. Figure 11 . Heawood’s example. Fortunately, Heawood was able to rescue the situation to some extent by adapting Kempe’s argument to prove that every map can be colored with five colors—itself a significant result. A related problem which Heawood also discussed was the empire problem, where each country has a satellite region that must receive the same color as its mother country. He proved that all such cubic maps can be colored with twelve colors and “obtained with great difficulty” a specific example that requires all twelve (see Figure 12). Note that every two-part empire is adjacent to all the others. Figure 12 . The empire problem. Next, after observing that drawing maps on a plane is equivalent to drawing them on a sphere, Heawood investigated the number of colors needed for cubic maps drawn on other orientable surfaces, such as the sphere $S(g)$ with $g$ added handles. For example, every map on the torus $S(1)$ can be colored with seven colors, and Heawood presented a torus map that uses all seven colors. But Heawood also made mistakes. For a cubic map with $R$ regions, $E$ edges, and $N$ points on the surface , $S(g)$ Euler’s formula tells us that . $N - E + R = 2 - 2g$ From this result Heawood deduced that its regions can be colored with $\left\lfloor {\ \frac{1}{2}}\left( 7 + \sqrt {48g + 1}\ \right) \right\rfloor$ colors, but for all $g > 1$ he failed to prove that there are maps that actually need this number of colors, an assertion that became known as the Heawood conjecture. It was not proved in its entirety until 1968 (see 2 and 3 ). In 1898, Heawood wrote a second paper in which he recast the four-color problem in terms of numerical congruences. He first showed that Tait’s coloring of the edges of a cubic map corresponds to assigning the numbers $1$ and $-1$ to the meeting points so that the sum of the numbers around each region is a multiple of $3$ (see Figure 13). Moreover, if the points are labeled , $p_{1}, p_{2}, \dots , p_n$ then for each region there is a congruence mod $z_{i} + z_{j} + \dots + z_{k} \equiv 0 \ ($ , $3)$ where each $z_{i}$ is $1$ or $-1$ and $z_{i}$ appears in the congruence whenever the point $p_{i}$ lies on an edge of that region. Figure 13 . Heawood’s labeling of the points of a cubic map. In his lifelong search for a proof of the four-color theorem, Heawood continued to explore his congruences, concluding with a paper that was published in his 90th year.

6 . Paul Wernicke Following Heawood’s revelation, Kempe attempted to correct his proof, but without success. Some mathematicians even expressed doubts as to whether the result was true, with the Danish mathematician Julius Petersen remarking I know nothing with certainty, but if it came to a wager I would maintain that the theorem of the four colors is not correct. Also, around that time the German mathematician Hermann Minkowki was lecturing on analysis situs (topology) at the University of Göttingen. Claiming that failures to prove the four-color theorem arose because only third-rate mathematicians had attempted the task, he boasted to his students that he could find a proof. Several weeks of lectures then followed as he tried without success, finally admitting that he too had failed. The first new idea of the 20th century was due to Paul Wernicke. Born in Germany in 1866, he had taken a degree in mathematics before migrating to the United States in 1893 and becoming an American citizen. He gained employment teaching modern languages in Kentucky, but was mainly interested in mathematics and went back to Germany to write a doctoral thesis on analysis situs before returning to the US. Wernicke had long been interested in the four-color problem. While in Germany he wrote a significant paper for the Mathematische Annalen in which he proved that any cubic map with no digons, triangles, or squares must contain, not just a pentagon, but two adjacent pentagons or a pentagon next to a hexagon (see Figure 14). His hope was that these last two configurations would be easier to investigate than the simple pentagon had been. Figure 14 . Wernicke’s unavoidable set. Figure 15 . A configuration with ring-size 14. Arising from this came the fundamental idea of an unavoidable set of configurations in a map. A configuration with ring-size k consists of one or more regions surrounded by a ring of $k$ other regions, as in Figure 15, and a set of configurations is unavoidable if every cubic map must contain at least one of them. This concept, originating with Kempe and developed by Wernicke, would prove to be crucial in later attempts on the four-color problem.

7 . Oswald Veblen 1912 was an important year for the four-color problem, with two significant papers by Americans appearing in the Annals of Mathematics. These papers, by Oswald Veblen and George Birkhoff, together with a groundbreaking paper of Birkhoff in the following year, initiated a new period of progress on the four-color problem. Figure 16 . Oswald Veblen (1880–1960). Oswald Veblen was born in Iowa and received his education at the University of Iowa (which he entered at age 14) and at Harvard University. He then transferred to the University of Chicago, where he earned his doctorate for a thesis on geometry, the area of mathematics for which he is best remembered. From 1905 to 1932 he taught at Princeton University, before becoming the first professor of mathematics at the new Institute of Advanced Study. In his paper on “An application of modular equations in analytic situs” Veblen used ideas from geometry and algebra to situate the four-color problem. He began by introducing two matrices to specify maps with given labelings of the vertices (meeting points), boundary edges, and regions: these were the vertex–edge incidence matrix $A$ whose - $(i, j)$entry is $1$ if vertex $i$ lies on edge , $j$ and $0$ otherwise, and the edge–region incidence matrix B whose - $(i, j)$entry is $1$ if edge $i$ borders region , $j$ and $0$ otherwise. Each of these matrices leads to two sets of linear equations; for example, for matrix $B$ the variables in the equations represent the regions of the map, and each edge corresponds to an equation of the form , $y_{a} + y_{b} = 0$ where $y_{a}$ and $y_{b}$ represent the regions that meet along that edge. Taking the elements of the finite field with four elements to denote the four colors, Veblen proved that a solution to the four-color problem consists in finding a set of values $\{ y_{i}\}$ which satisfy none of these equations. Veblen then developed these ideas further, expressing the four-color problem in terms of subspaces of a finite projective space. He also showed how a set of equations that arise from the matrix $A$ gives rise to the Heawood congruences we met earlier.

... continue reading