四色猜想中H-E类构形的正确四着色（全文文字部分）

zhangyd2007@soh

尊敬的四色问题专家，您好。
      近日，我们在《数学中国》哥德巴赫猜想难题栏目中上传了《四色猜想中H-E类构形的正确四着色》的附件，由于不能一次图文并茂地显示全文，需要一个一个下载才能完整评读，很不方便。今天，只能把全文文字部分上传，希望专家从完整的论述推断论文的正确性。有兴趣的话，可以打开四个附件看图。也可以参考《四色猜想中H构形4-染色问题的解决》中的图1----图10，比本文少一个完备性图示以及论述，就在图11里。因此本文已经十分完整，正确。
       如果您想详细了解这篇论文全貌，可以通过我的邮箱E-Mail:zhangyd2007@sohu.com告诉我，通过我的微信号（18335385319）得到。


                                                                              四色猜想中H-E类构形的正确四着色
                                                                                张彧典1      龚亦轩2        张奕然3
                                     1、 太原市（18335385319），2、上海市（13524709840）3、（苏州市15203419005）
                                                                                  E-Mail:zhangyd2007@sohu.com

摘要:  四色猜想[ 1 ]于1852年由英国古斯里提出，1879年，肯普( Kempe)给出一个有价值的证明 [ 2 ] ，1890年，赫伍德(Heawood) 给出一个构形(简记为H构形)，指出肯普证明中的漏洞，1921年，埃雷拉(Errera)又给出一个比赫伍德构形更漂亮（具有十折对称性）的构形(简记为E构形)，我们把以上两个构形称之为H-E类构形，这样的构形究竟有多少，而且都可以正确四着色? 成为世界数学家们一百多年以来试图解决的问题。
1976年，美国数学家阿佩尔与哈肯(Appel--Haken)给出一个机器证明，从此四色猜想变成四色定理了。同时，阿佩尔大胆预言：四色问题的一个简短证明总有一天会被发现，甚至被因此而一举成名的天才高中生所发现。
本文通过四个创新定理以及高中数学方法，成功解决了H-E类构形的分类以及正确四着色问题，实现了阿佩尔的预见。
.
关键词:  四色猜想 ,  埃雷拉构形, H-E类构形 , 十折对称 , 四色顶点四边形

                                                                                        1、H-E类构形的数学模型
  
      1935年，《美国数学学会杂志》发表了《部分着色地图上的一组操作》[ 3 ]，其中定义了“着色困局构形”，也就是“H-E类构形”，接着给出了基本模型， 这种构形的主要特征是:两条“极大链”[ 4 ] A-C、A-D相交，如图1（1）所示，我们将其简化为8点式对偶图形式，如图1（2）或者1（3）所示，图（2）、（3）互为拓扑等价关系，图（2）是把图（3）中顶点V拓扑变换到与之相邻的五边形外部并且省略了。作者还给出了埃雷拉构形，简记为“E1构形”，本文所有构形都采用图1（2）表示方法。
                                                                                                                                               
                                          (1)文献3给出的构形模型                          （2）  V在五边形之外                 （3）V在五边形之内

                                                                                           图1：H-E类构形的数学模型


                                                                                                     2、相关定义

定义1、构形
       我们在肯普 “构形” 定义的基础上，给出“构形”的完整定义，即正确的四着色构形由两部分组成:一是由点和边组成的几何结构，二是由某种四着色方案形成的“颜色分布图”(简称“色图”)。
定义2、色链，相反色链，极大链，十折对称，峰点，极大平面图
       色链：构形中，任意不同染色的相邻顶点与它们之间的连线（边）所组成的点、边“路径”[ 5 ]称为色链，简称为链，如A—B、A—C等；当色链呈现封闭的环时，称为环链，简称为环；
      相反链：如果两条色链染色不同，就称为相反链，比如A-B链和C-D链；
      极大链：  如果色链的起点与终点为五边形之不相邻、不同色的两个顶点时，称之为极大链，在图1所示数学模型中只有A1---C1、A1—D1、B-C、B-D四种极大链；
      十折对称：也是文献4中给出的，是指埃雷拉构形的几何结构具有方向不同的十条对称轴，使得构形的点、边呈现左右对称，称为十折对称；
       峰点 [ 6 ]：设四色染色的五边形围栏中的A色顶点被两个B色顶点从两边托举在上面，好像山的顶点，所以称为峰点。
       极大平面图 [ 7 ]：顶点数固定而边数最多的平面图。本文所有图都是图1（2）式构形。               
定义3、四色顶点四边形和三色顶点四边形。
       在用四种颜色正确着色的构形中，如果四个不同的着色顶点和连接它们的四条边围成一个最小四边形，那么这个四边形称为四色顶点四边形，如图2（1）；如果最小四边形的4个顶点只用三种不同颜色着色，那么这个四边形称为三色顶点四边形，如图2（2）。
                                                      
                                                                                         图2:    最小四色、三色顶点四边形


                                                                                                         3、四个创新定理

       我们在长期研究前人证明四色猜想的成果基础上，独立发现了有别于前人的四个定理，下面逐一给出这四个定理及其证明。
定理1:
       在用四种颜色正确染色的极大平面图中，不可避免地存在至少一个四色顶点四边形。
       这个定理可以称为四色顶点四边形存在定理。                       
证明反证法) 在含有四种颜色的极大平面图中，如果连一个最小四色顶点四边形都没有，也就是所有的最小四边形都是三色顶点四边形，那么每个三色顶点四边形中一定有两个不相邻顶点的颜色相同，如图2中的（2），导致整个地图中的所有三角形顶点也一定是用这样的三种颜色着色，也就是整个极大平面图的顶点只用这样的三种颜色着色，这与用四种颜色着色的条件相矛盾。  
       在图2中，(1)和(2)的几何结构相同，只是色图中一个顶点着了不同颜色。 (1)具有一个四色顶点四边形包含在极大平面图中，这是最小四色地图； (2)具有一个三色顶点四边形包含在极大平面图中，这是最小三色地图。 显然，(1)和(2)是矛盾的，这是对定理1的最好验证。
                                          
定理2：四色顶点四边形性质定理
（1）        一个四色顶点四边形的两条对角链不能同时存在于同一个四色顶点四边形。
证明：由于一个四色顶点四边形中的四个顶点颜色不同，由两组不相邻顶点连接的对角链一定互为相反色链，所以它们不能在这个四色顶点四边形中相交，即不能同时存在于一个四色顶点四边形。
（2）在四色顶点四边形中，改变已知的对角链只能破坏原始构形的几何结构，而不会破坏原始构形的顶点着色分布即色图。  
    证明: 改变给定四色顶点四边形中已知的对角链，如图2中的（1），就是把已知的对角链B—C变换为它的相反链A—D，这时，只是改变了原始构形几何结构中边的组合， 而并没有涉及到原始构形中的所有顶点的着色，所以不会破坏原构形的顶点着色分布图 即色图。
   这个定理，提供了将十折对称几何结构转化为非十折对称几何结构的一个变换法则，可以称为非十折对称变换法则。
定理3：当构形不是十折对称且初始颜色为CK0时，算法2.1不循环。
证明：
       在2003年发表的《平面图的一个试探性四着色》（即文献6）中，作者科凯将E1构形表示为它的对偶图，称为CK图，并证明了
引理3.1:“当初始着色为CK0时，算法2.1循环，并以20为一个周期”，详细证明见文献6。
      1992年，在《应该知道的赫伍德范例》（即文献4）中，作者米勒给出了一个“赫伍德图”，并证明了“当运用四种连续颠倒着色的赫伍德换色程序时，E1构形循环”。
我们不妨在这里称之为引理3.2，详证见文献4，并且将“四次赫伍德颠倒着色”称为“H换色程序”。               
       文献6中的“CK图”与文献4中的“赫伍德图”都是“埃雷拉图”即E1构形， 文献6中的算法2.1与文献4中的H换色程序相同，只是两个构形中的四种颜色标识和围栏上的排列方向不同( 前者1、2、3、4为顺时针排列，后者B、R、Y、G为逆时针排列 )，所以算法2.1的颠倒着色是顺时针方向，H换色程序的颠倒着色是逆时针方向，说明对于E1构形的周期循环，两个方向(逆时针和顺时针)的颠倒着色的结果是相同的。为方便起见，本文统一用A、B、C、D表示四种不同的着色，并且把两种换色程序统一称为“H换色程序”, 即依次对“B-D、D-A、A-C、C-B”[ 或者“B-C、C-A、A-D、D-B”]4种色链进行颠倒着色。这时，引理3.1和引理3.2的证明，统一如图3所示:  
在图3中，(1)是当E1构形处于初始位置时，A-C链(用虚线表示)和A-D链(用粗黑线表示)相交形成的色图。在(2)-(5)中，虚线代表已知或生成的极大链， 粗黑线表示颠倒着色的色链。      
       当沿箭头逆时针方向施行一个H换色程序，如图（2）、（3）、（4）、（5）所示，图(6)就是经过四次颠倒着色后生成的构形。对比(1)和(6)不难发现，两种构形的几何结构一样，都具有十折对称性，色图也一样，只是(6)的色图位置是从(1)顺时针旋转了144°。
         
                                                       图3、E1构形的周期循环过程   
                                                                                               
     当图(6)再经过4个H换色程序，即总共5个H换色程序20次(4次X5)颠倒着色时，E1构形的几何结构和着色完全旋转回到图(1)的初始位置。                                                                              
     在图3中，当进行H换色程序时，由于连续四次颠倒着色，图(1)和连续演变的图(3)、(4)和(5)形成一个循环周期。完整考察它们的色图，仍然存在两条相交色链，属于H-E类构形，只是峰点的位置不同，如图4所示:   
      


                                                  图4:     E1构形的四个连续变化的完整色图        
                                                           
       在图4中，它们的几何结构没有变化，都具有十折对称性，但颜色图发生了变化：从峰点A1、C1、B1、D1开始的两条极大链(用虚线和实线标记)的相交组合不同。
当图4所示的四种不同的E构形峰点全部变为A的“BAB”分布，而且峰点A的初始位置如同基本模型时，即可得到图5所示的四种构形，称为E族4构形，简记为E1、E2、E3、E4。
            
                                                     图5：E族中的四种同态构形

       检查图5中的四个同态构形，不难发现，它们的几何结构都是十折对称的，但是它们的色图是不同的。当我们分别对它们施行H换色程序时，无论方向如何(顺时针或逆时针)，构形都会周期循环。是什么因素决定了它们的循环呢？我们认为：几何结构的十折对称与色图都是不可或缺的条件。因此，引理3.1和引理3.2的条件是不完善的，应该分别完善为
引理3.1’:
       当E1构形具有十折对称且初始着色为CK0时，算法2.1循环 , 并以20为一个周期。
引理3.2’:
       当对E1构形施行四种连续颠倒着色的H换色程序时，具有十折对称的E1构形着色循环。
       如果把完善以后的引理3.1’作为原定理，那么引理3.2’ 就是引理3.1’的逆定理。这时，根据高中数学关于四个命题真假性的四种不同组合，如图6所示，由于互为逆定理的引理3.1’与引理3.2’都是真命题，可以判断这四个命题都是真命题，因此，文献6中引理3.1’的否定理也是成立的。

                                                         图6 四种命题的真假性的不同组合

      到此证明了，定理3“当E1构形不是十折对称且初始颜色为CK0时，算法2.1不循环”是正确的。
      由定理3，可以得到
      推论：对于任何一个非十折对称的H-E类构形，施行H换色程序有限次以后就可以正确四着色。
      定理3及其推论就为“非十折对称的H-E类构形的正确四着色”提供了一个纯理论证明。
     定理4   Z—换色程序对于E-族构形正确四着色是可行的。
     证明 :
     由于E族4构形在施行H换色程序时发生周期循环，证明它们不能用这种方法进行，但是在四个最小E构形中，E1和E2包含特征环A-B，E3和E4包含特征环C-D。基特尔曾经给出E1构形一种特殊解法，称“切链换色法”（见文献3），但是他以及后人并没有发现E1构形还存在3个同态构形，并且给出这三个构形的解法，我们通过对E族4构形的求解，给出两种不同的基特尔“切链换色法”，即 “张氏换色程序”（简记为“Z换色程序”）。由于E1与E2是可以互相转化，属于一个类型，E3与E4具有左右对称性，属于另一个类型，所以，下面仅给出E1和E4代表的构形的四着色证明（即把五边形顶点的着色数从4减少到3从而可以给省略了的V着第4种颜色）就够了。
E1的详细着色过程如图7所示：
       当已知图（1）或（3）时，首先颠倒A-B环外C-D链(粗黑线)的着色，生成不相交的A-C、A-D(或B-C、B-D)极大链，然后颠倒孤点色B(D)、B(C)[或A(D)、A(C)]，将五边形的顶点着色数减少到3，见图（1）或（3）所示。

                                           图7:  E1在一个周期中连续变换的四种构形的四着色过程
                           [ 图7中左边的初始构形（1）（2）（3）（4）就是图4中的（1）（3）（4）（5）]

      当已知图（2）或（4）时，首先颠倒A-B环外C-D链(粗黑线)的着色，生成新的B-C(或A-D)极大链，然后颠倒孤点色A（D）[或B(C)]，将五边形的顶点着色数减少到3，见图（2）或（4）所示。
      至于E4的详细证明，只给出初始构形的四着色证明就足够了，而不用像E1那样给出一个周期中连续变换的4个构形的全部四着色证明。如图8所示。
      首先在图（1）之C-D环[ 图(1)中的虚线 ] 外颠倒A-B链( 粗黑线 )的着色，生成新的A-C极大链 [ 图(2)中的虚线 ]，然后颠倒A-C极大链下的孤点 [ 图(2)中的大黑点 ] 着色D（B），使得图(3)中五边形顶点的着色数减少到3。      

                                                                       图8，E4构形初始构形的正确四着色过程

      图7和图8的色链着色颠倒的方法就是Z换色程序，表明Z换色程序对于E族四个构形的正确四着色是可行的，即定理4成立。
      下面，需要探讨的是E族四构形的放大问题，也就是看看定理4对于E族四构形的所有放大构形是否仍然可行？
       我们运用数学归纳法，把对E族四构形的正确四着色证明作为归纳基础证明，然后进行归纳假设证明定理4仍然成立。
       假设Z换色程序在K=16+5n （n为自然数）的E族构形中是可行的，现在证明当K=16+5(n+1) （n为自然数）时, Z换色程序仍然是可行的。
       十折对称的几何结构的特征是由内到外交替排列的五边形和五角星 , 由于E族4构形都具有十折对称的几何结构，所以，我们只研究E1构形的放大就足够了。
如图9所示，实线表示K=16+5n(n为自然数)，虚线表示在归纳基础图（实线图）外部（也可以在内部）扩展的几何结构 , 即两个五边形被两个五角星间 隔，使得整个图形仍然显示出十折对称性。                                                                                 

                                                       图9、E1的向外扩展
                  
       当第k个五边形(粗虚线)的着色为BACDA [ 或（A）（C）（D）（C）（D）] 时，第(k+1)个五边形即扩展构形的五边形的顶点着色必须为ABCDB，才能保证与E1五边形围栏着色A1B1C1D1B2相同，特征环A-B (或C-D) 仍然存在。否则，构形就变成肯普已经证明了的简单构形(K构形）了。这时，施行Z换色程序仍然可行，即在扩大的A-B环外颠倒C-D边（即链）顶点着色，生成不相交的A-C、A-D环, 成为K构形，从而使得五边形围栏上5个顶点的着色数4减少到3 。
       但是，当上述四色构件在最小E-构形的外扩区域仍呈现十折对称性时，从图9的解析可以看出，增加的色边只是最小E1构形A1-C1、A1-D1相交链在外扩区域的延长，因此这样的向外扩展就没有必要研究了，这是因为：
   
                                                               图10（1）                   图10（2）

                                                                                 图10
                                                         
      当我们在这个放大的十折对称的E族构形中，施行5个H换色程序（20次颠倒着色）时，10（1）中加黑点的五边形的5条边都没有参与全图几何结构的周期循环，成为无用边，那么只包含这种边的四色构件也就是无用的了。由此证明了，在E族构形外扩区域内加入包含无用边的四色构件的情形是没有研究价值的。                                         
有了这样的理性认识，就可以解释文献6中给出的图6 [ 本文编号为图10（2）]所提出的两个疑问：
      如10（2）中，粗黑线五边形以内表示最小E1构形，虚线表示外扩区域，右边三色顶点四边形ABCB内嵌入一个四色构件，只是包含了对角链A—C, 即在这条边上增加了3个顶点，文献6作者由此质疑：既然全图几何结构已经失去十折对称性，但是为什么不影响算法2.1（即H换色程序）以及构形周期循环呢？这样的构形还有多少？
正是由于嵌入的四色构件只是包含了三色顶点四边形中的对角链A-C（无用边），所以这个四色构件也就成为无用的了。这种嵌入的四色构件一定只包含于 图10（1）中加黑点的5条边所在的5个三色顶点四边形 ，也就是说，像图10（2）那样的无用构形只有5个（单一）, 如果选择5个构形的不同数量的组合时，一共只有31个。
      另外，还需考虑一种放大构形，就是四色构件嵌入了E族构形内部（或外扩部分）的有用边，如图11(2)所示，在C-D边上增加了B、C两个点，形成虚线ABAC构件，破坏了已知E2构形几何结构的十折对称性，这样的放大构形就不能用Z换色程序求解，而用H换色程序可解。
           
                                       （1）、E族构形内四色顶点四边形对角链替换         (2)、四色构件（虚线）嵌入C-D边
                                                    （虚线所示A-B 链被粗黑线C-D替换  ）                 的放大构形
                                                                    图11、两种几何结构的非十折对称变换


                                                                                    4、H-E类构形的正确四着色证明

                                                                                            4-1 、 H-E类构形的分类
              
       首先，我们对H-E类构形进行分类，法则是看H-E类构形的几何结构是否具有十折对称性？具体做法是：
      （1）、利用四色四边形的性质定理2（1），在具有十折对称的E-族4构形中，把所有不破坏A-C与A-D二链相交的四色顶点四边形的已知对角链用它的相反色链替换，使几何结构不再具有十折对称性。经过考察，4个E构形一共有62个可变换的四色顶点四边形对角链( 在E族4构形中的分布分别是17+15+15+15)。通过62个对角链的单一变换，就可以得到62个非十折对称H-E类构形, 如图11（1）。如果变换E族4构形中对角链2—15（或者17）的不同数量的组合，就可以得到许许多多非十折对称的H-E类构形。
      （2）、如图11(2) 所示的构形，即在E族构形内部（或外扩部分）的有用边上增加了一些点，形成一个新的四色构件嵌入原来构形，破坏了原来构形的十折对称性，也可以得到许许多多非十折对称的放大构形。
       以上两种非十折对称的构形就组成第一类H-E构形的全集, 而具有十折对称的E-族4个构形就组成第二类H-E构形集。
               
   
                                                                                         4-2 、两类H-E构形的正确四着色证明
      
       对于第一类非十折对称的H-E构形的正确四着色，已经给出一个定理3（与推论）的理论证明，所以没有必要对如图11（1）所示的62个基本构形与如图11(2)所示的放大构形逐一求解。
      为验证上述理论证明的正确性，我们曾经对62个基本构形施行H换色程序求解：最多16次逆时针颠倒着色（顺时针颠倒着色却只需要2次）就可以成功四着色，如图11（1），逆时针5次可以成功四着色（顺时针颠倒着色就需要13次才行）；如图11（2）所示的放大构形，逆时针颠倒着色26次才可以成功四着色（顺时针颠倒着色也只需要2次）。实践得出的结论是：对于第一类非十折对称的H-E构形，施行换色程序求解时，总存在顺（或者逆）时针方向的颠倒着色次数不超过9 。这个结论也可以通过《肯普证明的完善》[ 8 ]得到验证，有兴趣的读者可以亲自实践验证。
       对于第二类十折对称的H-E构形的正确四着色，从已经给出的上述数学归纳法证明过程看，归纳假设证明是没有意义的，只要用定理4证明E族4构形成功四着色就足够了。
       综上所述，本文已经实现了文献6中的判断：如果能找到着色困局构形（即H-E构形）的某些操作或者是某些操作集合，能使得所有地图在施行这些操作后都不会继续保留在着色困局（即不再是H-E构形而变成肯普已经证明了的简单K构形）里，那么四色问题也就获得解决了。

      致谢
      论文完成过程中，英国兰卡斯特大学A. Lehoyd教授发来4号文件，新加坡万春如翻译了四色猜想的几个证明，北京敢峰提供了他的研究成果“4CC和1 + 1证明”。同时得到清华大学林翠琴教授、上海师范大学吴望名教授的指导。特别是来自西安市的雷明帮助制作了所有的图纸。在此，我们表示感谢。
   
      参考文献  
[1] 王献芬，胡作玄，四色定理的三代证明，自然辩证法通讯，2010，4（32），42-48。
[2] 张忠辅，数学的陷阱，上海自然杂志，1991年，5（14），379-381.
[3] ] IRVING KITTELL , A set of operations on partially colored maps,
Bulletin of the American Mathematical Society, 1935，6（41），407-413。
[4 ]Holryd F.C，Miller R。The Example That Heawood Should Have Given
Oxford quarterly of mathematics，1992，43(2)，67-71。
[5] 江嘉禾，四色地图问题的解决，世界科学译刊，1979，04，49-64。
[6] khamis Carr and William Kokai，A tentative plan 4- coloring ，
J. Comb. Math. Comb. Comp. 46 (2003), 97-112.
[7] 许寿椿，图说四色问题，北京大学出版社，2007，25。
[8]张域典，肯普证明的完善，山西忻州师范学院学报，2004 , 2（20），64—68.
第一作者简介:
张彧典，男，1943年9月生，汉族，大专学历，退休前任山西省盂县党校数学高级讲师。从1980年开始研究四色猜想的人工证明，45年来，在学习继承前人研究成果的基础上，完成了《四色猜想中H-E类构形的正确四着色》，弥补了肯普证明中的漏洞，实现了阿佩尔的预见。
                                                                                                [ 此文完成于2026年3月11日 ]