Why does the world map only have 4 colors?

On a world map, how many colors are needed to color adjacent countries different colors?

The answer is four colors.

This is the famous Four Color Theorem in mathematics. This interesting problem, which originally originated from the problem of coloring countries on a map, is known as one of the three major mathematical problems in modern times. It took mathematicians more than 100 years to come up with a real proof, and the computer proof used also entered the mathematical stage.

Today, there are still many interesting problems in graph theory 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 numbers must be greater than the number itself, then how many numbers are needed to cover the entire plane?

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.

World map colored using the four-color theorem. Image source: Standard map service system of the Ministry of Natural Resources

Origin of the Four Color Problem

The story begins in 1852, when Francis Guthrie, a British cartographer, raised a question about "coloring a 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 he was puzzled as to 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. Professor De Morgan tried but was unable to solve the problem, so he wrote a letter to pass the problem on to his good friend, Irish mathematician Professor William Hamilton. Unfortunately, the intelligent 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".

Mathematician Cayley, Image 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 neighbors). 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". He then used induction to remove this vertex and its adjacent edges to obtain a subgraph G'. If this subgraph G' satisfies the four-color conjecture, then the original graph G' is reducible, and the removed vertices and their edges are called "reducible configurations".

Kempe believed 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 are in 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 results were published, people discovered a fatal, irreparable error. But Kempe's ideas still provided an important breakthrough for later generations, and people continued his method to prove that maps with 22, 39, and 52 countries or less can be four-color.

It was not until 1976 that American mathematicians Kenneth Appel and Wolfgang Haken finally completed the proof of the four-color theorem on two computers at the University of Illinois in the United States, spending 1,200 hours. 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 logic proofs. On the day when the two mathematicians made their research results public, the local post office stamped all the mail with a special "four colors are enough" postmark to celebrate.

For many years after the proof of the four-color theorem was published, the University of Illinois at Urbana-Champaign's mathematics department stamped its outgoing mail with "Four Colors Are Enough." Image credit: las.illinois.edu

Mathematicians Wolfgang Haken (1928-2022) and Kenneth Appel (1938-2013), Image 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 cases. 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. 30 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.

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 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 the 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 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:

Therefore, d(-2, 2)=4＞3=f(-2)=f(2). Then χρ(Z)=3.

One-dimensional Packing 3-staining, Image source: Reference [8]

The above example only considers the one-dimensional case. What if we consider the coloring problem of the two-dimensional plane integer set Z2? It can be imagined that for an infinitely large plane, we can divide the plane into grids (like an infinitely large chessboard), and define the distance between two grids as the horizontal distance between them plus the vertical distance. Then how to pack and color them?

In 2008, Goddard and his four collaborators first made public their thoughts on this problem. They used human calculations entirely and concluded that 9 ≤χρ(Z2)≤ 23. Subsequently, several mathematicians used computer-assisted proofs to gradually optimize the result to 13 ≤χρ(Z2)≤ 15.

In 2022, graduate student Bernardo Subercaseaux and professor Marijn JH Heule from Carnegie Mellon University further optimized this result to 14 ≤χρ(Z2)≤ 15. In January 2023, they announced that they had completely solved the packing coloring problem of the planar integer set Z2 - they proved in the article that χρ(Z2)= 15, that is, only 15 numbers from 1 to 15 can fill the entire plane grid, and ensure that the distance between two grids with the same number is greater than this number. Let's briefly introduce their ideas and methods.

Obviously, it is neither practical nor necessary to use exhaustive method for an infinite grid. Therefore, mathematicians thought of verifying a small part of it, such as taking a 10×10 grid and then copying and splicing it. If it can still meet the distance requirements, then the proof is obtained.

Suvecasseu and Heller first simplified the graph from this perspective, but they did not consider a simple rectangle, but started from a finite subgraph Dr(ν)={u∈Z2/d(u, ν)≤r} similar to a rhombus, and used Dr, k to represent the k-packing coloring of the subgraph Dr[(0, 0)], and Dr, k, c to represent the k-packing coloring of the subgraph Dr[(0, 0)] and the center point (0, 0) is assigned color c. If the subgraph Dr(ν) can be k-packing colored, then there must be χρ(Z2)≥k; otherwise χρ(Z2)≥k+1. It is not difficult to imagine that in a finite graph like Dr(ν), the smaller the number, the more times it appears; so in the coloring process, the storage location of larger numbers can be given priority. For example, when r≤k, the number r in the subgraph Dr, k, r will only appear once at the center point (0, 0), otherwise it will violate our distance requirement. This is also the advantage of Dr(ν) compared to rectangular subgraphs. Dr(ν) is actually a regular quadrilateral with good symmetry, so Suecaseus and Heller divided Dr(ν) into eight equal parts (see Figure 7). When coloring, they arranged the larger numbers in the 1/8 angular region in turn, thus avoiding repeated verification of the coloring scheme. D3, 7, 3 in Figure 8 is a very intuitive example.

Divide Dr(ν) into eight equal parts. Image source: Reference [8]

D3, 7, 3 staining, image source: reference [8]

The second simplification made by Suecaseus and Heller is that they no longer simply use the grid point as a coloring unit. They select five adjacent grid points in Dr(ν) to form a plus-shaped area, and color this plus-shaped area as a unit. In other words, you can only consider filling a certain number into this plus-shaped area, but do not consider which grid point in this plus-shaped area to put it. After arranging the coloring scheme of the plus-shaped area, each grid point is colored.

Plus sign area, Image source: Reference [8]

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

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

Planning and production

Source: Fanpu

Author: Han Ying

This article is a work supported by Science Popularization China Starry Sky Project

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

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

Editor: Yinuo