A Proof of the Four-Color Problem based on a New Law of Logic the Law of the Middle Term

I. 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]. The most famous previous proof of this problem was made by Kenneth Appel and Wolfgang Haken in the United States in 1976 using computers [2]. Afterwards, there are still a considerable number of people hoping to find an artificial proof of this problem. My paper titled "A Logical Proof of the Four-Color Problem [3]" was published in the Journal of Applied Mathematics and Physics in May 2020. Later, it was found that the key logical proof part can form a new logical law — the law of the middle term. This paper aims to give a proof of the 4CC based on the law of the middle term in logic proposed in this paper, so that the proof idea is clearer, the proof process is more rigorous, and more concise. While solving the problem of graph theory, also made a little contribution to the development of logic.

II. METHODS

This paper is based on Kempe's work.

Kempe once tried to prove 4CC by means of reduction to absurdity. The main idea is that if there are five color maps, there will at least be a "minimal five color map" with the least number of countries.

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

Next, Kempe looked at the country with the least number of neighbors in the minimal five color map — country u (he had proved that country u has no more than five neighbors). Suppose there are n countries in . If there are no more than 3 neighbors of country u, it can be "removed" to form a map with only n-1 countries, which should be 4-colorable. The original three neighbors of country u used at most three colors, such as red, yellow and green. At this time, put the country u back and color it with the color unused by its neighbors, such as blue, so that the minimal five color map can be 4-colored again, see Figure 1.

Figure 1: Country u owned three neighboring countries.

This kind of subgraph that can reduce the number of map colors by "removinG* and "restorinG* a country is later called "reducible configuration".

III. RESEARCH IDEA

Kempe's work putted forward two important concepts, which laid the foundation for further solving 4 CC in the future.

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 found in his research that the chromatic number of relevant maps can be reduced by "removinG* and "restorinG* a country in some subgraphs. Since the introduction of the concepts of "configuration" and "reducibility", 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 part of the proof of this paper is the same as Kempe's proof idea. It starts with the assumption that there is a minimal five color map (called 5-critical graph in this paper) G, then analyzes the logical relationship between graph G's related subgraphs when they are 4-coloring, and then uses the law of the middle term based on logic proved in this paper, it is proved that the necessary configurations composed of four or five neighbors in graph G are reducible, so 4CC is proved to be true by means of reduction to absurdity.

IV. LABELS AND CONCEPTS

In this paper, is used to represent the minimum degree of the vertices of a graph; use PA to express a proposition about something A; use PA PB to represent the sufficient condition that PA is PB. 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(The so-called induced subgraph is a subgraph composed of some vertices in a certain graph and all the edges connecting these vertices in the original graph).

A coloring of a graph is to assign a set of colors to each vertex so that no two adjacent vertices have the same color. The set of all vertices with the same color is independent and is called a color group. An n-coloring of graph G is a coloring with n colors, according to this coloring, all its vertices are divided into n color groups.

Among all the colorings of a certain graph G, the color number of the coloring with the least color is called its chromatic number, denoted as . if , graph G is called n-colorable or n colorable graph; if , G is called n-color or n-color graph.

A graph G is said to be critical if for all its vertices or edges v/e, ; if , Then G is called an n-critical or n-critical graph.

V. THE LAW OF THE MIDDLE TERM

The law of the middle term: if , but PA acts on PC through and only through B, then there must be a PB such that and .

Proof: If this law does not hold, that is, if PA → PC, when PA acts on PC through and only through B, for any PB, it is all not "PA → PB and PB → PC", that is, neither of them is PA → PC, then obviously this would contradict the premise PA→PC.

VI. RESULTS

The Four Color Theorem: For all planar graph , .

Proof: Use the method of reduction to absurdity. If this theorem is not valid, then there should be 5-color graphs in planar graphs [4][5][6]. Let G is a 5-critical graph, and let u be the vertex with the smallest degree, that is, , it can be proved that [7][8] in G.

Figure 2: .

When , set the vertices adjacent to u as , , , , as shown in Figure 2. The reason why edges , , , exist in G is that if anyone of them are missing, such as is missing, then the graph obtained by combining and into 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 5-critical graph.

Figure 3: If the edge is missing, the graph can become 4-colorable.

Let , , Since the number of edges of is less than , should be a 4 color graph. It is easy to know that when we make 4-coloring for , u and must always be colored the same color, otherwise, as long as we put back between u and , we can get a 4 colored , which contradicts the hypothesis that is a 5-critical 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 , If Pu is used to represent "u is red" and is used to represent " is red", first, . Otherwise, if Pu is true and is false, that is, u and are different in red, which will contradict the above inference that when we make 4-coloring for , u and must always be colored the same color [9].

Figure 4: When we make 4-coloring for G*, u and v1 must always be colored the same color.

Secondly, when using color group C to color , if Pu is true, that is, u is red, then from the above inference, will also be true, that is, will also be red with u. It is known from the law of the middle term and , and Pu acts on through and only through that, at this time, for , there must be a coloring , making and . But in the aforementioned coloring process, obviously can have "On all vertices of have all the three colors of yellow, green and blue" and "On all the vertices of have only some two colors of the three colors of yellow, green and blue". But obviously cannot including the latter case, otherwise it is only necessary to change the red of u to another color among the three colors of yellow, green and blue that are not used on all vertices of , so that u and are different colors, so that it contradicts the inference that "when 4-coloring , u and must be the same color". Thus, in this case, can obviously only be the former case, that is, on all vertices of have all the three colors of yellow, green and blue. But this is obviously only possible if there are odd circles in [10].

It follows from there is odd circle in that must adjacent to .

In the same way, it can also be inferred that must adjacent to , so that there is a contradictory result of edge intersection in G, as shown in Figure 5.

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

, let the vertices adjacent to u are , , , , . Similar to the case of , edges , , , and should exist, as shown in Figure 6.

Figure 6: deg(u) = 5. Let

, it can also be proved by imitating the situation of : there must be an odd cycle in Gd, therefore, either is adjacent to , or is adjacent to . If is adjacent to , it can be deduced in the same way that in G, either is adjacent to , or is adjacent to . And if is adjacent to , it can be deduced in the same way that in G, either is adjacent to , or is adjacent to , so that there is a contradictory result of edge intersection in G, see Figure 7.

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

Similarly, it can be proved that when is adjacent to and is adjacent to . Similarly, it can be proved that when is adjacent to . This proves theorem.

VI. CONCLUSIONS

On the basis of my previous relevant proofs, this paper refines the key logical proof part into a new logical law called the law of the middle term, which makes the proof thinking clearer, the proof process more rigorous, and more concise. While discussing difficult problems of graph, it also made a little contribution to the development of logic.