Four Color Theorem

In the fall of 2017, the Mathematics Department held the Four Color Fest celebrating the 40th anniversary of the proof of the Four Color Theorem, perhaps the most significant result in the history of the department. This multi-day event featured lectures, concerts, exhibits, and family activities to celebrate the first successful proof of this elusive result. The activities honored the work from the 1970’s by Kenneth Appel and Wolfgang Haken, Professors of Mathematics at Illinois. Appel and Haken gave the first proof of the Four Color Theorem, which had been conjectured for more than a century, and for which many alleged earlier proofs were found to be flawed.

The Four Color Problem conjectures that four is the smallest number of colors needed to shade the regions of an arbitrary map (satisfying the assumptions mentioned next) so that any two adjacent regions are painted with different colors.

Here are the basic assumptions:

  • Each region is connected.
  • Regions which share a common boundary (a curve or line segment, not just a single point) must receive different colors.
  • The map appears on either a planar surface or the surface of a sphere.

The Four Color Theorem solves this conjecture; four colors suffice!

A map of the United States reveals that at least four colors are required. Consider the states sharing a boundary with Nevada. These states are California, Arizona, Utah, Idaho, and Oregon. It is easy to see that one cannot color all these states (including Nevada) with only three colors.

Map of United States
Map showing only 4 colors to color the United States. w:User:Derfel73, w:User:Dbenbenn, w:User:Strangerpete, CC BY-SA 3.0

The four corner states require only two colors, since Utah and New Mexico are allowed to receive the same color, as their common boundary is merely a point. Similarly, Colorado and Arizona are allowed to receive the same color. If we insisted that states whose common boundary is just one point must be colored differently, then four colors would NOT suffice. That is why the common boundary must be a curve or line segment.

The third assumption is also needed. One can consider maps on more complicated surfaces; for example a map drawn on the surface of a doughnut could require SEVEN colors. See Wolfram Math World for intriguing information on this topic. The Four Color Fest site and its links include additional mathematical and historical information.

 

Map of Illinois Counties stating Four Colors Suffice, Illinois Mathematics Department , 1977, 2017
Illinois Counties, Photo from https://math.illinois.edu/four-color-fest

The Color Fest used the above picture of a map of the counties in Illinois, using four colors. Tee shirts including this map were sold at the fest and are now collector’s items.

After the solution of the conjecture, the Urbana Post Office created a postmark saying “four colors suffice”.

stamp that says four colors suffice from December 28, 1994
For a number of years following the publication of the Four Color Theorem proof, the Department of Mathematics stamped outgoing mail with this postmark. (Image courtesy of the Department of Mathematics.)

 

The problem was likely first posed in 1852, when Francis Guthrie was coloring a map of England. Guthrie theorized that one could always color a planar map with only four colors, when the above assumptions hold. He described the problem to his brother Frederick, who was a university student. Frederick presented the problem to his professor, Augustus de Morgan, (a well-known name to students of math and computer science because of de Morgan’s laws for operations on sets). The conjecture that “Four Colors Suffice” was born.

The challenge in proving this theory comes from the enormous amount of possible combinations for map borders. The problem is approached via graph theory. One regards each region as a vertex and connects vertices with an edge when these regions share a boundary. The number of possible graphs is infinite. Several people thought they had proved the theorem in the 1800’s, but the alleged proofs all contained flaws. The problem went unsolved for over a hundred years.

Kenneth Appel and Wolfgang Haken of the mathematics department at Illinois began their work in 1974. One of the great ideas in their approach was to reduce the problem to a finite (albeit large) number of cases, and to handle these cases using a computer. They completed the proof in 1976. It was the first computer assisted proof of a major theorem. The proof was announced in the Bulletin of the American Math Society and details appeared in two issues of the Illinois Journal of Mathematics.

 

The use of a computer brought considerable initial criticism. Eventually criticism abated and computers have now become a common tool used in mathematical proofs. Furthermore, the techniques in the proof have played major roles in graph theory and in computer science.

Watch Graph coloring and machine proofs in computer science, by Andrew Appel (Higgins Professor of Computer Science at Princeton University and son of Kenneth Appel)

 

To end the Four Color Fest, a “Concert: A Portrait in Four Colors” took place in the Music Building. The featured instrument of the evening was the Haken Continuum invented by Lippold Haken, Wolfgang Haken’s son and a lecturer of electrical and computer engineering at Illinois. The piece was composed specifically for the event by Rudolf Haken, another son of Wolfgang Haken and a professor of viola at the University of Illinois, in the School of Music. Rudolf was also one of the performers in the concert.

Fingerboard Continuum
Haken Continuum

You can find other videos related to the Four Color Theorem from the 2017 forty year anniversary, Four Color Fest at https://math.illinois.edu/four-color-fest.

Kenneth Appel died April 19, 2013 (age 80) and Wolfgang Haken died October 2, 2022 (age 94).

  • Altgeld Hall – home of the math department where Kenneth Appel and Wolfgang Haken were faculty members.

 

Appel, A., [Illinois Dept. of Math]. (2017, November 3). Four Colors Appel Slides [Video]. YouTube. https://www.youtube.com/watch?v=83PlZ9R9_Ps

Appel, K. and Haken, W. (1976). Every planar map is four colorable. Bulletin of the American Mathematical Society, 82, 711-712,  https://doi-org.proxy2.library.illinois.edu/10.1090/S0002-9904-1976-14122-5 open access version: https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-82/issue-5/Every-planar-map-is-four-colorable/bams/1183538218.full

Appel, K. and Haken, W. (1977) Every Planar Map Is Four Colorable. Part I: Discharging. Illinois Journal of Mathematics, 21(3), 429-490. DOI 10.1215/ijm/1256049011

Appel, K., Haken, W., and Koch, J. (1977) Every Planar Map Is Four Colorable. Part II: Reducibility. Illinois Journal of Mathematics, 21(3), 491-567. DOI  10.1215/ijm/1256049012

Brady, H., [Numberphile]. (2017). The Four Color Map Theorem – Numberphile [Video]. YouTube. https://www.youtube.com/watch?v=NgbK43jB4rQ

Brady, H., [Numberphile]. (2017). Four Color Theorem (extra footage) – Numberphile [Video]. YouTube. https://www.youtube.com/watch?v=laMkuPrad3s

Continuum-Side-view.jpg. (2021, May 13). Wikimedia Commons, the free media repository. Retrieved 18:18, June 24, 2022 from https://commons.wikimedia.org/w/index.php?title=File:Continuum-Side-view.jpg&oldid=560067918.

Fritsch, R., & Fritsch, G. (1998). History. In: The Four-Color Theorem. Springer. https://doi-org.proxy2.library.illinois.edu/10.1007/978-1-4612-1720-6_1

Kenneth Appel. (1985). Faculty, Staff and Student Portraits. Record Series 39/2/26, Box 2. University of Illinois Archives.

TeesJ. (2020, October 27). File:FourColorsStamps.jpg. Wikimedia Commons, the free media repository. Retrieved 20:21, June 6, 2022 from https://commons.wikimedia.org/w/index.php?title=File:FourColorsStamps.jpg&oldid=503935536

Wolfgang Haken. (n.d.) Faculty and Staff Press Release File. Record Series 39/1/11, Haken, Wolfgang. University of Illinois Archives.

Wikipedia contributors. (2021, December 22). Continuum Fingerboard. In Wikipedia, The Free Encyclopedia. Retrieved 18:20, June 24, 2022, from https://en.wikipedia.org/w/index.php?title=Continuum_Fingerboard&oldid=1061510184

w:User:Derfel73, w:User:Dbenbenn, w:User:Strangerpete. (2022, January 24). File:Map of United States accessible colors shown.svg.  Wikimedia Commons, the free media repository. Retrieved 21:26, June 6, 2022 from https://commons.wikimedia.org/w/index.php?title=File:Map_of_United_States_accessible_colors_shown.svg&oldid=624050773.

Contributors: Professor Emeritus John P. D'Angelo