四色猜测的创新证明

雷明85639720

四色猜测的创新证明
雷  明
（二○一九年八月十九日）

本文只所以叫做“创新证明”是因为证明的方法与以前的证明方法有所不同，不需要首先判别已知图是H—构形还是K—构形，所以也就不需再找出平面图的不可免集，而是在给出一个构形时，根据图中链的特征一步步的判断，最多三步就可以空出颜色给待着色顶点着上图中已用过的四种颜色之一。
1、证明前的理论准备：
四色猜测（也叫四色问题）是在给地图染色的过程中提出的。说的是给任何地图染色，只要有公共边界的两个区域不染相同颜色，最多四种颜色就够用了。由于地图本身就是无割边的3—正则平面图，各顶点的度均是3，其对偶图则是极大的平面图，各面均有三条边。所以给地图的面的染色就相当于对其对偶图的顶点着色，一个地理学的问题就转化成了一个图论中的数学问题了。
对极大平面图着色，总能遇到待着色顶点周围的顶点已进行了4—着色，只有待着色顶点还未着色的情况，这就叫构形，把与待着色顶点相邻的顶点叫围栏顶点。因为极大图经去顶或减边后得到的任意平面图的色数只会减少，决不会再增加；只要解决了极大平面图的四色问题，任意平面图的四色问题也就得到了解决。由于平面图中一定存在着度小于等于5的顶点，所以在对任何平面图着色时，总可以把待着色顶点放在度小于等于5的顶点上。这就又把一个研究对象是无穷的问题转化成了有穷的问题了。这就是平面图的不可避免构形。
度小于等于3的不可免构形，以及围栏顶点占用颜色数小于等于3的构形，给待着色顶点着上图中已用过的四种颜色之一，是没有问题的。现在的问题是围栏顶点已占用完了四种颜色时的4度和5度构形，待着色顶点该如何着色呢？
我们把用两种颜色交替着色的序列叫做色链，简称链。交换链中各顶点的颜色，可以达到改变链中某一顶点颜色的目的。这就是坎泊创造的颜色交换技术。对于4度的待着色顶点，其中两对对角顶点的颜色所构成的对角链只要有一条是连通的，另一条则一定不连通，因为两条对角链正好是一对颜色完全不同的相反色链。这样就可以从围栏中不连通的对角链的一个顶点开始交换链中各顶点的颜色，就可以空出该顶点的颜色来给待着色顶点着上。这是坎泊早就解决了的问题。
对于度为5的待着色顶点，一定有一种颜色是用了两次的，把两个相同颜色所夹的顶点叫峰点，则BAB型的5度构形的峰点的颜色就是A。坎泊已证明了这种情况下无连通链、有一条连通链和有两条连通链但两连通链只有一个共同顶点情况下的待着色顶点是可以着上图中已用过的四种颜色之一的，而遗漏了两连通链有两个以上共同顶点且有一个实际交叉顶点的这一情况。现在，证明四色猜测主要是证明这种情况下的待着色顶点是否可以着上图中已用过的四种颜色之一。
2、四色猜测的创新证明方法：
以前人们只把坎泊证明中漏掉了的那种情况的待着色顶点叫“染色困局”，我认为这是“狭义的”，而我把只要是5度构形的围栏顶点已占用完了四种颜色的构形统一叫做“广义的染色困局”。在遇到这样的“染色困局”时，可以不管其是否是坎泊以前证明过的构形，都可以用相同的方法进行处理。因为有些图是难以分出是不是“狭义的染色困局”的。不管两条连通链是有几个共同顶点，只要能把连通链变通成不连通的，就可以把图变成坎泊以前已证明过是无连通链的可约的构形。再从不连通的对角链的一个围栏顶点进行交换，空出颜色来给待着色顶点。现在以BAB型的“染色困局”举例如下：

2、1  如果构形中是含有经过了围栏顶点的环形链，不管是A—B链还是C—D链（如图1和图２），都可以在环形链内（或外）交换与环形链呈相反色链的链，使得A—C链或A—D链均成为不连通的（已连通的变得不连通，不连通的则仍旧不连通。这就是“断链交换”，交换的是5连形邻角顶点的颜色构成的邻角链），使图成为可约的构形。再进行一次或两次由对角顶点颜色构成的“空出颜色”的交换即可空出图中已用过的四种颜色之一给待着色顶点V着上。
2、2  如果不含有经过围栏顶点的环形链，也不管是什么情况，先看有没有从一个B色顶点到其对角顶点是否有连通的B—D链或B—C链：
2、2、1  若有这条连通链（如图3,a），则一定没有从峰点A到C或D的A—C（或A—D）连通链，则从A或C（或D）开始交换A—C链或A—D链，就可空出A或C（或D）给待着色顶点V着上（如图3,b或图3,c）；

2、2、2  若没有这条连通链（如图4），则交换B—D链或B—C链后，再看有没有新生成从另一个B色顶点到其对角顶点的B—C连通链或B—D连通链：

2、2、2、1  若没有生成B—C（或B—D）链通链（如图5），则从另一个B色顶点开始交换与其对角顶点的颜色构成的B—C链或B—D链，即可连续的移去两个同色B，给待着色顶点V着上B（如图6）；
2、2、2、2  若生成了B—C（或B—D）连通链（如图7），则继续对新的类型的“染色困局”施行同方向的“转型交换”，一定可以在有限的42次交换之内空出颜色给待着色顶点V的（这可以单独的给以证明）。当然，在转型过的程中，图若转化成前面1中含有环形链的“染色困局”时，也可以按有环形链的染色困局去处理，可以减少转型的次数。
3、转型交换最大次数是42次的证明：
3、1  5度构形转型交换的周期是20
5度构形有5个围栏顶点，围栏顶点共占用了4种颜色。进行连续的转型交换，使得构形又转型成为BAB型，峰点A又回到原来的5度最上方一个顶点时，需要的交换次数是4和5的最小公倍数20次。这时，围栏各顶点的颜色均与最初转型前的颜色完全相同。再继续进行转型交换时，构形将以每20次交换为一个周期，无穷的转型下去，永远也不能空出颜色来。无论是进行逆时针方向转型，还是进行顺时针方向转型，都有同样的特点。
3、2  Errera—图虽是无穷转型也空不出颜色的图，但却是可4—着色的：

有没有无穷次转型交换也空不出颜色来的构形呢？有。这就是Errera—图（如图8。两图是同一个图，只是两种不同的画法。）。该图的确是无穷次的转型交换也空不出颜色的，两个方向的转型均是如此。许多学者的研究都说明了该图的转型过程的确是无穷循环的，循环的周期是20。但由于该类构形中有一条经过了围栏顶点的环形的A—B链（见图8，b中的外圈加粗边），可以交换A—B环形链内、外的任一条C—D链，使图变成可约的构形。所以该构形虽是无穷转型的，但却是可以4—着色的。
3、3  5度构形转型交换次数一定有限的理论证明：
无任何环形链的构形，在连续转型交换时，一定会分别在两个方向转型的第20次转型之前（包括第20次），图就一定会转化成为一个可以连续的移去两个同色的K—构形而可约。否则，图将是一个无穷转型交换也空不出颜色的图。但这却十在是不可能的事，因为无穷转型交换也空不出颜色的Errera—图，其中不但含有经过围栏顶点的A—B环形链，而且还含有不经过围栏顶点的C—D环形链（见图8中的加粗边），且A—B链和C—D链都是轴对称分布的，而现在这里所研究的对象（无任何环形链的构形）中，却是任何环形链也没有的构形，且A—B链和C—D链也不是轴对称分布的。
虽然1935年由Kittell给出了一个5度的轴对称构形（如图9，其中a图是地图形式，b、c两图是两种不图画法的原图a的对偶图），但其“裸图”（即未着色时的图）也只有一个对称轴，且不是中心对称的；而Errera—图“裸图”却是有五个对称轴（即张彧典先生所谓的“十折对称”）的图，且是中心对称的。所以无任何环形链的构形，决不可能是可以无穷的转型交换下去而空不出颜色的构形。两个方向的转型交换，一定都是可以在20次转形交换之前，变成一个可以连续的移去两个同色的构形的。再进行两次空出颜色的交换，可以连续的移去两个同色，即可解决问题（见后面的图27和图28）。


由于转型是可以向不同的两个方向进行的，假设一个构形向两个方向转型时，都是在第20次转化成了可以连续的移去两个同色的K—构形，那么，两个第19次之内（包括两个第19次）就有39个H—构形。把顺时针转型第19次后所得到的构形（因为第19次所得的图仍是H—构形，而第20次后的图就成了K—构形了（如图10）），再进行逆时针转型时，一定是在第40次转型后，图就会转化成一个可以连续的移去两个同色的K—构形（同样的，把逆时针转型第19次后所得到的构形再进行顺时针转型时，也会得到同样的结果），再进行两次空出颜色的交换，就可以给待着色顶点着上图中已用过的四种颜色之一，共计42次交换。
设构形逆时针转型的次数是X，顺时针转型的次数是Y，从上面的结果可以看出，对于任何5度构形，都有X≤40，Y≤40和X＋Y≤40的关系。再进行两次空出颜色的交换，共计交换总次数则是：X＋2≤42，Y＋2≤42和X＋Y＋2≤42。这就是由一个已知的构形构造转型交换次数不超过42次的不同构形的原理。
当然在转型过程中，若所得到的图中含有经过围栏顶点的环形链时，也可以交换环形链内、外的任一条相反链，使图变成可约的构形，提前结束转型。
3、4  几个需要交换20次以上才能空出颜色的构形：

我们先给出一个逆时针转型时总交换次数是21次的构形（如图11，a），读者可以验证一下，是不是需要21次交换。再把这个构形进行顺时针转型，在第7次交换时就空出了颜色，那么第5次交换就是一个可以连续的移去两个同色的构形，则前4次交换所得的图分别是CDC型、ABA型、DCD型和BAB型的5度构形。对这些图再进行逆时针转型时，就是分别需要总交换次数是22次、23次、24次和25次的构形。图11，b就是逆时针转型时，需要25次交换才能空出颜色给待着色顶点的5度构形。
请注意，图11的这两个构形中都含有环形的C—D链，是可以用断链法很快解决问题的。为什么我们不这样去作，而要进行多达20次以上的连续转型交换呢？是因为有些人不但把所含有A—C和A—D两条相交叉链的构形统统都定义为H—构形，而且又把除了Errera—图构形以外的其他H—构形也都统统叫做Z—构形的，并且认为统统都得用转型交换的方法来解决。所以我们所构造出来的图中虽然也含有环形链，也不去用断链交换法去解决，仍把它看成是Z—构形，而用连续的转型交换法进行解决的。这几个图连续转型交换的总交换次数都大于20，这就说明了有些人所说的Z—构形只有15类和最大的总交换次数不大于16的结论是错误的。
3、5  5度构形转型交换次数一定有限的实践验证：

我们可以仿照敢峰先生构造终极图（即Errera—图）的办法，先画一个非常一般的不含连通链的H—构形，然后进行转型交换，每交换一次，都要人为的在平面图范围内再构造成H—构形。直到在平面图范围内不可能再构造成H—构形，图成为可约的可以连续的移去两个同色的K—构形为止。
图12是两个一般的无环形链的H—构形，左右结构正好是相反的,实际上同一个构形，所以我们只要研究图12，a就可以了。
现在我们对图12，a进行逆时针转型交换如下：

第一步，对图12，a从顶点1开始交换B—D链，得到的图13中虽然已生成了从顶点3到顶点5的连通的B—C链，但图却转化成了一个DCD型的H—构形，并且已经是一个可以连续的移去两个同色D的K—构形了。这一点可以从第二步转形交换得到的图14中没有形成从顶点1到顶点3的连通链可以看出。

第二步，对图13从顶点5开始交换D—A链，得到的图14中没有生成从顶点1到顶点3的连通链D—B，应该说问题已经可以解决。但在平面图范围内还可以构造出从顶点1到顶点3的D—B连通链（如图15），这是一个ABA型的H—构形。
第三步，对图15从顶点2开始交换A—C链，得到的图16中也没有生成从顶点4到顶点1的连通链A—D，问题也应得到解决。同样的，在平面图范围内也还是可以构造出从顶4到顶点1的连通的A—D链的（如图17），这是一个CDC型的可以连续的移去两个同色C的K—构形，而不再是H—构形了。

第四步，对图17从顶点5交换C—B链，得到的图18中虽没有生成从顶点2到顶点4的连通链C—A，但在平面图范围内再不可能构造从顶点2到顶点4的连通链C—A了，因为其前面有一条连通的相反色链B—D在阻隔着，C—A链是不可能通过的。很明显的是一个只有一条连通的B—D链的K—构形了。

第五步，对图18再从顶点2交换C—A链，就连续的移去了图16中的两个同色C，把C给待着色顶点V着上（如图19）。着色结速。
以上只进行了三次转型交换，加上最后的两次交换，共计是五次交换。这就是5度构形的最大交换次数。以上是对图12按逆时针转型交换的，若按顺时针转型交换时，也会得出同样的结论（如图20到图26）。请读者自已也再试一试。



顺时针转型也只进行了三次转型交换，加上最后的两次交换，共计也是五次交换。两个方向的转型交换得出相同的结果，这就说明5度构形的最大交换次数的确是不大于5的。如果把图12的任意图变成极大图时，则交换的次数将会更少。这就从对构形的着色实践上验证了5度构形转型交换时的最大交换次数一定是“有限的”，这个“有限”的上界是5，最大也决不会超过42次。
对图9，c的轴对称的5度构形，进行转型交换（如图27），第4次转型得到一个可以连续的移去两个同色B的构形（如图27，d），再交换两次，空出了B（如图7，f），共计6次交换，远小于42次。



但该图却在第3次转型后，形成了具有环形链的构形（如图27，c和图28，a），然后按有环形链的构形去解决，5次交换就可解决问题。如果把该图某一个方向的第3次转型后的图（如图27，c）再进行相反方向的转型时，则总共只要9次交换就可以解决问题，距上界42次仍相差很远。

4、除了有环形C—D链的九点形构形仍是H—构形外，其他的九点形构形都是K—构形：
如图28，b和图29都是“九点形”构形，可以看出，图29，a、图29，c和图28，b均变了可以连续的移去两个同色B的K—构形；而只有图29，b仍是H—构形（有环形C—D链的H—构形，赫渥特图就可以简化成图29，b），不可能连续的移去两个同色B，只能通过交换C—D环形链内、外的任一条A—B链后，图才能变成K—构形而可约。

然而这些九点形构形中却都含有连通且相交叉的A—C链和A—D链。这一现象再一次说明了连通且相交叉的A—C链和A—D链只是构成H—构形的必要条件，而并非是充分条件。没有它，不可能构成H—构形，但有了它的构形却不一定就都是H—构形。
5、平面图的着色流程：
图30就是平面图的4—着色流程图。

首先把着色时可能遇到的待着色顶点分为染色困局顶点和非染色困局顶点。非染色困局顶点用坎泊链法（即坎泊已用过的交换法或空出颜色的交换法），染色困局顶点用非坎泊链法（即坎泊没有使用过的颜色交换法）。非染色困局的顶点包括度是小于等于4的顶点和围栏顶点占用颜色数小于等于3的顶点。其他的围栏顶点占用了4种颜色的待着色顶点，不管其是不是H—构形，都按染色困局顶点对待。然后再按各种染色困局的解决办法分别解决。
6、四色猜测是正确的：
现在，在“染色困局”的各种情况下的构形都是可约的了（也包括坎泊早已证明了是可约的4度以下的构形），任何平面图就都是可4—着色的了。平面图的四色猜测也就得到了证明是正确的。当然地图的四色猜测也就是正确的了。从提出至今已有一百六十七年历史的地图四色猜测，就可以上升为地图四色定理了。结束这一个半世纪的证明历史了。

雷  明
二○一九年八月十六日于长安

注:这篇文章是由《四色猜测证明方法的创新》（二○一九年八月十六日在《中国博士网》上发表过，网址是：）和《回答张彧典先生的42次颠倒的证明问题》（二○一九年八月十七日在《中国博士网》上发表过，网址是：）两篇文章合成的。

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，