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 20th 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” G5 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 G5 (he has proved that the country u has no more than five neighbors).
Suppose that there are n countries in G5, 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 G5 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 v1, v2, v3, v4, as shown in Figure 2. The reason why edges v1v2, v2v3, v3v4, v4v1 exist in G is that if anyone of
them are missing, such as v1v2 is missing, then the graph obtained by combining v1 and v2 into v12 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-uv1, Gd = G" [{v2, v3, v4}], G1 = G" [{All the vertices of G being adjacent to v1}], G24 = G" − G1 − v1 − v3 − u + v2 + v4,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 v1 must always be colored the same color, otherwise, as long as we put uv1 back between u and v1, 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 v1 was colored red”, D = “all of the vertices of Gd were colored yellow, green and blue”, D' = “all of the vertices of Gd were colored some two colors of yellow, green and blue”, E = “all of the vertices of G1 were colored yellow, green and blue”, H = “all of the vertices of G24 were colored the colors to make E true”, K = “all of the vertices of Gd 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 v1 were colored different colors, it will be inconsistent with the aforementioned inference that u and v1 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 Gd, G24, G1 and v1 in turn. According to the position relationship
![]()
Figure 3. If the edge v1v2 is missing, the graph can become 4-colorable.
![]()
Figure 4. When G" can be 4-colored, u and v1 must always be colored the same color.
between u, Gd, G24, G1 and v1, 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 Gd. In the latter case, the color of one of yellow, green and blue that was not colored at the vertices of Gd can be colored at u, but which contradicts the inference that u and v1 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 Gd, otherwise, A is true but Gd 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 Gd that v2 must adjacent to v4.
In the same way, it can also be inferred that v1 must adjacent to v3, 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 v1, v2, v3, v4, v5. Similar to the case of deg(u) =4, edges v1v2, v2v3, v3v4, v4v5 and v1v5 should exist, as shown in Figure 6.
Let Gd = G" [{v2, v3, v4, v5}]. Similarly with the case of deg(u) = 4, it can also be proved that there is odd circle in Gd, so either v2 is adjacent to v4 or v3 is adjacent to v5. If v2 is adjacent to v4, it can similarly be proved that either v1 is adjacent to v4 or v2 is adjacent to v5. In addition, if v1 is adjacent to v4, it can similarly
![]()
Figure 5. Shows the result of contradiction with intersecting edges in G.
![]()
Figure 7. Shows the result of contradiction with intersecting edges in G.
be proved that either v1 is adjacent to v3 or v2 is adjacent to v5. So that there are contradictory results of edges intersection in G, as shown in Figure 7.
Similarly, it can be proved that when v2 is adjacent to v4 and v2 is adjacent to v5.
Similarly, it can be proved that when v3 is adjacent to v5. 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.