The Four Color Theorem: A New-Age Algorithm for the Classical Coloring Problem

You must have heard of the Four Color Theorem, which was originally derived from the interesting problem of coloring countries on a map and is known as one of the three major mathematical problems in the modern world. It took mathematicians more than 100 years to give a real proof, and the computer proof used has also appeared on the mathematical stage. Today, in the field of graph theory, there are still many interesting problems derived from the Four Color Theorem. For example, a problem that originated from a radio broadcasting station: fill in numbers on an infinitely large grid paper, and the "distance" between the same number must be greater than the number itself, so how many numbers are needed to cover the entire plane?

Written by | Han Ying

When you were young, did you stare at the world map on the wall of your study? Staring at the colorful patterns, you imagined that one day you would be able to travel around the world. In 19th century Britain, an ancient and classic mathematical problem - the coloring problem - was born from such a gaze.

Figure 1: World Map | Source: Standard Map Service System of the Ministry of Natural Resources

Origin of the Four Color Problem

The story began in 1852, when Francis Guthrie, a British cartographer, raised a question about "coloring the map" while observing a map. He found that only four colors were needed to color the map so that adjacent countries had different colors. But what puzzled him was whether the number "4" was the best? So he sought help from his brother Frederick Guthrie and his friends. During the communication, they gradually realized that this problem had a deep connection with mathematics. So Frederick sought help from his teacher, Augustus De Morgan, a mathematician at University College London. After trying, Professor De Morgan was helpless, so he wrote a letter to pass the problem to his good friend, Irish mathematician Professor William Hamilton. Unfortunately, the wise Hamilton was not very interested in this problem.

Morgan wrote in the letter: "A student asked me to explain a fact today. We don't know whether it can be regarded as a fact. He said that a figure on a plane can be arbitrarily divided into a finite number of parts and each part can be colored so that adjacent parts have different colors, and only four colors can be used. What do you think? If this problem is true, can it attract people's attention?"

At first, this "easy-sounding" problem did not attract widespread attention from mathematicians. It was not until 1878 that British mathematician Arthur Cayley officially announced and named this problem the "four-color problem" at the London Mathematical Society, which aroused everyone's desire to solve it. At the time, mathematicians generally believed that the four-color problem would not be too difficult and should be solved quickly. However, things did not go as planned. It took more than 120 years from the "four-color conjecture" to the "four-color theorem", and it was even once called the world's three most famous mathematical problems along with "Fermat's Last Theorem" and "Goldbach's Conjecture".

Figure 2: Mathematician Cayley Source: Smithsonian Institution Librarie

Centennial Proof of the Four Color Theorem

There is a lot of invalid information in the popular description of the four-color problem, such as the shape, area, longitude and latitude of each country, etc. The only important information is - adjacency (that is, two regions share the same border). Ignoring this invalid information, let's see how to strictly define this problem using the abstract language of graph theory.

Given a graph G = (V, E), where the non-empty set V is the vertex set and E is the edge set. The concept of dual graph is actually used here, that is, a vertex ν∈V is used to represent a country on the map; an edge e12=(ν1, ν2)∈E is used to represent that two vertices (countries) ν1 and ν2 are adjacent. Below we only consider simple undirected graphs - the edges of the graph are undirected, that is, e12=e21; there are no duplicate edges, that is, there is at most one edge connecting vertices ν1 and ν2; there are no self-loops, that is, there are no edges connecting only one vertex.

The four-color problem is then abstracted into a conjecture: to color the vertices of a simple undirected graph G = (V, E) so that adjacent points have different colors , then at least four colors are needed. The minimum number of colors required here is called the chromatic number.

At first, people could only calculate manually to find that the four-color conjecture was true for a map containing 96 countries. The turning point of the story occurred in 1879, when a British lawyer, Alfred Kempe, provided an important idea for the proof of the four-color conjecture. Kempe proposed that in any simple undirected graph G=(V, E), at least one vertex has 2, 3, 4 or 5 adjacent vertices (a country has at least 2, 3, 4 or 5 neighboring countries). This proposition is actually an application of Euler's formula. Suppose there are ν vertices, e edges and f faces in the graph G=(V, E). First of all, any face has at least three edges, two adjacent faces share an edge, and each edge has 2 vertices, so 2e=3f. If each vertex has at least 6 edges, then 2e≥6ν. But Euler's formula tells us that ν-e+f=2. This leads to a contradiction.

Kempe named the above vertices with at most 5 adjacent points and their corresponding edges as "inevitable configurations". Next, he used induction to remove this vertex and adjacent edges to obtain a subgraph G'. If this subgraph G' satisfies the four-color conjecture, then the original graph G' is called reducible, and the removed vertices and edges are called "reducible configurations". Kempe believes that as long as it can be proved that all inevitable configurations are reducible configurations (that is, they can be four-colored after removing the corresponding vertices and their edges), then the four-color conjecture must hold. In mathematical terms, assuming that a graph containing n vertices satisfies the four-color conjecture, then for a graph with n+1 vertices, there must be a vertex and its edge that is an inevitable configuration. If the adjacent points are three-colored, then paint the removed points with the fourth color, and the conclusion will naturally hold; otherwise, the original graph needs to be recolored to try to release this vertex so that its adjacent points can be three-colored. For this purpose, Kemp designed the "Kemp chain" method.

However, 11 years after Kempe's result was published, people discovered a fatal and unfixable error. But Kempe's ideas still provided an important breakthrough for future generations. People continued his method and proved that maps with 22, 39, and 52 countries can be four-color. It was not until 1976 that American mathematicians Kenneth Appel and Wolfgang Haken spent 1,200 hours on two computers at the University of Illinois in the United States to finally complete the proof of the four-color theorem. They continued and improved Kempe's method, completely listed all 1,936 inevitable configurations, and verified their reducibility one by one. This work made a sensation in the world, not only because they proved a difficult mathematical problem, but more importantly, it told people that computers can also be used for mathematical logical proofs. On the day when the two mathematicians made their research results public, the local post office stamped all the mail with a special stamp of "four colors are enough" to celebrate.

Figure 3 For many years after the proof of the four-color theorem was published, the Department of Mathematics at the University of Illinois at Urbana-Champaign stamped its outgoing mail with the postmark "Four Colors Are Enough". Source: las.illinois.edu

Figure 4: Mathematicians Wolfgang Haken (1928-2022) and Kenneth Appel (1938-2013) 丨 Source:
legacy.com/mathyear2013.blogspot.com

In fact, Appel and Haken were not the first to realize the need for computers to help solve the four-color conjecture. As early as 1950, German mathematician Heinrich Heesch predicted that only with the help of powerful computing devices that can process huge amounts of data can the limited but huge number of different configurations in the four-color conjecture be tested. In the era when computer technology had not yet flourished, Heesch's ideas were very advanced. He was the first mathematician to advocate and try to use computers to solve the four-color problem. At the same time, he generously shared many of his ideas with Haken. It can be said that he played a great role in promoting the proof of the four-color conjecture.

Although the research results of Appel and Haken caused a sensation, they were not widely recognized at the time. People's doubts mainly stemmed from the disapproval of computer proof of mathematical problems. Skeptics believed that the method of Appel and Haken was essentially an exhaustive test method. They just used machines to test tens of millions of situations. The details of their proof were hidden in the computer and could not be reviewed by humans. The mathematical community called for a pure and clear mathematical proof. Thirty years later, Georges Gonthier, a young mathematician from the University of Cambridge in the UK, gave a completely computerized proof of the four-color theorem. Unlike Appel and Haken, each step of his logical proof was independently completed by a computer. After years of computer revolution, people gradually recognized the help of computers in mathematical work, and finally were willing to admit that the four-color theorem was established!

Broadcast chromatic number problem: a generalization of the four color problem

In the process of studying the four-color conjecture, mathematicians also thought about other related coloring problems. For example, the most famous Hadwiger-Nelson problem: coloring points on an infinitely large plane so that adjacent points have different colors. What we are going to introduce today is another variation of the four-color problem: the Packing coloring problem, also known as the Broadcast coloring problem. This problem was first proposed by Wayne Goddard, a professor at Clemson University, and others. It actually comes from a very practical problem - the frequency allocation of radio stations.

Figure 5: Radio | Source: Internet

The coverage area of ​​the signal sent by each radio station is limited. The stronger the signal, the wider its coverage area. The frequency modulation (FM) band of the radio is very narrow. The FM range of civilian radios in my country is FM87.5-108MHz. It is obviously impractical if radio stations in every province and city in my country send signals of different frequencies. And the signals of two radio stations with the same frequency will not interfere with each other only if they are far enough apart. For example, the FM frequencies of Tianjin Crosstalk Radio, Shenyang Metropolitan Radio, and Taizhou Traffic Music Radio are all 92.1MHz; and Beijing, which is adjacent to Tianjin, does not allocate a 92.1 MHz signal band in its radio station frequency table to avoid superposition interference of the same signal.

So how do we allocate the frequencies of radio stations in different regions so that we can use the shortest signal band interval to cover the national broadcasting system while avoiding interference? How do mathematicians define this in mathematical language?

Similar to the four color theorem, given a simple undirected graph G=(V, E), we use an integer set K={1,…,k} to represent the color set, and use d(u, ν) to define the distance between two vertices u, ν. Consider the mapping f:V→{1,…,k}, which satisfies that for any two vertices u, ν∈V, and any integer c∈K, if f(u)=f(ν)=c (that is, the colors of vertices u and ν are the same), then the distance between u, ν d(u, ν)＞c (that is, the two vertices with the same color are far enough apart; considering the practical background above, this means that radio stations with the same signal frequency are far enough apart). Such a mapping f constitutes a packing k-coloring scheme, and the smallest integer that satisfies the packing coloring scheme is called the packing coloring number of the graph (packing coloring number) χρ(G).

The packing coloring problem is actually a stronger restriction on the map coloring problem. When K={1}, the packing 1-coloring problem is the most primitive map coloring problem, which requires that the colors of two adjacent vertices are different. Let's take a look at a simple example. Consider the one-dimensional integer axis in the figure below. Take the graph G=Z={0, ±1, ±2,...} as an integer set. Each integer represents a vertex. Two adjacent integers are recorded as two adjacent vertices. The distance between two integers is defined as the absolute value of their difference. The mapping is constructed as follows:

Figure 9: Plus sign area | Source: Reference [8]

As their peers have said: Suvecasseu and Heller are not just solving problems, they are optimizing combinatorics research ideas. With unremitting efforts, they finally solved the planar packing coloring problem after four months.

end

The four-color theorem has troubled the mathematical community for more than a century, and to this day, no real pure mathematical proof has been found. But the significance of the four-color problem goes far beyond the problem itself. More importantly, in the process of successive generations of mathematicians thinking about it, it has led to thinking about other branches of disciplines, such as graph theory, topology, and computer science. People are willing to study the four-color problem not to really fill the map with four colors, but to explore the topological properties and mathematical connotations of the number "4".

As the first mathematical theorem proved with the assistance of computers, the four-color theorem went from being questioned at first to being widely recognized, which destined it to have an extraordinary status in the history of mathematics. With the rapid development of artificial intelligence today, AI-assisted mathematical proofs have become the focus of most scholars. Although some people still believe that AI's formal proofs will destroy the original beauty of mathematics, it is undeniable that advanced technical means have greatly simplified the work of mathematicians. Perhaps what we should question is not the computer itself, but the attitude and method of scholars in using computers.

In his Elements, Euclid defined mathematics in 300 BC in a nearly perfect language, presenting a set of intuitive and rigorous systems to later generations. When time came to the 21st century, people used precise symbols and mechanical rules to translate mathematics into computer codes. Isn’t this also an inheritance and iteration of mathematical culture?

References

[1] Xu Junming. Graph Theory and Its Applications. 3rd Edition[M]. Hefei: University of Science and Technology of China Press. 2010.

[2]Fritsch R. The Four-Color Theorem[J]. American Mathematical Monthly, 1997, 106(8):785.

[3]Gonthier G. Formal Proof—The Four- Color Theorem[J]. American Mathematical Society Notices, 2009(1).

[4] Wang Xianfen, Hu Zuoxuan. Three generations of proofs of the four-color theorem. Journal of Dialectics of Nature. 2010, No. 4, pp. 42-48, 127, 7 pages in total

[5]Goddard, W., Hedetniemi, S., Hedetniemi, S., Harris, J., Rall, D.: Broadcast chromatic numbers of graphs. Ars Comb. 86 (01 2008)

[6]Bre sar, B., Ferme, J., Klav zar, S., Rall, DF: A survey on packing colorings. Discussiones Mathematicae Graph Theory 40(4), 923 (2020)

[7]Subercaseaux, B., Heule, MJH: The Packing Chromatic Number of the Infinite Square Grid Is at Least 14. In: Meel, KS, Strichman, O. (eds.) 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 236, pp. 21:1–21:16. Schloss Dagstuhl – Leibniz-Zentrum fur Infor- ¨ matik, Dagstuhl, Germany (2022)

[8]Subercaseaux, B., Heule, MJH The Packing Chromatic Number of the Infinite Square Grid is 15. arXiv:2301.09757

This article is supported by the Science Popularization China Starry Sky Project

Produced by: China Association for Science and Technology Department of Science Popularization

Producer: China Science and Technology Press Co., Ltd., Beijing Zhongke Xinghe Culture Media Co., Ltd.

Special Tips

1. Go to the "Featured Column" at the bottom of the menu of the "Fanpu" WeChat public account to read a series of popular science articles on different topics.

2. Fanpu provides a function to search articles by month. Follow the official account and reply with the four-digit year + month, such as "1903", to get the article index for March 2019, and so on.

Copyright statement: Personal forwarding is welcome. Any form of media or organization is not allowed to reprint or excerpt without authorization. For reprint authorization, please contact the backstage of the "Fanpu" WeChat public account.