After the emergence of electronic computers, the process of proving the four-color conjecture has been greatly accelerated due to the rapid improvement of calculation speed and the emergence of man-machine dialogue. Harken of the University of Illinois began to improve the "discharge process" in 1970, and then compiled a good program with Appel. 1June, 976, they spent 1200 hours on two different electronic computers of the University of Illinois in the United States, made 1000 billion judgments, and finally completed the proof of the four-color theorem, which caused a sensation in the world.
Non-computer proof of four-color theorem: an application of Poincare theorem
Based on the original topology, graph theory and coloring theory, this paper adds some necessary axioms, theorems and definitions, thus establishing a relatively perfect theoretical system about coloring problems, and using some new methods to prove the four-color theorem of plane graphs on a sphere and a plane. That is, any plane on a sphere or plane has X(G)≤4.
I. Introduction
The reason why the four-color theorem has not been proved by theory for a long time rather than by computer is mainly because a simple and perfect theoretical system has not been established. The axioms, theorems and definitions listed below are mostly needed to prove the four-color theorem, most of which are already in the original topology, graph theory and coloring theory, and few are newly added.
The most important feature of coloring on a sphere or a plane is the occlusion effect of any circle on a sphere or a plane. Similarly, "circle" has such a "blocking" effect on all "simple polyhedrons". However, some "circles" on the "non-simple polyhedron" no longer have this "blocking" effect. This paper proves the "four-color theorem" by using this characteristic.
On the other hand, the mathematician Euler is proving the "Euler Formula" V+F–E = 2 (where V is
The vertex number of a simple polyhedron (e is the number of edges and f is the number of faces) adopts the method of removing lines, faces and points step by step, while this paper adopts the method of adding lines first, then removing points and lines step by step, and finally completes the proof. Although the two methods are not exactly the same, they are all similar.
Second, prepare
Axiom 1: Any direct (directly connected) two points must use different colors. (Note: This paper adopts the method of "point coloring")
Axiom 2: Any two points that cannot be reached directly can be painted with the same color.
Axiom 3: Any "closed circle" on a "plane" or a "sphere" (which refers to a figure composed of several straight lines connected end to end) can divide the "plane" or "sphere" into two parts that cannot be directly reached, that is, the points in this part (that is, the point in this "circle") must pass through the "closed circle" (hereinafter referred to as "closed circle"). Because if "line" and "line" intersect, obviously they cannot be on the same "plane" or "sphere".
Axiom 4: Some "closed rings" (shaped like ordinary lifebuoys) on the torus can't "break the isolation". That is, a point on one side of a circle can reach a point on the other side of the circle without passing through a point on the circle. (This "torus" is actually "seven colors", but this article will not discuss it. )
Theorem 1: Every planar graph without triangles is 3- colorable (that is, X(G)≤3).
(Note: All unproven theorems in this paper are existing theorems in topology and graph theory, such as Theorem 1, Theorem 2, Theorem 3, etc. In addition, the axioms listed in this paper are often used in various books on topology and graph theory, but they are not explicitly listed)
Theorem 2: A graph is bichromatic if and only if it has no "odd cycle".
Theorem 3: The chromatic number of a complete graph K on a "plane" or "sphere" is 4.
Definition 1: If there are some points in an "odd circle" or an "even circle", these points are called "inner dots" of the circle. This "circle" is called the "outer circle" of these points.
Definition 2: If there are some points outside an "odd circle" or an "even circle", these points are called "points outside the circle" of this circle.
In fact, "inside" and "outside" are relative. Especially on the sphere.
Definition 3: If there are some points on an "odd circle" or an "even circle", these points are called "points on a circle".
Definition 4: If there is only one point on a circle, this "circle" is called the "smallest circle" of this point.
Definition 5: If the "coloring number" of the original image does not change after removing a "coloring point", then this point is called a "coloring omission point".
Theorem 4: If there is only one "circle" and one point in a graph, and this point is connected with "points on the circle" respectively, then the chromatic number of this graph is: X(G)≤4.
It is proved that the chromatic number X(G)≤3 is as shown in figure (1) ABCDE ... (according to the theorem 1), after adding a point 0 to the circle, since the point 0 is connected with all points on the circle, the point 0 must take another color different from all points on the circle. So its coloring number should be increased by one, so there is X(G)≤4. Prove it.
Figure (1)
Theorem 5: If a connecting line connecting two disconnected points in the original graph is added to the plane graph, the coloring number of the new graph is not less than that of the original graph.
Proof: If the original colors of the two points connected later are different, the original coloring number remains unchanged after connection. If the original coloring of these two points is the same, it is necessary to change one of the coloring points into another color and readjust the coloring of the whole picture. At this time, the coloring number of the new graph will not be less than that of the original graph. This is because if the chromatic number of the new graph is less than that of the original graph, and the chromatic number of the original graph is n (reduction to absurdity), then the chromatic number of the new graph is N-K, (n and k are positive integers, k)
Prove it.
Theorem 6: Only the triangulation graph with "points on the circle" (that is, there are neither "points inside the circle" nor "points outside the circle") is 3- colorable. That is, X(G)=3.
Proof: As shown in Figure (2), there is a cycle ABCDEFG…… ......................................................................................................................................................... For example, vertices A, B and C are colored with 1, second and third * * * colors, respectively. Then, the vertex D of the next Δ Δ ACD that has a common edge AC with Δ Δ ABC is colored with the second color same as point B. Then, the vertex F of the next Δ Δ ADF that has a common edge with Δ Δ ACD is painted with the third color same as point C. ..... So go on, you can color all the vertices with three different colors. This proves that only the triangulation graph of "points on the circle" is 3- colorable. That is, it is proved that X(G)=3.
Figure (2)
Theorem 6 infers that the chromatic number of a graph with only "points on a circle" is X(G)≤3.
It is proved that adding several connecting lines to the circle on the basis of the original diagram will make it a "triangulation diagram". After doing this, the coloring number of the original image will not decrease (according to Theorem 5). So there is X(G original) ≤X(G new). However, after adding the "connecting line", the coloring number of the new graph increases.
X (gNew) =3 (according to Theorem 6). Therefore, X(G primitive) ≤3 has been proved.
Theorem 7: Any planar graph has chromatic number: X(G)≤5 (this theorem can be omitted when proving the four-color theorem in this paper, but it will be more convenient to describe and prove it in this paper if it is used, and this theorem is proved in all graph theory books).
Theorem 8: Any closed three-dimensional space must be a three-dimensional sphere as long as all the closed curves can be shrunk into one point. (Poincare theorem)
Theorem 8 Inference: Digging a "hole" on a "sphere" becomes a "plane" in the sense of topology. Digging two holes in the sphere becomes a "cylinder" in the sense of topology. No matter how many holes are dug in the "sphere", the "coloring number" on the original "sphere" will not change.
It is proved that if the "periphery" of a finite "plane" is shrunk outward to a point in space, or both the upper and lower bottom surfaces of a "cylinder" are shrunk to a point, it will also become a spherical surface of a three-dimensional sphere. (Poincare Theorem) Therefore, surfaces such as "plane" and "cylinder" are all "spheres" in topological sense, so their coloring numbers must be the same. (end of proof)
Proof of Three-color Theorem and Four-color Theorem
Four-color theorem: For any planar graph on a sphere or plane, there is X(G)≤4.
Prove: (reduction to absurdity)
Suppose that the four-color theorem cannot be established, that is, a plane figure must be colored with five or more colors. That is, X(G)≥5, without loss of generality, can be used as any complex graph, as shown in Figure (3). (Note: Readers can also try to select any other graphics here. ) The solid line part represents a small part of the whole graph, and the dotted line part represents most of the omitted graphs. Its complexity can be arbitrarily constructed and imagined by readers, but it must be a "finite graph" rather than an "infinite graph".
Figure (3)
Then, the chart is processed and analyzed in the following steps:
Step 1: On the basis of retaining all points and connecting lines of the original image, connect as many points in the original image as possible (it should be noted that no new colored points are added, only connecting lines are added) until it becomes a "triangulation diagram". As can be seen from the previous Theorem 5, after this processing, the coloring number of the new graph will not be reduced compared with the original graph, and this step is called "adding lines".
Step 2: Take any "inner dot" in the picture and analyze the "smallest circle" around this point. For example, we take this "point in the circle" as V, and we take V and V and V and V and V and V and V and V … We turn the original graph into a "triangle graph", and the "smallest circle" of V is V-V-V-V, and we adjust and analyze the coloring of this "local graph". According to Theorem 4, we can arrange the smallest "point outer circle" of V in the first, second and third colors for coloring. Arrange v to color the fourth color. If all the "points outside the circle" are recolored, we can know from the assumption that their "coloring number" x(g)≥5, but from the previous "axiom 2" and "axiom 3", we can know that "points inside the circle" and "points outside the circle" cannot be reached directly, so the coloring of V can be adjusted from the original fourth color to the fifth color, and then we can know from the definition 5 that if Doing so will not reduce the "coloring number" of the original image. (Because V is blocked by the "smallest circle" around it, it has nothing to do with the coloring of "points outside the circle". If this reduces the coloring number of the original image, such as reducing the coloring number of the original image from five to four, it means that the coloring number of the original image should be four. ) This step is called "removing points" and "removing lines". (At this time, the V point is a "colored ellipsis point". Since the V point has been removed, the line directly connected with it is naturally unnecessary. Because this paper adopts the method of point coloring. )
Step 3: Repeat the first step of "adding lines" or the second step of "removing points" and "removing lines" for other "inner points" in the diagram (which can be used alternately or not) until there are no more "inner points" to go. Finally, it becomes a "triangle diagram". Because "points" decrease one by one, and "inside the point" and "outside the point" are relative. So the final result can only be as shown in Figure (1) or Figure (2), that is, a diagram with only one circle and only one point in it (at this time, the points in the circle are connected with the points on the circle) or a triangulation diagram with only the points on the circle. But the "coloring number" x (g) at this time is less than or equal to 4. This obviously contradicts the initial assumption that X(G)≥5, so the initial assumption that X(G)≥5 is wrong. So the chromatic number X(G)≤4 on the "sphere" or "plane" is true. Prove it.
In order to facilitate readers to better understand this proof, readers can choose more graphics, from simple to complex, and repeat experiments and thinking according to the method provided in this paper (that is, the three steps in the proof), so that they can realize the incomparable mystery and correctness of this proof.
Fourth, explain in detail.
In order to make readers better understand the thinking of this article, I want to make some supplementary explanations. The main idea of this paper is to analyze and deal with the "circle", "inner point" and "outer point" of the "partial map" in the "full map". The "triangle" in the "triangle" map is essentially a "circle" composed of three points. If there is a "circle" composed of more than three points in the diagram, it can be made into a "triangle diagram" by adding lines, and then analyzed. If there is a "circle" composed of two points or a "circle" composed of one point in a graph (for example, if one area surrounds another area), although it was not mentioned in the last article, its analysis and processing method can be exactly the same as that of a "circle" composed of three points. It's hard for me to find it.