4-Staining of “Staining Dilemma Configuration” in Four-Color Conjecture ()
1. Introduction
The four-color conjecture was formally put forward in 1852 and lasted 169 years. In 1879, Kempe gave a short proof [1], but there was a flaw, that is, it did not solve the 4-staining problem of the “staining dilemma configuration”.
In 1976, American mathematicians Appel and Haken gave machine proof [2]. Robertson further simplified the machine proof in 1997, but it was not universally accepted in mathematics. Appel foresaw that one day someone would find a brief proof of the four-color conjecture.
In 2018, I found an important theorem (four-color vertex quadrilateral and its property theorem) in the 4-color maximum plane graph; At the same time, it is found that the “Errera diagram” given by Errera 1921 has three other homomorphic configurations (all 10-fold symmetric staining dilemma configurations), which constitute the E-family 4 configurations. These two great discoveries produced two new theories and methods, which skillfully solved the classification of staining dilemma configuration and correct 4-staining, made up for Kemp’s loophole, completed the brief proof of four-color conjecture, and realized Appel’s foresight.
Next, follow the discussion method of combining practice with theory; the definitions and theorems are derived from a 4-color maximal planar graph [3] (i.e., “triangulation”, see reference [2]). All configurations are maximal plan views, and the outer plane V adjacent to the Pentagon is omitted.
2. Staining Dilemma Configuration Modeland Related Definitions and Theorems
In 1935, “ehe Journal of the american mathematical society “published “a set of operations on partially staining maps” [4], in which “Staining dilemma configuration” was defined and a basic model was given, as shown in the left of Figure 1. We simplified it as an 8-point minimum model with dual graph, as shown in the right of Figure 1; the author also gives the “Errera diagram” (abbreviated as “E configuration”, that is, E1 in Figure 5).
Definition 1. Configuration
On the basis of Kempe definition, we add a detailed definition of the “configuration”, that is, the correct four-color staining configuration consists of two parts: one is the geometric structure composed of points and edges, and the other is the “color distribution map” (abbreviated as “color diagrams”) formed by a certain four-color staining scheme.
Definition 2. 4-color vertex quadrilateral and 3-color vertex quadrilateral.
In a configuration that is correctly staining with four colors, if four different staining vertices and the edges connecting them form a minimal quadrilateral,
![]()
Figure 1. Staining dilemma configuration model.
this quadrilateral is called a four-color vertex quadrilateral; if the four vertices of the minimal quadrilateral only use three different color staining, then, this quadrilateral is called a three-color vertex quadrilateral.
Theorem 1: There is inevitably at least one minimum four-color vertex quadrilateral in the configuration correctly staining with four colors.
Proof (disprove method):
In the correctly staining four-color configuration, if there is no minimum four-color vertex quadrilateral, that is, all the minimum quadrilaterals are three-color vertex quadrilaterals, then this three-color vertex quadrilateral should have two vertices with the same color, so this three-color vertex The staining of the two triangles in the quadrilateral is also the same. All the vertices of the triangles in the entire map must also be staining with these three colors, that is, the entire map is also staining with these three colors. This contradicts the four-color staining condition. Use Figure 2 to verify:
In Figure 2, the geometric structures of (1) and (2) are the same, except that one vertex of the color map is staining differently.
1) A quadrilateral with four-color vertices is included in the maximal plane graph, which is the minimum four-color map;
2) A quadrilateral with a tricolor vertex is included in the maximal plane graph, which is the minimum tricolor map.
Obviously, (1) and (2) are contradictory, which is the best interpretation of Theorem 1.
Definition 3. Color chain and opposite color chain:
In the correct 4-staining configuration, if at least two vertices of different coloring are connected by edges, they are called color chains, such as A-B chain, B-C chain, etc. When color chain presents a closed loop, it is called a ring chain. If two color chains are staining differently, called the opposite color chain, such as A-B chain and C-D chain,
Theorem 2. Four-color vertex quadrilateral property theorem:
1) Two diagonal chains of a four-color vertex quadrilateral cannot exist in the same four-color vertex quadrilateral at the same time.
Proof: Since the four vertices in the four-color vertex quadrilateral have different colors, the diagonal chains connected by the two sets of non-adjacent vertices are opposite color chains, so they cannot intersect, that is, they cannot exist in the same of four-color vertex quadrilateral.
![]()
Figure 2. Minimum four-color and three-color vertex quadrilateral.
2) In the four-color vertex quadrilateral, changing the known diagonal chain can only destroy the geometric structure of the original configuration, but not the combination of color points of the original configuration.
Proof:
Changing the known diagonal chain in the quadrilateral with four-color vertices only changes the combination of edges in the original configuration (i.e., geometric structure), but does not change all vertices in the original configuration and their staining.
3. Two Kinds of Proofs of an Important Lemma
In “A Tentative Four Coloring of Planar Graphs” [5], the author expressed E1 configuration as its dual graph, called CK graph, and proved lemma 3.1: “When the initial staining is CK0, the algorithm 2.1 loops, and takes 20 as a cycle”, which is proved in detail in Literature 5.
In 1992, in the article “The example of Heawood should be known”, the author gave a “Heawood graph” [6], that is, E1 configuration, and proved that “when Heawood inverted staining (H-staining procedure for short) is carried out four times, E1 configuration staining cycle”, which can be called lemma 3.2 here. See ref.6 for detailed proof. In this paper, “four times of Heawood reverse staining” is called “H-staining procedure”.
Algorithm 2.1 in Document 5 is the same as the H-staining procedure in Document 6, except that the four colors in the two configurations and the arrangement direction on the fence are different (the former 1, 2, 3, 4 are arranged clockwise, the latter B, R, Y, and G are arranged counterclockwise), so the reversed dyeing of Algorithm 2.1 is clockwise, and the reversed staining of H-staining program is counterclockwise, indicating that for the periodic cycle of E1 configuration, two directions (counterclockwise and clockwise) The reverse staining of is the same. In this paper, A, B, C, and D are used to represent four different staining methods, and the two staining methods are collectively referred to as “H-staining procedures”.
The proof of Lemma 3.1 and Lemma 3.2 is shown in Figure 3:
In Figure 3, (1) is the color diagram formed by the intersection of A-C chain (indicated by dashed line) and A-D chain (indicated by thick black line) when E1 configuration is in the initial position. In (2) - (5), the dotted line represents the known or generated maximum chain. Thick black lines represent color chains staining upside down.
Sequentially carrying out reverse staining for B-D, D-A, A-C and C-B four times counterclockwise along the arrow, (6) is the configuration generated after 4 times of reverse staining. Comparing (1) with (6), it is not difficult to find that the geometric structures of the two configurations are the same, and both have ten-fold symmetry, and color diagram is the same, except that the position of the color diagram is rotated clockwise by 144˚ from (1).
When Figure 6 undergoes four cycles of H-staining, that is, a total of 20
![]()
Figure 3. Cyclic process of E1 configuration.
times (4 times X5) reverse staining, the geometric structure and staining of E1 configuration completely rotate back to the position of the Figure 1.
4. The Generation of E-Family Configuration and the Perfection of Two Lemmas
In Figure 3, when the H-staining procedure is carried out, the graph (1) and the continuously evolved graphs (3), (4) and (5) form a cycle due to the reverse staining for four consecutive times. After careful investigation of their color diagrams, they still belong to the staining dilemma configuration, as shown in Figure 4.
In Figure 4, their geometric structure has not changed, and they all have 10-fold symmetry, but the color map has changed. The two intersecting color chains starting from the peak points A1, C1, B1, D1 (marked with dashed and solid lines) is different in combination.
![]()
Figure 4. Four continuous change graphs of E1 configuration.
When all of them are changed into “BAB” distribution of peak point A, the four different E configurations shown in Figure 4 are arranged in the order of peak points: A1 (corresponding to Figure 1), B1 (corresponding to Figure 4), D1 (corresponding to Figure 5) and C1 (corresponding to Figure 3), and the four configurations shown in Figure 5 can be obtained, which is abbreviated E1, E2, E3, E4.
Examining the four homomorphic configurations in Figure 5, it is not difficult to find that their geometric structures are all 10-fold symmetrical, but their color diagrams are different. When we apply H-staining programs to them respectively, the configuration will cycle periodically regardless of the direction (clockwise or counterclockwise). What makes them cycle? We think that the 10-fold symmetry of geometric structure is the main factor, while the staining diagram is only the secondary factor. Therefore, the propositional conditions of lemma 3.1 and lemma 3.2 are imperfect. Therefore:
Lemma 3.1 should be perfected as follows:
When E1 configuration has 10-fold symmetry and the initial staining is CK0, the algorithm 2.1 loops and takes 20 as a cycle.
Lemma 3.2 should be perfected as follows:
When Heawood inverted staining is carried out four times, E1 configuration staining with 10-fold symmetry presents a cycle.
The above two lemmas are obviously reversible.
If lemma 3.1 is taken as the original theorem, then lemma 3.2 is the inverse theorem of lemma 3.1. At this time, according to the four different combinations of the four propositions true and false sex, as shown in Figure 6, it can be judged that these four propositions are true propositions. Therefore, the negative principle of lemma 3.1 in literature 5 is also true, that is:
![]()
Figure 5. Four Homomorphic configurations in E-family.
![]()
Figure 6. Classification of the truth and false of four propositions.
Theorem 3: When the configuration is not 10-fold symmetric and the initial staining is CK0. Algorithm 2.1 does not loop.
Generally speaking, there are four different combinations of the truth and falsity of the four propositions.
Obviously, the following inference can be drawn from Theorem 3:
As long as the geometric structure of the staining dilemma configuration of any combination of points and edges is not 10-fold symmetry, then there will be no periodic cycles when performing the H-staining procedure, that is, through a limited number of reverse staining, the configuration can be given 4-staining.
The inference of Theorem 3 realizes the research direction given by Professor Lin Cuiqin of Tsinghua University in 1996: If it can be proved that 4-staining of can be successfully achieved for any maximal plane graph after finite inverse staining, it will be a great success and a shock at home and abroad.
5. Verification of Theorem 3 and Its Corollaries
We use the property theorem of four-color quadrilateral to transform the diagonal chain of any known four-color quadrilateral, so that the geometric structure no longer has ten symmetry (This transformation is called non-tenfold symmetric transformation), and then by H-staining program is applied to them to see if they can be 4-staining. There are 62 transformable four-color vertex quadrilateral diagonal chains (The distribution in the four configurations of the E-series is 17 + 15 + 15 + 15). By transforming diagonal chains one by one, 62 non-tenfold symmetric staining dilemma configurations can be obtained, and the correct 4-staining can be obtained by using H-staining program. Then, according to the classification of reverse staining times from less (2 times) to more (16 times), 15 different configurations are obtained, which we call {Zhang configuration}, abbreviated as {Zi, I = 1, 2, 3, …, 15}. As shown in Figure 7, in each configuration, diagonal chains shown by dashed lines are replaced by thick black lines, So that the geometric structure of the configuration is no longer ten times symmetrical.
In Figure 7, the number of reverse staining in two directions is marked under each configuration. It is not difficult to see that the inversion times of Z1 - Z8 and Z15 - Z8 in the 4-staining of the configuration is the same from two directions.
Therefore, according to the symmetry of the clockwise and counterclockwise inversion staining times, the 15 configurations can be simplified into 8 configurations (Z1 - Z8), and the inversion staining times are 2 to 9 times.
When the diagonal chain of each four-color vertex quadrilateral is transformed, the above 62 non-tenfold symmetric staining dilemma configurations are generated. If you choose all the different combination transformations in 62 diagonal chains, you will get thousands of non-10-fold symmetric configurations. According to Theorem 3, they can also use the H-staining procedure 4-staining.
6. 4-Staining Proof of Two Kinds of Staining Dilemma Configurations
Staining dilemma configuration can be divided into two categories according to whether its geometric structure has ten times symmetry. One is a 10-fold symmetric configuration (E-Family four configurations and their extended configurations), and the other is a non-10-fold symmetric configuration. The 4-staining proof of these two configurations is given below.
6.1. The 4-Staining Proof of the Dilemma Configuration of Non-Tenfold Symmetric Staining
This problem has been proved by Theorem 3 and its corollary above. Here, just to help readers understand the 4-staining process of these configurations in detail, the 4-staining proof of Z15 configuration with the most unidirectional reverse staining times is given, as shown in Figure 8: the dotted line indicates the known or generated maximum chain, the thick black line indicates the reverse staining chain, and the arrow indicates the evolution order of the configuration.
![]()
![]()
Figure 7. 15 non-ten-fold symmetrical configurations.
6.2. 4-Staining of 10-Fold Symmetry Staining Dilemma Configuration
We use mathematical induction to prove it.
Because the E-family 4 configuration has a periodic cycle in the process of H-staining, it cannot be proved that they 4-staining by this method. In the four minimum E configurations, E1 and E2 contain characteristic chain A-B rings, E3 and E4 contain characteristic chain C-D rings. Therefore, we use this staining property to give a special “Zhang-staining program”, called “Z-staining program” for short (Kittel called the “tangent chain method”) [7].
The Z-staining program of E-family 4 configuration can also be called Theorem 4.
6.2.1. Proof of Inductive Basis
Only the 4-staining of the configurations represented by E1 and E4 are given below.
The detailed staining process of E1 is shown in Figure 9:
![]()
Figure 9. 4-staining process of four configurations of E1 periodic transformation.
If the graph 1) or 3) is known, firstly reverse staining of C-D chain (thick black line) outside A-B ring to generate disjoint A-C, A-D (or B-C, B-D) maximal chains, and then reverse staining the B(D), B(C) (or A(D), A(C)), reduce the vertex color number of the Pentagon to 3 (see Figure 1 or Figure 3).
If the graph 2) or 4) is known, firstly reverse staining of C-D chain (thick black line) outside A-B ring to generate a new B-C (or A-D) maximal chain, and then reverse the vertex color (A(D)) or B(C)), reduce the vertex color number of the Pentagon to 3 (see Figure 2) or 4)).
As for the detailed proof of E4, it is enough to give only the 4-staining proof of the initial configuration, instead of giving all the 4-staining proof of four continuous transformation configurations like E1. As shown in Figure 10.
Firstly, the staining of A-B chain (thick black line) is reversed outside C-D ring (dotted line in Figure 1) to generate a new A-C maximal chain (dotted line in Figure 2), and then the solitary point D (big black point in Figure 2) under A-C maximal chain is changed to B color in Figure 3.
The 4-staining proof of Figure 9 and Figure 10 shows that Z-staining program is feasible.
6.2.2. Inductive Hypothesis Proof
Assuming Z-staining program is feasible in the E-family configuration with K = 16 + 5n, the Z-staining program is still feasible when K = 16 + 5(n + 1).
The geometric structure of 10-fold symmetry is characterized by five-pointed stars and pentagons alternately arranged from inside to outside. When we study the vertex staining of pentagons separated by five-pointed stars, we find the following rules:
![]()
Figure 10. 4-staining process of initial configuration of E4 configuration.
Within or outside the smallest 16-point E-family configuration, the increased pentagonal vertex staining always appears in the order of ACDCD or BACDA and ABCDB. This is determined by the staining of pentagonal vertices from inside to outside.
Among the four configurations of the E-family, E1 is a class and E2, E3 and E4 are a class (at least one of the two intersecting chains passes through the symmetric central color point), so it is enough to select only of the extended proofs of E1 and E4.
In the three graphs of Figure 11 below, the solid line represents K = 16 + 5n (n = 0, 1, 2, 3, …), the dashed line represents the element embedded inside (or outside) the solid line graph.
The whole figure still shows ten times symmetry.
Proof:
1) When expanding inside E1, as shown in Figure 11(a):
Because E1 or E2, E3, E4 are embedded, the entire enlarged image is still 10-fold symmetrical, and the two color chains A-C and A-D intersection of still exists and the characteristic ring A-B still exists, so the Z-staining procedure is still feasible.
![]()
(a) ![]()
(b) ![]()
(c)
Figure 11. (a) E1 configuration expands inward; (b) E1 configuration expands outward; (c) E4 configuration expands outward.
2) When E1 expands outward, as shown in Figure 11(b):
When the vertex staining of the kth pentagon (thick dashed line) in Figure 11(b) is BACDA (or ACDCD), the vertex coloring of the (k+1)th pentagon must be ABCDB, which is the same as E1 (real line) The vertices of the two outermost pentagons are colored exactly the same. A-C chain and A-D chain are the extension of E1 A-C chain and A-D chain in the extension interval, and the Characteristics ring A-B (or C-D) still exists. When the stained letter is BACDA, the generated characteristic ring is A-B ring; when the stained letter is (A)(C)(D)(C)(D), the generated characteristic ring is C-D ring. The Z-staining procedure is still available.
3) Because the characteristic chain A-C in E4 configuration passes through the color point C of symmetry center, this configuration cannot be expanded inward, but can only be expanded outward, as shown in Figure 11(c):
Looking at Figure 11(c), that is, E4, the result is just opposite to that of Figure 11(b).
When the staining of the k th pentagon (thick dotted line) is ACDCD (or BACDA), the vertex staining of the (k + 1)th pentagon must be ABCDB. Like the case in Figure 11(b), the characteristic ring C-D (or A-B) still exists, and the Z-staining procedure is still feasible.
At this point, the proof is completed.
When the above four-color component is embedded in the enlarged interface outside the minimum E-configuration, and still exhibits ten-fold symmetry it can be seen from Figures 11(2) and 11(3) that the added color chain is only in the minimum E-configuration Part of the color chain extension, the 4-staining effect is the same, so no further study is necessary.
As for other enlarged forms of E-configuration:
When some color chains are arbitrarily elongated in the minimal E configuration, or a known tetrachromatic diagram is embedded in some triangles, quadrilaterals, and pentagons, as long as the tenfold symmetry geometry and its original color diagram are not destroyed, then 4-Dyeing programs are still available.
If in doubt, please refer to the literature [8].
7. Conclusion
Comprehensive 1 - 6, through 4 new theorems, the staining dilemma configuration of any vertex and edge geometric structure is divided into two categories according to whether it has a 10-fold symmetrical geometric structure, and then using the H-staining procedure or Z-staining procedure, successful 4-staining. In this way, what is foreseen in literature 4 is realized: if certain operations or certain operation sets of the staining dilemma configuration can be found, all maps will not continue to remain in the staining dilemma after these operations are performed, then the four color problem is solved. Also realized Appel’s scientific foresight.
Acknowledgements
During the completion of the thesis, Professor A. Lehoyd of Lancaster University in the United Kingdom sent Document No. 6, Singapore Wan Chunru translated several proofs of the four-color conjecture, and Beijing’s Ganfeng provided his research results “4CC and 1 + 1 Proof”. At the same time, received the guidance of Professor Lin Cuiqin from Tsinghua University, Professor Wu Wangming from Shanghai Normal University, and Professor Liu Guizhen from Shandong University. Especially Lei Ming from Xi’an City, gave Z9 and Z15, and helped make all the drawings. Here, we express our gratitude.