|
|
四色定理的非计算机证明(英文稿)
Non-computer Proof on the Four Color Theorem -An Application of Poincare Theorem
He Zongguang (College of Zhejiang Science and Technology Engineering)
He Zongming (Shanghai No.5 Medical Instrument Factory)
Abstract
In addition to the original topology, graph theory, and coloring theory as a base, this article includes some indispensable axioms, theorems and definitions thus establishing a relatively perfect theoretical system on the coloring issue, and using some new methods to prove the four color theorem for ichnograph in the spherical surface and in the plane. Namely for any ichnograph in the spherical surface or in the plane, X(G)≤4 does always exist.
Key words
Closed loop, Disjunction and isolation, Coloring point that can be omitted, Triangulated graph, Adjustment and analysis of coloring, Adding line, Removing point, Removing line
1. Introduction
The successful proof of a theorem must depend upon a perfect theoretical system,in which there are possibly fewer but enough axioms, basic concepts as well as the theorems, definitions, formulas and so on. The absence of any link will make the demonstration difficult. For a long time, due to the lack of a condensed and perfect theoretical system, no academic proof based on a non-computer approach has been given to The Four Color theorem. The following axioms, theorems and definitions are necessary to prove the Four Color theorem, and most of them originally exist in topology, graph theory, and coloring theory, with few ones added here.
The most important characteristic in the coloring issue either in the “spherical surface” or in the “plane” is the “interdiction” effect of any “loop” in the “spherical surface” or in the “plane”. Similarly, all “loops” also have the “interdiction” effect on all "the simple polyhedron”while some no longer this effect on "the non- simple polyhedron”. This article just uses this characteristic to prove successfully the "Four Color Theorem".
On the other hand, when proving "Euler formula" V+F–E=2 (where V is the vertex number of the "simple polyhedron", E is the "edge number" and F is the "surface number"), Euler uses the method of gradually “removing line”, “removing plane” and “removing point”; While in this article, the method of “adding line” is first used, then done with “removing point” and “removing line” for more than once gradually till the proof is completed in the end. These two methods are not exactly the same, but actually have some similarities.
2. Propaedeutics
Axiom 1: Any two directly accessible points (that can be directly joined) must be colored differently. (Note: This article uses “Point Coloring” method).
Axiom 2: Any two points that are directly inaccessible may be colored in the same color.
Axiom 3: Any closed loop (Referred to as the graph which consists of “lines” connected in head-to-end manner) in the “plane” or in the “spherical surface” can divide the “plane” or the “spherical surface” into two parts indirectly accessible to each other. That’s to say, the point in one part (namely in the “loop”) should go through the “closed loop” (loop for short in the following) to get to the point in the other part (namely outside the loop) (in the coloring question, “lines” can not overlap with each other, because the overlapped lines obviously can not be in the identical " plane" or " spherical surface".)
Axiom 4: Some “closed loops” cannot play the role of “disjunction and insulation” in “ring surface” (shaped as a regular life buoy). Namely "the point" on one side of "the loop" may get to the point on the other side without passing through the points in "the loop"(this kind of “loop surface” actually is “seven-coloring”. But no discussion on this will be given in this article).
Theorem 1: Each ichnograph without any triangle can be three-coloring (namely X (G) ≤3).
Note: In this article, the theorems that don’t have the accompanying proof are those already existing in “Topology” and “Graph theory”, such as the theorem 1, 2, and 3 and so on. Moreover all the listed axioms in this article have been used in various books on topology and graph theory and they are not accurately listed.
Theorem 2: A graph is two-coloring when and only when it does not have “odd loop”.
Theorem 3: In the “plane” or in the “spherical surface”, the coloring number of a complete graph K is four.
Definition 1: There are some points in the “odd loop” or “even loop”, and these points are called the “point in the loop”. And the “loop” is called the “loop outside the points”.
Definition 2: There are some points outside an “odd loop” or “even loop”, and these are called “point outside the loop”.
In fact, the "in" and "outside" is defined relatively, and this is especially obvious in "the spherical surface".
Definition 3: There are some points on the “odd loop” or “even loop”, and these points are called “point on the loop”.
Definition 4: If there is only one point in the loop, the “loop” is called the “minimum loop” of the point.
Definition 5: If after the removing of a certain “colored point” the “coloring number” of the original graph does not change, then the point is called “Coloring point that can be omitted”.
Theorem 4: If there is a “loop” in a graph, and with only one point in the loop, (as in the figure (1)) and there is no any point outside the loop and the point is connected with all the “points on the loop”, then the coloring number of this graph: X (G) ≤4.
Proof: As in the figure (1) the coloring number of ABCDE...... is X(G)≤3 (according to theorem 1). After the addition of point 0 in the loop, because point 0 is connected with all the points on the loop, point 0 should take a color different from that of all the points on the loop. Thus the coloring number should be one more. Therefore this has X (G) ≤4. Proof is over.
Fig.1
Theorem 5: After adding a line liking the two points which have not been connected in the graph, the coloring number of new graph will not be less than that of the original graph.
Proof: If the colors of the two points to be connected are originally different, the new coloring number will not change after the connection of such two points. But if the colors of those two points are same, then it is necessary to change one of coloring point into another one, and moreover re-adjust to color the whole graph. But the coloring number of new graph will not be less than that of the original graph. Reduction to absurdity: suppose that the coloring number of new graph is less than that of original graph, and let N is the latter’s coloring number, and N-K is that of the former (Both of N and K are positive integer, and K<N), and then after removing the new increased connecting line, the other part can be adopted new graph’s coloring method and also it can also satisfy the demand for different colors in neighboring points. It indicates that the original graph’s coloring number at most should be N-K. It is inconsistent with the original suppose (the original graph’s coloring number is N). So it is impossible that the coloring number of new graph is less than that of original graph. Therefore, after adding a line liking the two points which have not been connected in the graph, the coloring number of new graph will not be less than that of the original graph. Proof is over.
Theorem 6: A quasi- triangulated graph(existence and only existence one triangulated graph of the polygen) with only “point on the loop” (namely it has neither the “point in the loop”nor the “point outside the loop”) is three-coloring. Namely X (G) =3
Proof: As in figure 2, there are loops ABCDEFG....... Firstly, three apexes of the triangle are distinguishably colored. For example, color No.1, No.2 and No.3 is colored respectively for Apex A, B, and C. Then color the Apex D of ΔACD, having a common side with ΔABC, in the same second color as Apex B. After that, color the apex of ΔADF, having a common side with ΔACD , in the same third kind of color as the Apex C......The same process goes on and on. Finally all the apexes will be colored with three different colors. This has proven that the quasi- triangulated graph with only “point on the loop” is three-coloring. Namely X (G) =3. Proof is over.
Fig.2
Deduction from Theorem 6: The coloring number of graph with only “point on the loop” is X(G)≤3.
Proof: Several lines are added in the loop in the original graph to make it a “quasi-triangulated graph”. This process will not reduce the coloring number (according to Definition 5) of the original graph. Thus X(Goriginal)≤X(Gnew) does exist. But the coloring number of the new graph after the addition of “lines” X (Gnew) =3 (according to Definition 6). Thus X (Goriginal) ≤3. Proof is over.
Theorem 7: So long as all the closed curves inside a closed three-dimensional space, may be contracted into a point, this space certainly is a three dimensional sphere. (Poincare Theorem).
Deduction from Theorem 7: Dig a “hole” in "the spherical surface",and this will become “ Plane” in the sence of the topology. Dig two “holes”, and this will become “Cylindrical Surface” in the sense of topology. No matter how many “holes” are dug in "the spherical surface", the “coloring number” of "the spherical surface" will not change.
Proof: Contract the “all -arounds” of the infinite "plane" into a point outwards, or contract the upper or lower surfaces of a cylinder into a point, and this becomes the spherical surface of a three dimensional sphere. (Poincare Theorem). Therefore, the curved surfaces, such as “Plane" and “Cylindrical Surface" and so on are all "the spherical surfaces" in terms of topology. Thus their “coloring number” is definitely the same. (Proof is over.)
3. The proof of the Four Color Theorem
Four Color Theorem: For any ichnograph in any spherical surface or plane, X(G)≤4 does always exist.
Proof:
Without losing the generality, make an arbitrarily complex graph, such as that in Figure 3. (Note: The reader also may choose any other shapes of graph in an attempt.For easy to understand during the course of the proof. The reader may imagine the graph is a spherical surface although it is a plane.) In the figure, the solid line represents a very small partial graph of the whole. And the dashed line indicates the major part of the omitted graph. Its complexity may be within the reader’s imaginations and contrivances as far as possible in conformity with "the finite graph" instead of "the infinite graph". So the “coloring number”of the graph is finited also.Suppose the “coloring number”is maximum “coloring number” in all graphes, If “coloring number” of the graph is K ,Then X(G)≤K in any graphes (K is a posisitive integral number its volume can be any big number wantonly.)
Fig.3
Then the operation and analysis of the graph will be given in the following steps.
Step 1: (to be called “Adding line”.)
On the basis of keeping all the points and lines in the original graph, connect all the points yet to be connected between two points as many as possible. (Heed that the new colored point shall not be increased any while only the connecting lines be increased) until it becomes a “triangulated graph”. According to the preceding Theorem 5, after the operation process, the “coloring number “of the new graph will not be less than that of the original one. This step is called “Adding line”.But the “coloring number “of the original graph is the maximum coloring number in the all graphes.So the coloring number of the new graph is K also.
Step 2: (to be called “Removing point” And “Removing line”)
Any graph is bound to exist one or more “minimum loop”(including a point in it) which has maximum number of coloring points. (but not “coloring number “) Of course the kinds number of coloring points of the partial graph can not be more then K also.
For example, we take this “point in the loop” as V0, and we have already connect V0 and V4, V0 and V5 due to “Adding line”, And with V3 and V7, V4 and V8… also connected, this turns the original graph into a “triangulated graph”. There is no harm in supposing:The “minimum loop”is V1-V2-V3-V4-V5-V1,as a“minimum loop” of the maximum number of coloring points.And We suppose all the number of coloring points (but not “coloring number “) including a point in the “minimum loop” equal to H.There are H≤K obviously.Then we choose randomly a point Vi“outside the loop”,and examine the Vi and the “minimum loop” adjacent to the Vi.So the number of coloring points including Vi and the“minimum loop” adjacent to the Vi is smaller then or equal to H surely。(It had been given before) So we can removing the point Vi and removing all the lines connecting to the Vi.Doing it like thus can not reduce the“coloring number“of the original graph.(Because the the point Vi to be interdiction and isolation in the “minimum loop”around the Vi.Its color already existed outside“minimum loop”of Vi，Or it can be changed into a certain color that already existed outside“minimum loop”of Vi, The coloring of the Vi has nothing to do with the coloring of“point outside the loop”,thus the point of Vi is “a coloring point that can be omitted”,so the point of Vi can be get rid off, then the lines connecting to it can been removed too, becouse we adopt the method of the “Point Coloring”.)
Step 3: To the graph the process of “Adding line” in step 1 and “Removing point” And “Removing line” in step 2 shall be repeatedly carried on alternately or not alternately,（as moer as posible to use Step 2 repeatedly） According to the above-mentioned views the“coloring number“of the original graph can not be reduced , until there is no meaning to further make the grph simplify,(at that time the coloring number of the graph is a obvious number) Finally it become a “quasi-triangulated graph”. Because the “point” is reduced one by one and the “point in the loop” and “point outside the loop” in the “spherical surface” or “plane” are relatively defined. the ultimate result could be like figure 1 or figure 2, namely the graph with only one “loop”, and only one point in the loop, and there is no any point ouside the loop. (Here the “point in the loop” is connected with the “point on the loop”) or there is a “quasi-triangulated graph” with only all the “points on the loop”. But the “coloring number” here is X(G)≤4,So the “coloring number”of original graph also is X(G)≤4. Proof is over.
In order to facilitate the understanding of the proof by the readers, it is recommended they choose some other graphs, from simple to complex to more than once experiment with and contemplate the method provided in this article (namely the three steps involved in the proof)so that they could understand the incomparable mystery and accuracy of this proof.
4. An explanation of a detail
In order to make the reader better understand the logic of this article, some explanations should be given. The whole article revolves around the analysis and operation of the “loop” and “point in the loop” and “point outside the loop” in the “partial graph” of the “whole graph”. The substance of the “triangle” in the “quasi-triangulated graph” is the “loop” made of three points. If the “loop” in the graph is made of more than three points, then it can turns into the “triangulated graph” by means of “Adding line” before analysis and operation is done. If the “loop” in the graph is made of two points or one point (For example, in the cases of one area surrounding the other area), though not mentioned in the preceding, its analysis and operation is totally the same as that of “loop” made of three points.
References
[1]Gong Guanglu. Finite Mathematics Introduction, section 1. Shanghai Science and Technology Press. 1985.5, pp: 288-343
[2]Jiang Zehan. Euler Theorem for Polyhedral and Topological Classification for Closed Surface, section 1. People Education Press. 1979.1, pp: 32-42
[3]F. Halari (American). Graph Theory, section 1. Shanghai Science and Technology Press. 1980.1, pp: 145-166
[4]Wang Shuhe. Graph Theory and its algorithm, section 1. China Science and Technology University Press. 1994.8, (The second printing), pp: 141-157
|
|
IP卡
狗仔卡
发表于 2008-9-23 13:17
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡