A Logical Proof of the Four Color Problem

Show more

1. Introduction

The Four Color Conjecture (hereinafter referred to as 4CC), also known as the Four Color Problem, was first proposed by Francis Guthrie, an Englishman, in 1852 [1] [2] [3]. Its description is as follows:

Give you a map of several countries. No neighboring countries can be colored the same color. Is it enough to use only four colors? Or is there a map that requires at least five colors?

Since the advent of 4CC, there are a lot of solvers. One of the early pioneers was Percy John Heawood, who has proved the Five Color Theorem, that is, any map at most five colors is enough [4] [5]!

Between 1878 and 1880, Alfred Kempe and Peter Guthrie Tait, respectively, announced that they had proved 4CC.

In 1890, Percy John Heawood pointed out Kempe’s holes in his proof. Soon Tait’s proof was disproved too. They were found to have actually proved a weaker proposition, the Five Color Theorem.

In the 20^{th} century, mathematicians proved 4CC, one after another, based on Kempe’s ideas of “configuration” and “reducibility”. In 1913, American mathematician Birkhoff combined Kempe’s ideas with his own new ideas to prove some large configurations are reducible. Whereafter, mathematicians have been proved, that maps within 22 countries could be colored with four colors in 1939, that maps within 35 countries could be colored in four colors in 1950, that maps within 39 countries could be colored in four colors in 1960, and that maps within 52 countries could be colored in four colors in 1975.

In 1976, news came from the United States that Kenneth Appel and Wolfgang Haken had proved 4CC by use of computer [6]. But a fair number of people still hope to find some kind of artificial proof of 4CC.

2. Methods

This paper is based on Kempe’s work.

Kempe was used to prove 4CC by means of reduction to absurdity. The main idea is that if there are five color maps, there will be at least one “minimal five color map” G_{5} with the least number of countries.

Kempe first proved the conclusion of a planar graph: in any map, there must be a country whose neighbors number is less than or equal to 5.

Kempe then looked at the country u which with the smallest number of neighbors in G_{5} (he has proved that the country u has no more than five neighbors).

Suppose that there are n countries in G_{5}, and if country u do not have more than 3 neighboring countries, then it can be removed first, forming a map with only n − 1 countries. The map should be 4-colored. The original three neighbors of country u have used at most three colors. At this time, if country u is put back and be colored the color which was not used by its neighboring countries will make the minimal five color map G_{5} becomes 4-colored again, see Figure 1.

This kind of subgraph, which can “eliminate” a country and reduce the number of colors, was later called “reducible configuration”.

3. Research Idea

Kempe’s proof puts forward two important concepts and lays the foundation for further solving 4CC.

Figure 1. Country u and its three neighboring countries.

Kempe’s first concept was “configuration”. He first proved that there must be a country on any map whose number of neighbors is five or less. In other words, a set of “configurations” of one to five neighbors is inevitable on each map.

Another concept proposed by Kempe is “reducibility”. Kempe showed that as long as a minimal five color map has one country with four or fewer neighbors, there will be a smaller five color map, so there won’t be a minimal five color map.

Since the concepts of “configuration” and “reducible” were introduced, some standard methods for checking the configuration of a graph to determine whether it is reducible have been developed. Seeking the inevitable group of reducible configurations is an important way to prove 4CC.

The first half of this paper, like Kempe’s proof idea, starts with the assumption that there is a minimal five color map (in this paper, it is called critical five color map) G, and then proves, by analyzing the logical relationship existing in the four color coloring of graph G or its related subgraphs in turn, the “configuration” composed of four or five neighboring countries in graph G is reducible, which is proved, by the method of reduction to absurdity, the 4CC holds.

4. Labels and Concepts

In this paper, δ is used to represent the minimum degree of the vertices of a graph.

If V is the set of all the vertices of a graph G and V’ is a non-empty subset of V, then the induced subgraph of graph G induced by V’ is represented by G[V’].

A n-color graph but not (n − 1)-color graph is a critical n-color graph if any vertex or edge of which is subtracted, it will become a (n − 1)-color graph.

5. Results

The Four Color Theorem: All planar graphs can be 4-colored.

Proof: Use the method of reduction to absurdity. If this theorem is not valid, then there should be 5-color graphs in planar graphs [7] [8] [9]. Let G is a critical 5-color graph. Then, it can be proved that δ = 4, 5 in G [10] [11]. Now assume deg(u) = δ In G, and consider the situations of deg(u) = 4, 5 in turn.

When deg(u) = 4, set the vertices adjacent to u as v_{1}, v_{2}, v_{3}, v_{4}, as shown in Figure 2. The reason why edges v_{1}v_{2}, v_{2}v_{3}, v_{3}v_{4}, v_{4}v_{1} exist in G is that if anyone of

Figure 2. deg(u) = 4.

them are missing, such as v_{1}v_{2} is missing, then the graph obtained by combining v_{1} and v_{2} into v_{12} is G', as shown in Figure 3. Because of the number of edges of G' is less than G, G' should be a 4-colorable graph. In this case, as long as G' is changed back to G, we can get 4-colored G, which contradicts the hypothesis that G is a critical 5-color graph.

Let G" = G-uv_{1}, G_{d} = G" [{v_{2}, v_{3}, v_{4}}], G_{1} = G" [{All the vertices of G being adjacent to v_{1}}], G_{24} = G" − G_{1} − v_{1} − v_{3} − u + v_{2} + v_{4},Since the number of edges of G" is less than G, G" should be a 4-colorable graph. It is easy to know that when we make 4-coloring for G", u and v_{1} must always be colored the same color, otherwise, as long as we put uv_{1} back between u and v_{1}, we can get 4-colored G, which contradicts the hypothesis that G is a critical 5-color graph, as shown in Figure 4. In other words, when using color group C composed of red, yellow, green and blue to make 4-coloring for G"_{,} let A = “vertex u was colored red”, B = “vertex v_{1} was colored red”, D = “all of the vertices of G_{d} were colored yellow, green and blue”, D' = “all of the vertices of G_{d} were colored some two colors of yellow, green and blue”, E = “all of the vertices of G_{1} were colored yellow, green and blue”, H = “all of the vertices of G_{24} were colored the colors to make E true”, K = “all of the vertices of G_{d} were colored the colors to make H true”, M = “vertex u was colored the color to make K true”. So first of all, A is a sufficient condition for B. Because if A is true but B is false, that is, u and v_{1} were colored different colors, it will be inconsistent with the aforementioned inference that u and v_{1} must always be colored the same color when make 4-color coloring for G" [12]._{ }

According to the foregoing sufficient condition that A is B, B must also be true when red is first applied to u to make A true, and then make 4-colors coloring to G_{d}, G_{24}, G_{1} and v_{1} in turn. According to the position relationship

Figure 3. If the edge v_{1}v_{2} is missing, the graph can become 4-colorable.

Figure 4. When G" can be 4-colored, u and v_{1} must always be colored the same color.

between u, G_{d}, G_{24}, G_{1} and v_{1}, in the aforementioned coloring process, B depends on and only depends on E, E depends on and only depends on H, H depends on and only depends on K, and K depends on and only depends on M. Since A is the only coloring for u in the aforementioned coloring process, so M=A. In addition, in the aforementioned coloring process, there are two cases of K=D or K=D' for G_{d}. In the latter case, the color of one of yellow, green and blue that was not colored at the vertices of G_{d} can be colored at u, but which contradicts the inference that u and v_{1} must always be colored the same color when make 4-colors coloring for G". Therefore, the former case can only be established, that is, K=D. Thus, the foregoing K depends on and only depends on M can be rephrased as D depends on and only depends on A. But this is obvious only if there is odd circle in G_{d}, otherwise, A is true but G_{d} can be a 2-colorable graph [13], that is, D is false, thus contradicting the inference that D depends on and only depends on A.

It follows from there is odd circle in G_{d} that v_{2} must adjacent to v_{4}.

In the same way, it can also be inferred that v_{1} must adjacent to v_{3}, and resulting in the contradictory result that there are at least two edges intersect in G, as shown in Figure 5._{ }

When deg(u) = 5, let the vertices adjacent to u are v_{1}, v_{2}, v_{3}, v_{4}, v_{5}. Similar to the case of deg(u) =4, edges v_{1}v_{2}, v_{2}v_{3}, v_{3}v_{4}, v_{4}v_{5} and v_{1}v_{5} should exist, as shown in Figure 6.

Let G_{d} = G" [{v_{2}, v_{3}, v_{4}, v_{5}}]. Similarly with the case of deg(u) = 4, it can also be proved that there is odd circle in G_{d}, so either v_{2} is adjacent to v_{4} or v_{3} is adjacent to v_{5}. If v_{2} is adjacent to v_{4}, it can similarly be proved that either v_{1} is adjacent to v_{4} or v_{2} is adjacent to v_{5}. In addition, if v_{1} is adjacent to v_{4}, it can similarly

Figure 5. Shows the result of contradiction with intersecting edges in G.

Figure 6. deg(u) = 5.

Figure 7. Shows the result of contradiction with intersecting edges in G.

be proved that either v_{1} is adjacent to v_{3} or v_{2} is adjacent to v_{5}. So that there are contradictory results of edges intersection in G, as shown in Figure 7._{ }

Similarly, it can be proved that when v_{2} is adjacent to v_{4} and v_{2} is adjacent to v_{5}.

Similarly, it can be proved that when v_{3} is adjacent to v_{5}. This proves the theorem.

6. Conclusion

Since 4CC was put forward, although many top mathematicians and others have made unremitting efforts, there has been no artificial, that is, non-computer, proof. On the basis of Kempe’s work, this paper adopts the method of reduction to absurdity, and takes the inevitable configuration of four or five adjacent vertices in the assumed existence of critical 5-color graph as the breakthrough point, with the help of careful logical analysis, the non-computer proof of the Four Color Theorem was established and the long cherished wish of the common people was realized.

Acknowledgements

In the process of completion, I received the help of Prof. Yin Jianhua from Hainan University, and I would like to take this opportunity to express my thanks to him.

References

[1] Project on the Compilation and Application of Scientific Encyclopedia of Popular Science in China, Four Color Theorem. http://url-4.cn/2h2uN

[2] Lang, M.F. (2014) Four Color Theorem.
http://www.360doc.com/content/14/1012/08/5874842_416237212.shtml

[3] Simon. S. (1998) Fermat’s Last Theorem. Shanghai Translation Publishing House, 264-274.

[4] Stein, S.K. (1975) Mathematics: The Man-Made Universe. W. H. Freeman and Company, 336-355.

[5] Brualdi, R.A. (1977) Introductory Combinatorics. Elsevier North-Holland, Inc., 271-302.

[6] Steene, L.A. (1982) Mathematics Today. Shanghai Science and Technology Press, 174-203.

[7] Ouyang, G.-Z. (1981) The Problem of 4-Color Map. Popular Education Press, 29-36.

[8] Hilary, F. (1980) Graph Theory. Shanghai Science and Technology Press, 119-172.

[9] Zuo, X.-L., Li, W.-J. and Liu, Y.-C. (1982) Discrete Mathematics. Shanghai Science and Technology Literature Press, 271-320.

[10] Bondy, J.A. and Murty, U.S.R. (1982) Graph Theory with Applications. Macmillan, 117-170.

[11] Harju, T. (1994) Graph Theory. University of Turku, 43-60.

[12] Copi, I.M. and Cohen, C. (1982) Introduction to Logic. 11th Edition, Renmin University of China Press, 211-482.

[13] Dossey, J.A., Otto, A.D. and Spence, L.E. (2007) Discrete Mathematics. 5th Edition, Mechanic Industry Press, 197.