https://www.ams.org/journals/notices/202603/noti3305/noti3305.html Skip to main content * Sign in + New to AMS? Register now. + Your Account + Your Purchases + Your Donations + Your Member Directory Listing + ------------------------------------------------------------- + Register for a Meeting + AMS Member Directory * MathSciNet * Bookstore * My Cart * Help * [Google Custom Search placeholder] Navigate the site * Publications Publications Home Over 100 years of publishing excellence Books + Bookstore + Book Author Resources + Submit a Book Proposal + Rights, Licensing, Permissions Open Math Notes + Frequently Asked Questions Journals + Member Journals + Research Journals + Translation Journals + Distributed Journals + Open Access Journals + Guidelines and Policies + Journal Author Resources Librarian Resources + eBook Collections + COUNTER Usage Statistics + My Subscriptions + Subscription Information + Licensing Information Mathematical Reviews/MathSciNet(r) + MathSciNet(r) + Reviewer Home + MathSciNet(r) Subscriptions * Membership + Membership Home Welcome to your membership center + Membership Choices o Join the Society o Renew your Membership o Gift a Membership + Individual Membership o Member Benefits o Member Directory o Reciprocating Societies o Members in Developing Countries + Institutional Membership o Domestic Institutions o International Institutions o Two-Year Institutions o Graduate Student Chapter Program + Other Member Types o Corporate Memberships o Associate Memberships * Meetings & Conferences + Meetings & Conferences Home Engage with colleagues and the latest research + National Meetings o Joint Mathematics Meetings o Upcoming JMMs o Previous JMMs o Special Lectures o Professional Enhancement Programs (PEPs) + Sectional Meetings o Upcoming Sectionals o Previous Sectionals o Presenting Papers o Hosting Sectionals + Other Meetings, Conferences & Workshops o International Meetings o Mathematics Calendar o Short Courses + Meetings Resources o Suggest a Speaker o AMS Meetings Grants o Submitting Abstracts o Welcoming Environment Policy o MathSafe - supporting safe meetings * News & Outreach + News & Outreach Home Explore news, images, posters, and mathematical essays + News from the AMS o Feature Stories o Information for Journalists o In Memoriam + Math Voices o Feature Column o Math in the Media o Column on Teaching and Learning + Explorations o Recognizing Diverse Mathematicians o AMS Posters o Mathematics & Music o Mathematical Imagery o Mathematical Moments * Grants & Awards + Grants & Awards Home Resources and opportunities to further your mathematical pursuits + Grants o AMS Backstop Grants o Research & Travel Grants o Child Care Grants for Meetings o Young Scholars Program Grants + Honors & Awards o Awards o Fellows of the AMS + AMS Fellowships o Stefan Bergman Fellowship o Birman Fellowship o Centennial Fellowship o Claytor-Gilmer Fellowship * Learning & Careers + Learning & Careers Home Resources to support advanced mathematics teaching and learning + For Students o High School o Undergraduate o Graduate o Find Graduate Programs o Math Alliance at the AMS + For Faculty & Leaders o Department Chairs Workshop o Column on Teaching & Learning o Math in the Media o Salary & Departmental Data + Jobs o Employment Services o MathJobs o BEGIN Careers + Professional Development o Mathematics Research Communities o Mathematical Opportunities Listing o MathPrograms * Government Relations + Government Relations Home Advocating for the mathematical sciences + Elevating Mathematics in Congress o Letters, Statements, & Legislation o Congressional Briefings + Legislative Priorities o Federal Issues of Concern o Federal Budget Process + Get Involved o Advocacy Resources o Contact Us + DC-Based Fellowships o Congressional Fellowship o Mass Media Fellowship o Catalyzing Advocacy in Science & Engineering (CASE) Fellowship * Giving + Giving to the AMS Your gifts make great things happen for mathematics + What You Can Support o The 2020 Fund o Next Generation Fund o Birman Fellowship for Women Scholars o JMM Child Care Grants o Mathematics Research Communities o MathSciNet for Developing Countries + Create a Legacy o Make a Tribute Gift o Create a Permanent Fund o Establish a Prize, Award or Fellowship o Bequests and Charitable Estate Planning + Honoring Your Gift o Donor Stories o Donor Wall of Honor o Thomas S. Fiske Society o AMS Contributors Society o AMS Gardens + Giving Resources o AMS Development Committee o AMS Gift Acceptance Policy o Contact Us o Donate Now * About the AMS + About the AMS Advancing research. Connecting the mathematics community + Our Organization o Accessibility o Equal Opportunity and Fairness o Jobs at AMS o Contact Us o Customer Service + Leadership o Executive Staff o Officers o Board of Trustees o Council o Executive Committee o Presidents o Committees + Governance Operations o Bylaws o Elections o Calendar of Meetings o Policy Statements & Guidelines AMS Website Down On Thursday, April 24th, 2025 from 5:30 AM ? 8:00 AM we will be performing maintenance on our website. During this time, the site will be unavailable. 1. Home 2. Notices of the American Mathematical Society Journal cover: Notices of the American Mathematical Society Notices of the American Mathematical Society Welcome to the Notices of the American Mathematical Society. With support from AMS membership, we are pleased to share the journal with the global mathematical community. PDFLINK 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). Graphic without alt text 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). Graphic without alt text The four-color problem has also been wrongly credited to the German mathematician and astronomer August Mobius, 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). Graphic without alt text 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. Graphic without alt text 3. Alfred Kempe Figure 5. Alfred Kempe (1849-1922). Graphic without alt text 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. Graphic without alt textGraphic without alt text 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. Graphic without alt text 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). Graphic without alt text 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. Graphic without alt text 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). Graphic without alt text 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. Graphic without alt text 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. Graphic without alt text 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. Graphic without alt text 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 Gottingen. 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. Graphic without alt text Figure 15. A configuration with ring-size 14. Graphic without alt text 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). Graphic without alt text 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. 8. George Birkhoff In early 1912 a friend and contemporary of Veblen at Princeton was George David Birkhoff, one of the most versatile and influential mathematicians of the early 20th century. Born in Michigan, he showed great promise from an early age. In 1902 he attended the University of Chicago, where he and Veblen first met. After a year there, he relocated to Harvard University for his bachelor's and master's degrees, before returning to Chicago to write a doctoral thesis on differential equations. After spending the next two years at the University of Wisconsin, he transferred to Princeton where he was promoted to professor. In 1912 he returned to Harvard where he remained for the rest of his life. Figure 17. George Birkhoff (1884-1944). Graphic without alt text Although Birkhoff is best remembered for his work in dynamical systems, differential equations, ergodic theory, and other areas, he had a lifelong fascination for the four-color problem. Ever in search of a proof, he used to ask his wife to draw complicated maps for him to color. Birkhoff's first approach to map coloring was quantitative, asking for the number $P(k)$ of ways to color a given map with $k$ colors; for example, for a map of four mutually neighboring regions this is $$\begin{align*} P(k) &= k (k - 1) (k - 2) (k - 3)\\ &= k ^4 - 6k ^3 + 11k ^2 - 6k. \end{align*}$$ He proved that $P(k)$ is always a polynomial in $k$ (now called the chromatic polynomial of the map), showed that if the map has $n$ regions and $m$ edges, then $P(k)$ starts with ,${k ^{n}} - mk^{n-1}$ and obtained a formula for every other coefficient. By studying these polynomials in general, he hoped to prove that $P(4) > 0$ for all maps. Birkhoff's interest in chromatic polynomials continued throughout his life, and in 1930 and 1934 he published further papers on the subject. The former was written up by Hassler Whitney (later to become a pioneering topologist) who had impressed Birkhoff with his ideas on the four-color problem, and who wrote a doctoral thesis on The Coloring of Graphs under Birkhoff's supervision; Whitney also published a noteworthy paper on chromatic polynomials in which he presented a simpler method for calculating their coefficients, and proved that these coefficients always alternate in sign. A lengthy and influential joint paper on the subject was later published by Birkhoff (posthumously) in collaboration with his former research student Daniel C. Lewis. In 1913, in a pioneering paper 11, Birkhoff made a significant contribution to the eventual solution of the four-color problem by describing a configuration as reducible if every coloring of the surrounding ring of regions can be extended to the regions inside. It follows that a reducible configuration cannot appear in a minimal counterexample to the four-color theorem. After systematically showing that every configuration surrounded by a ring of three or four regions is reducible, Birkhoff progressed to those with ring-size 5 and proved that these are all reducible, apart from the single pentagon. He also showed that the Birkhoff diamond (Figure 18) of four pentagons surrounded by a ring of six regions is reducible. Here there are essentially 31 different colorings of the surrounding ring; for 16 of these the coloring extends directly to the pentagons, while for the remaining 15 this is effected after one or more Kempe interchanges of color. Figure 18. The Birkhoff diamond. Graphic without alt text In the ensuing years, many more reducible configurations would be discovered, eventually numbering in the hundreds and thousands. 9. Philip Franklin In the 1920s and 1930s, steady progress continued to be made. In 1921 the Belgian mathematician Alfred Errera wrote a doctoral thesis on map coloring for the University of Brussels and followed this with several further papers, proving in particular that every minimal counterexample to the four-color theorem must contain at least 13 pentagons, and cannot contain only pentagons and hexagons. Meanwhile in America, Philip Franklin had appeared on the scene. A graduate of the City College of New York, he transferred to Princeton University where he completed a doctoral thesis entitled The Four Color Theorem under the supervision of Oswald Veblen. He followed this with an important paper 12 which extended the current knowledge, both of unavoidable sets and of reducible configurations. In 1924 he moved to the Massachusetts Institute of Technology where he remained for the rest of his life, researching in various areas and writing several well-regarded textbooks for students. In his paper Franklin used Kempe's counting formula to discover further reducible configurations, such as a pentagon adjacent to three pentagons and a hexagon adjacent to four pentagons and two hexagons. He also proved that every map with no digons, triangles, or squares must include a pentagon joined to two others, to two pentagons and a hexagon, or to a pentagon and two hexagons; this yielded the new unavoidable set in Figure 19. No further unavoidable sets would then appear until 1940 when Henri Lebesgue (of Lebesgue integral fame), in the last paper he ever wrote, produced several new ones. Figure 19. Franklin's unavoidable set. Graphic without alt text Franklin also deduced that every map with up to 25 regions can be colored with four colors. Further work along these lines was then carried out by Clarence Reynolds of West Virginia University who increased this number to 27, and by C. E. Winn who in 1940 increased it further to 35. 10. Heinrich Heesch Following World War II, attempts at proving the four-color theorem began to take a different turn with the appearance of the German mathematician Heinrich Heesch. Born in Kiel, he graduated in both mathematics and music in Munich before earning a doctorate at the University of Zurich for a thesis on the axioms of geometry. He then transferred to Gottingen University, where he became an assistant to Hermann Weyl on studies into crystals. While there, he gained some notoriety for solving the "regular parquet problem" on plane tiling patterns; this was part of "Problem 18", one of the challenges that David Hilbert had posed when he gave his celebrated lecture at the Paris International Congress of Mathematicians in 1900. But from 1933 the National Socialists' purges of staff at German universities were making academic life intolerable, and Heesch resigned from his Gottingen position. Returning to Kiel, he stayed with his parents for the next dozen years, supporting himself by schoolteaching while continuing his researches into tiling patterns; one of these patterns was later incorporated into the ceiling of the library in Gottingen. Heesch first learned of the four-color problem in the mid-1930s and developed a lifelong fascination with it. He quickly realized that in order to solve it he should seek an unavoidable set of reducible configurations--"unavoidable" means that every map must include one or more of these configurations, and "reducible" means that whichever one it is, every coloring of the rest of the map can be extended to the configuration. In other words, because no reducible configurations in the unavoidable set can appear in a minimal counterexample to the four-color theorem, no such counterexample can exist. Around 1948, Heesch presented a lecture on the four-color problem to a large audience in Kiel. Proposing the need for a finite unavoidable set of reducible configurations, he accepted that such a set might be very large--possibly involving up to 10,000 configurations. To help with their classification he defined a configuration to be D-reducible if any coloring of the regions in the surrounding ring could be extended to the configuration, either directly or after interchanges of color: as we have seen, digons, triangles, squares, and the Birkhoff diamond are all -$D$reducible. He also called a configuration C-reducible if it could be made reducible by first modifying it in some convenient way. Meanwhile, Heesch was constructing large numbers of reducible configurations, and over the years he developed the ability to recognize at sight when configurations are reducible--eventually with over 80 percent accuracy. To this end, he noted three features whose presence seemed to prevent a configuration from being reducible--these are a "4-legger region" adjacent to four consecutive regions of the surrounding ring, a "3-legger articulation region" adjacent to three regions (not all adjacent) of the surrounding ring, and a "hanging 5-5 pair" of adjacent pentagons that are both adjacent to a single region within the ring (see Figure 20). Figure 20. Three obstacles to reducibility. Graphic without alt text As we have remarked, few unavoidable sets were known at this time, but Heesch discovered a useful approach to showing that a given set of configurations is unavoidable. This became known as the method of discharging and takes many forms, but to illustrate the basic idea we can show why Wernicke's set of configurations (in Figure 14) is unavoidable. So suppose, for a contradiction, that there exists a map with no digons, triangles, or squares, no two adjacent pentagons, and no pentagon adjacent to a hexagon; then every pentagon is adjacent only to regions with seven or more edges. Next, assign a "charge" of $6 - k$ to each -$k$sided region, so that pentagons receive unit charge, hexagons receive zero charge, and polygons with more than six edges receive negative charge. It then follows from Kempe's counting formula that the total charge on the whole map is 12, a positive number. If we now "discharge" the map by distributing the unit charge on each pentagon equally to its five neighbors, then the total charge on the map remains positive, but every pentagon now has zero charge, the hexagons still have zero charge, and (as is easily checked) the others receive insufficient charge to become positive. It follows that the total charge on the map is nonpositive, and this contradiction proves the result. By this time, the subject of graph theory was developing and most map-colorers were working with the four-color problem in its "dual form"--that is, in Kempe's linkage version. Here, instead of coloring a map with neighboring regions receiving different colors, the aim is to color the vertices of a planar graph so that any two adjacent vertices are colored differently. To this end, Heesch introduced convenient symbols for the vertices that correspond to pentagons, hexagons, etc. (see Figure 21). In later years, these became used almost universally. Figure 21. Heesch's symbols for the regions of a map. Graphic without alt text 11. Wolfgang Haken Born in Berlin in 1928, Wolfgang Haken showed an early taste for mathematics. At the age of 15 he was drafted into a World War II anti-aircraft battery while continuing with his schoolwork which he concluded in early 1946. At this time, most German universities were not accepting students below the age of 23, but the University of Kiel was an exception and Haken began his studies there when just 17, the youngest student in the university. Accepted in the middle of the university year to read mathematics, physics, and philosophy, he was thrown straight into second-semester courses without having studied the earlier groundwork. But he managed to catch up, later describing this period as "really very, very exciting--for me they were wonderful years." Kiel then had just one active mathematics professor, Karl-Heinrich Weise. An excellent teacher, in 1947 he taught a topology course in which he mentioned three unsolved problems: the knot problem, the Poincare conjecture, and the four-color problem. All three would later occupy a major part of Haken's life with his solution of the first, his substantial contributions to the second, and his eventual solution with Kenneth Appel of the third. In Kiel Haken came to know Heinrich Heesch and attended his lecture on the four-color problem. Haken understood little of it at the time, but later recalled that Heesch needed to work systematically through some 10,000 special cases in order to obtain a proof. This talk planted a seed in Haken's mind which would bear fruit in the decades to come. Following the award of his degree in 1948, Haken began graduate studies with Weise as his supervisor, obtaining a doctorate in 1953 for a thesis on higher-dimensional topology. He then relocated to Munich, where he worked on microwave technology in the research and development section of the Siemens company. While in Munich Haken maintained his interest in mathematics, being particularly intrigued by the "knot problem" of deciding whether a given three-dimensional closed curve (such as a tangle of string) has a knot in it. He worked on this problem in his spare time and eventually succeeded in producing a complete solution which he announced at the 1954 International Congress of Mathematicians in Amsterdam. His difficulty lay in finding the time to write up a full proof for publication while continuing his full-time job, but this task was eventually completed and his lengthy proof duly appeared in Acta Mathematica. One academic who read Haken's proof was the logician Bill Boone of the University of Illinois in Urbana-Champaign. Greatly impressed, he invited Haken to the University as a visiting professor, and while there Haken lectured on his solution to the problem. He then spent two years at Princeton's Institute for Advanced Study before returning to Illinois to take up a permanent position at the University. Haken then turned his attention to proving the Poincare conjecture. His approach to every difficult problem was to regard it as a tree with many leaves and branches, and to cut these down one at a time until the whole tree was demolished. For the Poincare conjecture, he found 200 leaves to be removed and claimed to have removed 198 of these. But after struggling with the last two for ten years, he finally admitted defeat. In 1967, Oystein Ore published the first book on the four-color problem 6, and in that year Haken turned his attention to the subject which he had neglected for almost twenty years. He first decided to contact Heesch to ascertain whether the latter had solved the four-color problem or whether he was still working through his 10,000 special cases. By this time, Heesch had produced thousands of reducible configurations, but had been unable to package them into an unavoidable set. Haken invited Heesch to present a lecture on the four-color problem at the University of Illinois, and asked him whether the increasing use of computers might help with the checking of so many configurations. Heesch was now working at the Free University of Hanover and had already employed a former graduate student named Karl Durre to test configurations for -$D$reducibility on the University's current computer; for any given configuration, this could be done routinely by checking whether all colorings of the surrounding ring could be extended, directly or after color-interchanges, to the regions inside it. We have seen that, for the Birkhoff diamond with ring-size 6, there are essentially 31 different colorings of the surrounding ring to check. But as the configurations increase in complexity, the number of colorings increases dramatically--by a factor of 4 for each unit increase in the ring-size--and for a configuration with ring-size 14 there are 199,271 colorings to consider. With so many configurations to check, the thousands of hours needed by any current computer seemed unachievable. The University of Illinois had no computers ready for use, but its computer department was able to arrange for Heesch and Durre to use the powerful Cray computer at the Brookhaven National Laboratory on Long Island. Its director, Yoshio Shimamoto, was himself fascinated by the four-color problem and invited them to spend long periods of time at Brookhaven. It was then already known that any solution would necessarily involve configurations with ring-size 12 or more, and the Cray machine then enabled them to check the -$D$reducibility of many configurations with ring-size 13 while starting on those with ring-size 14. At one stage in the investigations, Shimamoto discovered a single configuration, the so-called "Shimamoto horseshoe" with ring-size 14, whose expected -$D$reducibility would prove the four-color theorem in its entirety. Rumors quickly spread around the world, but after grinding on for 26 long hours, the computer eventually confirmed, to everyone's disappointment, that the horseshoe configuration was not - $D$reducible after all. 12. Kenneth Appel Around 1970, Heesch had developed some new discharging processes which he believed would reduce the four-color problem to 8,900 awkward configurations with ring-size up to 18, which could then be tested individually. But by this time Haken had become disillusioned with the prospect of having to work through so many difficult cases, and during a lecture which he presented at the University of Illinois he announced: The computer experts have told me that it is not possible to go on like that. But right now I'm quitting. I consider this to be the point to which and not beyond one can go without a computer. One of the people attending Haken's lecture was Kenneth Appel, who had written a doctoral thesis for the University of Michigan on some links between mathematical logic and algebra. A highly accomplished computer programmer, he had learned his computing skills while in Michigan and his career had included working for Douglas Aircraft and researching at Princeton's Institute of Defence Analyses before transferring to the University of Illinois in 1961. At the time of the lecture, Appel was one of the examiners for a doctoral thesis on an aspect of the four-color problem by one of Haken's research students, and after Haken's pronouncement he approached Haken with a proposal: I don't know of anything involving computers that can't be done: some things just take longer than others. Why don't we take a shot at it? Figure 22. Kenneth Appel (1932-2013) and Wolfgang Haken (1928-2022). Graphic without alt text Up to this time, most map-colorers sought reducible configurations in large numbers before attempting unsuccessfully to package them into unavoidable sets. But Haken's approach was different, in that he sought to develop unavoidable sets that consisted of configurations which appeared "likely to be reducible," before testing these configurations for reducibility. Any configuration that was not easily shown to be reducible would then be replaced by others. His hope was that this iterative process would lead more quickly to an unavoidable set of reducible configurations. When Appel and Haken started to develop this idea, the earliest outputs of configurations from the computer contained many duplicates, but Appel soon introduced some simple modifications that reduced the list. This quickly became an ongoing experimental process, with Appel and Haken regularly adjusting the discharging algorithm and improving the computer program to refine the list. To simplify matters, they restricted their attention to configurations which included none of Heesch's three obstacles to reducibility, as these would be unlikely to feature in an eventual unavoidable set. Initially concentrating on "geographically good" configurations that excluded just the first two obstructions (the 4-legger and 3-legger regions), they came to believe that producing an unavoidable set of geographically good configurations within a couple of months was indeed within the bounds of possibility. With this in mind they then spent several months of 1974 developing a theoretical argument which confirmed that such an unavoidable set does indeed exist, with an achievable method for its construction. Gradually, Appel and Haken came to realize that although -$D$ reducible configurations were usually manageable (if they were not too large), some help would be needed with the -$C$reducible ones, where modifications were necessary but their nature was unclear. On approaching the University's computer science department, Appel found that a graduate student named John Koch was willing to help. Appel tasked him with finding simple ways to modify -$C$reducible configurations with ring-size 11, and when Koch succeeded in doing so, Appel was then able to extend Koch's ideas to configurations with larger ring-size. In 1975, Appel and Haken introduced Heesch's third obstacle to reducibility (the hanging 5-5 pair) and were relieved to find that the consequent changes in their procedures would only double the size of the unavoidable set. The various improvements they continued to make during these months soon led to a "man-machine dialog" in which the computer seemed to discover approaches of its own which improved those that had been specifically programmed. Already they were coming to believe that it would be possible to find an obstacle-free unavoidable set of configurations that were likely to be reducible, and that the number of problematic configurations would be small. To their great relief it had also become clear that they would not need to go beyond ring-size 14. Throughout the first few months of 1976, they continued to make further improvements to their discharging methods, using these awkward configurations to guide them. In March of 1976 the University of Illinois purchased a powerful new computer which would be largely unused during the spring break, and Appel was able to use it most effectively for the massive task of checking all their configurations for reducibility. In the event this saved them many months of tedious work, and to their great surprise the task was completed in June. To celebrate their success, Appel wrote a note on the mathematics department's blackboard saying: Modulo careful checking it appears that four colors suffice. With their family members to help, the final checks were completed in just a few weeks, resulting in an unavoidable set of 1936 reducible configurations. On July 22, 1976, they went public, informing their colleagues, and sending out preprints to other workers in the field. Figure 23. The mathematics department's postmark following the announcement of the proof. Graphic without alt text 13. Aftermath Appel, Haken, and Koch were just in time, as some of their competitors were approaching complete solutions. The eminent combinatorialist Bill Tutte endorsed their solution, and their success was reported in newspapers around the world. Appel and Haken wrote a short "Research Announcement" for the American Mathematical Society, outlining the main ideas of their proof 13. In December 1977, Appel and Haken published a lengthy paper 14 in the Illinois Journal of Mathematics on the discharging part of the proof, and coauthored a sequel 15 with John Koch on the reducibility part; these papers were accompanied by a microfiche providing 450 pages of further explanations and diagrams. By then, the authors had found many duplications and instances of one configuration within another, and the number of configurations in the published list was now reduced to 1482. A few mistakes subsequently discovered were corrected, but Appel and Haken knew that, with so much self-correction within the proof, a few rogue configurations could always be easily replaced. The computer-assisted proof of such a long-standing problem was welcomed with enthusiasm by some, and with unease and disappointment by many, but was rejected outright by others who did not accept mathematical arguments that could not be checked by hand. Figure 24. A few of Appel and Haken's reducible configurations. Graphic without alt text In 1986 Appel and Haken wrote a lighthearted article entitled "The four color proof suffices" 16 which answered many of the criticisms that had arisen, and followed this three years later with a large volume 17 which corrected all the detected errors and included a printout of their microfiche pages. Then, in 1994, Neil Robertson and Paul Seymour, who spent many summers solving open problems in graph theory, collaborated with Daniel Sanders and Robin Thomas to rework the Appel-Haken approach, making it more streamlined and systematic, and obtained a simpler unavoidable set with just 633 reducible configurations 18. Ten years later their approach was fully machine-checked by the French computer scientist Georges Gonthier 19 who verified 60,000 lines of formal language proof before declaring that their proof was indeed correct. The four-color theorem could at last be considered proved. References 12345678 contain further information about the history and proof of the four-color theorem, together with detailed references to the papers cited in this article. References 9101112 and 1819 are for notable papers mentioned in the article, and 1314151617 are publications by Appel and Haken. References [1] Robin Wilson, Four colors suffice: How the map problem was solved , Princeton Science Library, Princeton University Press, Princeton, NJ, 2014. Revised color edition of the 2002 original, with a new foreword by Ian Stewart. MR3235839, AMSref \bib{1} {book}{ author={Wilson, Robin}, title={Four colors suffice}, series={Princeton Science Library}, subtitle={How the map problem was solved}, note={Revised color edition of the 2002 original, with a new foreword by Ian Stewart}, publisher={Princeton University Press, Princeton, NJ}, date={2014}, pages={xviii+199}, isbn={978-0-691-15822-8}, isbn={0-691-15822-3}, review={\MR {3235839}}, } [2] Robin Wilson, John J. Watkins, and David J. Parks, Graph theory in America--the first hundred years, Princeton University Press, Princeton, NJ, 2023, DOI 10.2307/j.ctv2sbm8p2. MR4574842, AMSref \bib{2}{book}{ author={Wilson, Robin}, author={Watkins, John J.}, author={Parks, David J.}, title={Graph theory in America---the first hundred years}, publisher={Princeton University Press, Princeton, NJ}, date={2023}, pages={xxi+293}, isbn= {978-0-691-19402-8}, isbn={978-0-691-24065-7}, review={\MR {4574842}}, doi={10.2307/j.ctv2sbm8p2}, } [3] Lowell W. Beineke, Bjarne Toft, and Robin J. Wilson, Milestones in graph theory--a century of progress, AMS/MAA Spectrum, vol. 108, MAA Press, Providence, RI, 2025. MR4922623, AMSref \bib {3}{book}{ author={Beineke, Lowell W.}, author={Toft, Bjarne}, author={Wilson, Robin J.}, title={Milestones in graph theory---a century of progress}, series={AMS/MAA Spectrum}, volume={108}, publisher={MAA Press, Providence, RI}, date={2025}, pages= {xv+124}, isbn={978-1-4704-6431-8}, review={\MR {4922623}}, } [4] Donald MacKenzie, Slaying the Kraken: the sociohistory of a mathematical proof, Soc. Stud. Sci. 29 (1999), no. 1, 7-60, DOI 10.1177/030631299029001002. MR1692830, AMSref \bib{4}{article}{ author={MacKenzie, Donald}, title={Slaying the Kraken: the sociohistory of a mathematical proof}, journal={Soc. Stud. Sci.}, volume={29}, date={1999}, number={1}, pages={7--60}, issn= {0306-3127}, review={\MR {1692830}}, doi={10.1177/ 030631299029001002}, } [5] Rudolf Fritsch and Gerda Fritsch, The four-color theorem: History, topological foundations, and idea of proof, Springer-Verlag, New York, 1998. Translated from the 1994 German original by Julie Peschke, DOI 10.1007/978-1-4612-1720-6. MR 1633950, AMSref \bib{5}{book}{ author={Fritsch, Rudolf}, author= {Fritsch, Gerda}, title={The four-color theorem}, subtitle= {History, topological foundations, and idea of proof}, note= {Translated from the 1994 German original by Julie Peschke}, publisher={Springer-Verlag, New York}, date={1998}, pages= {xvi+260}, isbn={0-387-98497-6}, review={\MR {1633950}}, doi= {10.1007/978-1-4612-1720-6}, } [6] Oystein Ore, The four-color problem, Pure and Applied Mathematics, vol. 27, Academic Press, New York-London, 1967. MR 216979, AMSref \bib{6}{book}{ author={Ore, Oystein}, title={The four-color problem}, series={Pure and Applied Mathematics, vol. 27}, publisher={Academic Press, New York-London}, date={1967}, pages={xv+259}, review={\MR {216979}}, } [7] Thomas L. Saaty and Paul C. Kainen, The four-color problem: Assaults and conquest, McGraw-Hill International Book Co., New York-Bogota-Auckland, 1977. MR480047, AMSref \bib{7}{book}{ author={Saaty, Thomas L.}, author={Kainen, Paul C.}, title={The four-color problem}, subtitle={Assaults and conquest}, publisher= {McGraw-Hill International Book Co., New York-Bogot\'{a} -Auckland}, date={1977}, pages={ix+217}, review={\MR {480047}}, } [8] Hans-Gunther Bigalke, Heinrich Heesch (German), Vita Mathematica, vol. 3, Birkhauser Verlag, Basel, 1988. Kristallgeometrie. Parkettierungen. Vierfarbenforschung. [Geometry of crystals. Tilings. Four color problem], DOI 10.1007/978-3-0348-7246-1. MR 946224, AMSref \bib{8}{book}{ author={Bigalke, Hans-G\"{u}nther}, title={Heinrich Heesch}, language={German}, series={Vita Mathematica}, volume={3}, note={Kristallgeometrie. Parkettierungen. Vierfarbenforschung. [Geometry of crystals. Tilings. Four color problem]}, publisher={Birkh\"{a}user Verlag, Basel}, date={1988}, pages={320}, isbn={3-7643-1954-2}, review={\ MR {946224}}, doi={10.1007/978-3-0348-7246-1}, } [9] A. B. Kempe, On the geographical problem of the four colours, Amer. J. Math. 2 (1879), no. 3, 193-200, DOI 10.2307/2369235. MR 1505218, AMSref \bib{9}{article}{ author={Kempe, A. B.}, title= {On the geographical problem of the four colours}, journal={Amer. J. Math.}, volume={2}, date={1879}, number={3}, pages={193--200}, issn={0002-9327}, review={\MR {1505218}}, doi={10.2307/2369235}, } [10] P. J. Heawood, Map-colour theorem, Quarterly J. Pure and Applied Math. 24 (1890), 332-338. [11] George D. Birkhoff, The reducibility of maps, Amer. J. Math. 35 (1913), no. 2, 115-128, DOI 10.2307/2370276. MR1506176, AMSref \ bib{11}{article}{ author={Birkhoff, George D.}, title={The reducibility of maps}, journal={Amer. J. Math.}, volume={35}, date={1913}, number={2}, pages={115--128}, issn={0002-9327}, review={\MR {1506176}}, doi={10.2307/2370276}, } [12] Philip Franklin, The four color problem, Amer. J. Math. 44 (1922), no. 3, 225-236, DOI 10.2307/2370527. MR1506473, AMSref \ bib{12}{article}{ author={Franklin, Philip}, title={The four color problem}, journal={Amer. J. Math.}, volume={44}, date= {1922}, number={3}, pages={225--236}, issn={0002-9327}, review={\ MR {1506473}}, doi={10.2307/2370527}, } [13] K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976), no. 5, 711-712, DOI 10.1090/ S0002-9904-1976-14122-5. MR424602, AMSref \bib{13}{article}{ author={Appel, K.}, author={Haken, W.}, title={Every planar map is four colorable}, journal={Bull. Amer. Math. Soc.}, volume= {82}, date={1976}, number={5}, pages={711--712}, issn= {0002-9904}, review={\MR {424602}}, doi={10.1090/ S0002-9904-1976-14122-5}, } [14] K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429-490. MR 543792, AMSref \bib{14}{article}{ author={Appel, K.}, author= {Haken, W.}, title={Every planar map is four colorable. I. Discharging}, journal={Illinois J. Math.}, volume={21}, date= {1977}, number={3}, pages={429--490}, issn={0019-2082}, review={\ MR {543792}}, } [15] K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491-567. MR543793, AMSref \bib{15}{article}{ author={Appel, K.}, author={Haken, W.}, author={Koch, J.}, title={Every planar map is four colorable. II. Reducibility}, journal={Illinois J. Math.}, volume={21}, date={1977}, number={3}, pages={491--567}, issn= {0019-2082}, review={\MR {543793}}, } [16] K. Appel and W. Haken, The four color proof suffices, Math. Intelligencer 8 (1986), no. 1, 10-20, 58, DOI 10.1007/BF03023914. MR823216, AMSref \bib{16}{article}{ author={Appel, K.}, author= {Haken, W.}, title={The four color proof suffices}, journal= {Math. Intelligencer}, volume={8}, date={1986}, number={1}, pages ={10--20, 58}, issn={0343-6993}, review={\MR {823216}}, doi= {10.1007/BF03023914}, } [17] Kenneth Appel and Wolfgang Haken, Every planar map is four colorable, Contemporary Mathematics, vol. 98, American Mathematical Society, Providence, RI, 1989. With the collaboration of J. Koch, DOI 10.1090/conm/098. MR1025335, AMSref \bib{17}{book}{ author={Appel, Kenneth}, author={Haken, Wolfgang}, title={Every planar map is four colorable}, series= {Contemporary Mathematics}, volume={98}, note={With the collaboration of J. Koch}, publisher={American Mathematical Society, Providence, RI}, date={1989}, pages={xvi+741}, isbn= {0-8218-5103-9}, review={\MR {1025335}}, doi={10.1090/conm/098}, } [18] Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2-44, DOI 10.1006/jctb.1997.1750. MR1441258, AMSref \bib {18}{article}{ author={Robertson, Neil}, author={Sanders, Daniel}, author={Seymour, Paul}, author={Thomas, Robin}, title= {The four-colour theorem}, journal={J. Combin. Theory Ser. B}, volume={70}, date={1997}, number={1}, pages={2--44}, issn= {0095-8956}, review={\MR {1441258}}, doi={10.1006/ jctb.1997.1750}, } [19] Georges Gonthier, Formal proof--the four-color theorem, Notices Amer. Math. Soc. 55 (2008), no. 11, 1382-1393. MR2463991, AMSref \bib{19}{article}{ author={Gonthier, Georges}, title={Formal proof---the four-color theorem}, journal={Notices Amer. Math. Soc.}, volume={55}, date={2008}, number={11}, pages={1382--1393}, issn={0002-9920}, review={\MR {2463991}}, } Robin Wilson is an emeritus professor of pure mathematics at the Open University, UK; an emeritus professor of geometry at Gresham College, London; and a former Fellow of Keble College, Oxford University. His email address is Robin.Wilson@open.ac.uk. Graphic without alt text Article DOI: 10.1090/noti3305 Credits Figures 1-3, 5, 8, 16, and 17 are from Wikimedia Commons. Figures 4, 6, 7, 9, 11-15, and 18-21 are courtesy of Robin Wilson / Princeton University Press. Previously appeared in Robin Wilson, Four colors suffice, Princeton University Press, 2014. Figures 10 and 24 are courtesy of Robin Wilson. Figures 22 and 23 are courtesy of the Mathematics Department, University of Illinois at Urbana-Champaign. Photo of Robin Wilson is courtesy of Catherine Lidbetter. masthead * Current Issue * About Notices * From the Secretary * Full Issues * Features * Career * Topical Columns * Reviews * What Is ... * Memorials * ----------------------------------------------------------------- * Notices Media Kit * Notices Features * Author Guidelines * ----------------------------------------------------------------- * Join the AMS Sidebar advert in The Notices Link to the American Mathematical Society homepage * * * * * American Mathematical Society * 201 Charles Street Providence, Rhode Island 02904-2213 * Contact Us AMS, American Mathematical Society, the tri-colored AMS logo, and Advancing research, Creating connections, are trademarks and services marks of the American Mathematical Society and registered in the U.S. Patent and Trademark Office. (c) Copyright 2024 American Mathematical Society * View Our Privacy Statement * Terms of Use * Accessibility and AMS Online Content