Proof of the Four Color Problem
- S Y
- 2021年7月24日
- 読了時間: 7分
0. 参考文献
[1]Encyclopedia Mypedia
Copyright (c) Heibonsha Limited, Publishers, Tokyo. All rights reserved.
[2] Coloring problem: Masaya Ohashi and others
1. What is the Four Color Theorem?
In any planar graph, there is a conjecture that the minimum number of colors needed to paint adjacent closed regions would be four, which is called the four-color problem. In 1976, W. Haken and K. Appel completed the proof using a computer. By the way, there is still no proof by logic. [1], but in honor of the two who proved it, we will call it the Four Color Theorem.
2. What is the Five-Color Theorem?
It is a theorem that states that five colors are sufficient to paint adjacent closed regions in a planar graph, and was proved by Percy Healywood in 1890. Euler's polyhedron theorem was used in the proof. [2] 3.
3. proof of the Four Color Theorem
In this article, I would like to try to prove the Four Color Theorem in a non-computerized way. If you have any suggestions, please feel free to comment.
3.1 List of figures used in this chapter
Fig.1
Fig.2
Fig.3
Fig.4
Fig.5
Fig.6
Fig.7
Fig.8
Fig.9
Fig.10
Fig.11
3.2 Disconnected Vertex Counting Method
Consider a graph in which the region to be filled is a vertex, and the connections are redrawn as edges. In this case, we examine the number of vertices that are not directly connected to themselves by an edge. However, we will ignore vertices that are not connected to any edges (isolated vertices).
Let's take Figure 1 as an example. Vertices A, B, C, and D are unconnected to vertices C, D, A, and B, respectively. Therefore, each of them can be counted as (1,1,1,1).
Let's take Figure 2 as an example. Vertices A, B, C, and D are disconnected from each other and from vertices C,(NaN), and A,(NaN), respectively. Here, (NaN) means the empty set. From the above, we can calculate the number of vertices to be (1,0,1,0).
Next, let's rank the vertices in order of decreasing number.
In the case of Figure 1
First place: A, B, C, D
Figure 2
1st : B,D
Second place: A, C
3.2 Linear (no closed curve)
In the linear case, we can consider Figure 3. Performing the disjoint vertex counting method on this figure, we get the following result.
(A, B, C, D, E, F, G) = (5, 4, 2, 5, 5, 4, 5)
Ranking gives the following results
First place: C
2nd : B,F
3rd place: A, E, D, G
Note that there is a third place at this point.
Now let's consider them as two line segments that interfere with each other at only one point.
Example
Line segment α: A→B→C→D
Line segment β: E→F→C→G
For each line segment, the following results are obtained by performing the disjoint vertex counting method.
Line segment α: (A, B, C, D) = (2, 1, 1, 2)
Line segment β: (E, F, C, G) = (2, 1, 1, 2)
We ranked each of them.
Line segment α
1st : B, C
2nd : A, D
Line β
1st : F, C
2nd : E, G
We notice that vertex C is ranked first in all the line segments. In fact, since many vertices are connected to the intersection of the line segments, it is easy to get a high ranking.
Also, in the ranking, the vertex with the highest ranking can place more restrictions on other vertices. On the contrary, the lower the ranking vertex is, the more strongly it indicates the nature of the entire graph.
In other words, if we start with a vertex of high rank, such as an intersection, we can easily paint over it.
In the case of line segments, the degree of a vertex is 1 or 2. Therefore, in the ranking, all vertices are ranked to the second place.
This leads to the following theorem.
Theorem: If you graph a surface to be painted, and it is a line segment, it will be painted with at most two colors. If the surface to be plotted is a line segment, it can be plotted with at most two colors, and if it is a line segment, it can be plotted with at most two colors.
3.3 The case of a single closed curve (no center point)
3.3.1 Observation
Consider a closed curve with several vertices, as shown in Figures 4 and 5.
In this case, we examine the evenness of the number of vertices of the same rank.
Since the curve is closed, rotational symmetry holds regardless of the number of vertices. Therefore, all vertices are equal in rank.
Furthermore, if the number of vertices is even, as shown in Fig. 4, we can achieve a linearly symmetric arrangement with a straight line that does not pass through any vertex. In this case, one of the lines divided by the symmetrical lines will be a linear line as described in 3.2, which means that it can be painted with two colors. The other side can be painted in two different colors as well. However, we need to make sure that the starting point and the ending point of each color are different from each other when we select them.
If the number of vertices is odd, as shown in Fig. 5, it is possible to achieve a line symmetrical arrangement with a straight line passing through one vertex. In this case, the vertices that do not have a straight line passing through them can be considered in the same way as when the number of vertices is even. However, for the vertices through which the line passes, a third color is required as a result. This is because the colors at both ends are different from each other.
3.3.2 Disconnected Vertex Counting Method
Regardless of whether the number of vertices is even or odd, the rankings will be tied for first place.
3.4 The case of a single closed curve without a center (with a center point)
3.4.1 Observation
Consider a closed curve with several vertices and one vertex at its center, as shown in Figures 6 and 7.
Here, a closed curve that does not pass through the center means a closed curve that does not pass through the vertex (center point) that is connected to all vertices.
In this case, one color has already been given to the center vertex, so we need to add one more color to the result in 3.3. In other words, if the number of vertices of the closed curve is even, it will be painted with three colors, and if the number of vertices is odd, it will be painted with four colors (Condition 3.4.1).
We now explain the following theorem.
Theorem
The properties of a graph with vertices that are not connected to the central point, as shown in Figures 8 and 9, are the same as those of a closed curve connected across such vertices. In other words, in Figure 8, we can regard the closed curve A→B→C→D→G→A as A→D→G→A, and in Figure 9, we can regard the closed curve A→E→D→G as A→G→D.
Proof
In Figure 8, we can regard the closed curve A→B→C→D→G as A→D→G, and in Figure 9, we can regard the closed curve A→E→D→G as A→G→D with no center point. In Figure 8, three colors are required for the closed curve A→B→C→D→G because it has five vertices, and two colors are required for the closed curve A→E→D→G because it has four vertices. The above conditions are equivalent to or weaker than condition 3.4.1, so we do not need to consider them.
3.4.2 Non-connected Vertex Counting Method
The vertex that is not connected to the center point is the lowest, the center point is the first, and the vertex that is connected to the center point is the second. All vertices are ranked within the second or third place. (*1)
1 We will prove this in 3.6.
3.5 Multiple closed curves not passing through the center (with center point)
Consider the case of multiple overlapping closed curves as shown in Fig. 10. (ABCDE, FGHIJK) In this case, some of the vertices may not be in the top three. However, if you look closely, you will see that there are several overlapping closed curves as explained in 3.4, "The case of a single closed curve not passing through the center (with a center point)". In other words, we can find a closed curve centered at a vertex connected to the center point.
For example, in Figure 10, point O is the center, and point C connected to it is the center of BODHG, and point A is the center of FBOEK. Each of these gives condition 3.4.1, which is the strongest condition.
Thus, the case where there are multiple closed curves that do not pass through the center can be considered in the same way by finding a vertex that gives the case where there is only one closed curve that does not pass through the center (with a center point).
3.6 In the case of a single closed curve that does not pass through the center (with a center point), is there any vertex that ranks after the fourth?
The following discussion applies to the case where vertices other than K, L, and M are connected to the center O. (*2) In Fig. 11, we consider eliminating any of the edges A, B, C, D, and E to change their rank. Also, due to the nature of the problem, we do not need to consider that a vertex is not connected to any one edge as well. Furthermore, we assume that the edges are continuous.
Currently, the values using the disjoint vertex accounting method are as follows
The following table summarizes how the values from the unconnected vertex accounting method for each vertex change when an edge is removed.
Select the edges to be removed, being careful not to isolate any vertices. The edges should be continuous.
The combinations are as follows
(Choose one)
A~E
(Choose two)
A・(C,D,E)
B・(C,D,E)
C・(D,E)
(Select three or more)
This method is inappropriate because isolated vertices appear.
The values using the unconnected vertex accounting method are as follows, respectively
From the above, we can see that in the case of a single closed curve that does not pass through the center (with a center point), there is no vertex that ranks higher than 4th.
Vertex 2
By adding a new vertex, another loop may appear, or a linear figure may appear in the loop, but by considering the loop and the linear figure separately, we can discuss them in the same way as before adding the vertex.
4. summary
By ranking the vertices using the disjoint vertex counting method, we have grasped the properties of the graph (how many vertices in the graph are ranked).
We also considered the results of the disjoint vertex counting method by classifying them into linear, loop (no center point), loop (with center point), and loop multiple (with center point). Then, we found that by focusing on "what is the lowest rank of the vertex counting result" and "are the vertices that make loops even or odd", we could give a solution as to what color they can be divided into.
Furthermore, we found that for all the vertices of the graph, the form result was in the top three at most.
We also found that the condition of being in the top three and having an odd number of vertices is the strongest and requires four colors.
From the above, we can reaffirm the following theorem.
"In any planar graph, the minimum number of colors required to paint adjacent closed regions is four."
©︎2021 Yume Isioto
Comments