H—构形一定是可约的——四色猜测的最简单证明

雷明85639720

H—构形一定是可约的
——四色猜测的最简单证明
（二○一九年四月二十二日）
（在这里我发不上图，请到《中国博士网》中去看）


1、把H—构形中的连通链断开就可以变成K—构形面可约
（1）H—构形的特征：4—轮以下的构形，坎泊1879年已证明是可约的了，同时也证明了5—轮中的K—构形也都是可约的，而只有5—轮中的H—构形被遗漏了，未被证明是否可约。当1890年赫渥特构造出了该构形后，坎泊与赫渥特两人也都不能对其4—着色。由于H—构形中有连通的A—C链和连通的A—D链，所以该两链均不能交换，也空不出A，C，D三种颜色之一给待着色顶点V。该两链不但有同一个起始顶点2A，且在中途还有交叉顶点8A（如图1），在交换了B—C（或B—D）链后，又会新生成连通的B—D（或B—C）链，因而不可连续的移去两个同色B。这就是当年坎泊与赫渥特两人都不能对该构形4—着色的根本原因。而这一原因就来自于A—C链和A—D链既是连通的，又是在中途又相交叉顶点的链。“连通”造成了不能空出颜色A，C，D三色之一，“中途相交叉”又造成了不能连续的移去两个同色B。
（2）H—构形是可约的：是不是H—构形就不能空出颜色而不可约呢？不是的。图中五边形（围栏）内除了6C—7D是单边外，其他各边均可看成是由该边两个端点顶点的颜色构成的色链。既然H—构形不能空出颜色的原因是来自于A—C链和A—D链的连通性和交叉性，我们就可以想办法使该两链变得不连通或者不交叉。顶点2A，8A，4D，5C，6C，7D都是处在连通且交叉的A—C链和A—D链上的关键顶点。2A既是两链的起始顶点，又是两链的共公顶点，8A是两链的交叉（公共）顶点，4D和5C分别是两链的末端顶点、且是相邻的两个顶点，6C和7D是两链中途的两个直接相邻的顶点。这些关键顶点颜色的改变，都会引起A—C链和A—D链的断开，构形变成K—构形而可约。

2、如何才能把H—构形中的连通链断开
如何才能使A—C链和A—D链断开，要看构形中的A—B链与C—D链的相互关系。由于A—B链和C—D链是一对相反链（即两链中的颜色完全不同），所以该两链是不会相交的。
（1）有A—B环形链的构形：在图２中有一条经过了围栏顶点1B，2A，3B的环形的A—B链（该A—B环也是经过了A—C链和A—D链共同的起始顶点2A的），使得经过A—C和A—D两链的末端顶点4D和5C的C—D链与A—B环内的C—D链不可能连通，交换A—B环内、外的任一条C—D链，都可以使A—C链和A—D链变得不连通，构形变成K—构形而可约。
（2）有C—D环形链的构形：而在图3中却有一条经过了围栏顶点4D和5C的环形的C—D链（该C—D环也是经过了A—C链和A—D链的两个末端顶点4D和5C的），也使得经过A—C和A—D两链的共同起始顶点2A的A—B链与C—D环内A—B链（即两链的交叉顶点8A，这是一个只有一个顶点的链）不可能连通，交换C—D环内、外的任一条A—B链，也都可以使A—C链和A—D链变得不连通，构形变成K—构形而可约。
（3）A—B链和C—D链都呈环形链的构形：如果构形中既含有环形的A—B链又含有环形的C—D链，从图4中的几种构形可以看出，各构形中至少有一条是经过了应该经过的围栏顶点的环形链。同样也可以在经过了构形的有关围栏顶点的环形链内、外交换其相反链（请注意，所交换的链上一定要含有位于A—C链和A—D链上的关键顶点，否则，交换后A—C链和A—D链也是不会断开的），也一定可以使A—C链和A—D链变得不连通，构形变成K—构形而可约。但不能交换未经过构形的有关围栏顶点的环形链内、外的相反链，因为这样交换后的构形中又会新生成两条既有共同起始顶点，中途又有交叉顶点的连通链，仍然是是H—构形。

3、不含任何环形链的构形的可约性
如果构形中不含有任何环形链（如图5），如何办？既然B—C链和B—D链不能连续交换，那么先交换其中一条总是可以的，先移去一个B，使构形转型，由BAB型转化为DCD型或CDC型，再根据转型后的构形进行分折，属于有那种环形链的构形，就用那种办法处理。
（1）转型交换：这种情况，构形中两种连通链都是直链，都不可能交换。现在就只能先交换一条关于两个同色B的B—C（或B—D）链，先移去一个B，使构形进行转型。转型分为连续的按逆时针方向或连续的按顺时针方向进行的两种转型。每进行一次转型,构形的峰点发生一次变化，同样的两个同色顶点也在发生着变化。任何一个5—轮构形都是可以从两个方向连续转型的，只是不同的构形两个方向的连续转型的次数都各不同罢了。但转型的最终结果都是一个可以连续的移去两个同色的K—构形。再交换两次，就可以空出两个同色来。给待着色顶点着上。

（2）一个无穷转型构形的例子：有没有可以无穷的转型下去，而不能空出颜色的构形呢？有。图4（c）就是一个例子，这个图是一个无穷的转型交换也不能空出颜色的构形。但每转型20次，就出现一次循环，构形又回到最初始的状态，各顶点的颜色与最初始时一模一样。这是因为5—轮构形有5个围栏顶点，且占用了4种颜色，要使得构形中各顶点的颜色，再反回到最初始状态的颜色时，必须得要5×4＝20次转型，20是一个周期。万春如所翻译的《一种试探式的平面图四染色》一文中所说的转型交换“将图形返回到原始染色所需的迭代次数是20的倍数”是正确的。
图4（c）虽然永远也转型不完，但它每一次转型的结果，却是一个只有一种经过了应该经过的围栏顶点的环形链的、如同图3和图4（c）的H—构形。交换该环形链内、外的任一条相反链，都可以使图变成K—构形而可约。转型每一步的结果，都是可约的。所以图4（c）的构形是一个可约的构形。该图从不同的两个方向转型，也都有同样的结果。
（3）无环形链的构形是不会无穷转型的：无任何环形链的构形是否也可以无穷的转型下去呢？不会的。因为图4（c）的构形，是一个有两种呈同心园分布的环形链的构形，而我们这里所说的构形，却是没有任何环形链的构形。如果这种构形也能够象图4（c）那样，无穷的转型下去，则该图中就应该有两条呈同心园分布的环形链，但它却一条环行链也没有。不符合无穷转型构形的条件。所以这种构形，在进行转型交换时，最多只要进行不大于有限的19次，就一定会变成一个可以连续的移去两个同色的K—构形。
4、任何5—轮构形最大的转型次数是不会超过19次的
（1）一个转型交换20次的图：图6(a)就是一个需要20次逆时针方向转型的构形。由于转型交换还可以顺时针进行，而这个构形顺时针进行转型时，却是一个可以连续的移去两个同色B的构形，所以图6（a）的构形实质上并不是H—构形而应该是K—构形。不能把同一个构形，既说成是H—构形，又说成是K—构形。一个构形只能属于一类。
（2）5—轮构形的转型次数不大于19：把图6（a）一次转型后的DCD型的构形图6（b），再整理成BAB型的构形（如图6，c）后，图6（c）就不再是K—构形而是H—构形了。因为该图顺时针转型时，是不可以连续的移去两个同色B的构形，一次顺时针转型后的构形才成为可以连续的移去两个同色的K—构形；相应的该图逆时针转型时，19次转型就可以转化成可以连续的移去两个同色的K—构形。两个方向转型的次数都没有大于19次这个上限，说明万春如所翻译的《一种试探式的平面图四染色》一文中所说的转型交换次数的上限是“所有的图都在一个固定的迭代次数（例如20）内终止”也是正确的。

（3）5—轮构形两个方向转型次数的和不大于20：如果一个图从某一个方向转型的次数X是1≤X≤19的，则它的逆向转型交换的次数Y也一定是1≤X≤19的。两个方向的转型交换次数的和X＋Y，也一定是不会大于20次的。一个可以连续的移去两个同色的K—构形，要空出颜色来，最少还需要进行两次空出颜色的交换。所以任何一个平面图构形最大的交换次数一定不会超过21次，就可以空出颜色来给待着色顶点的。由于21是一个有限的数字，这就说明了任何平面图，在不大于21次的有限次交换之内都是可约的。这就证明了四色猜测是正确的。

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

注：此文已于二○一九年四月二十三日在《中国博士网》上发表过，网址是：

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，否