四色猜测是正确的，四色足矣！

雷明85639720

四色猜测是正确的，四色足矣！
雷  明
（二○二一年七月十四日）

1、把无穷问题转化成有穷的问题
四色问题从给地图的染色而提出，证明时还得从给地图的染色开始。四色猜测是在1852年由英国的绘图员法朗西斯在绘制英国地图时提出的。说的是任何一张行政区划地图，最多只用四种颜色，就可以把地图中的各个区域染成不同的颜色，且使得有共同边界相邻的两区域的颜色有所不同。
地图是一个含有“无顶环”的无割边的3—正则的平面图。地图的对偶图是一个带有悬挂顶点的极大平面图。这里的“无顶环”和悬挂顶点都是指实际地图中的“国中之国”。给地图的面上的染色就是对其对偶图的顶点着色。这就把一个地理问题转化成了数学问题。
由于极大平面图的每一个顶点均是处在一个“轮”形图的中心位置，所以对极大平面图进行着色时，着色过程中或到达最后时，总都会遇到与要着色的顶点所相邻的顶点全都已着上了四种颜色之一的情况。把这种还有一个顶点未着色，且该顶点又是处在一个轮的中心位置的图就叫做“构形”。未着色的顶点叫待着色顶点，与待着色顶点相邻的其他顶点都叫围栏顶点。由于构形的待着色顶点都是处在一个轮的中心位置的，所以这种构形也就叫轮构形。
由于任何平面图中都一定含有至少一个顶点的度是小于等于5的，所以度是小于等于5的顶点也就是平面图的不可避免顶点。以不可避免顶点为待着色顶点的构形就是平面图的不可避免构形。可见平面图的不可避免构形的待着色顶点的度都是小于等于5的，从0到5共六种。由这六种度的待着色顶点的构形所组成的集合，就是坎泊已经给出的不可避免构形集。也就是说，平面图中6度以上的待着色顶点的构形是可以避免的。因为在着色时，总可以把待着色顶点放在度是小于等于5的顶点之上；或者在着色过程中，遇到了6度以上的顶点作待着色顶点时，总是能够通过移动的方法把待着色顶点移动到度是小于等于5的顶点之上的。
研究平面图的着色，只要研究度是小于等于5的六种待着色顶点是否可约（即是否可4—着色）就可以了。这就把待着色顶点的度可以是无穷大的无穷种构形的无穷问题，又转化成了待着色顶点的度只是小于等于5的六种构形的有穷问题了。只要证明了这五种不可避免的构形都是可约的，极大平面图的四色问题也就解决了。当然地图的四色问题也就解决了。因为可4—着色的极大平面图，经去顶或减边后得到的任意平面图的色数，只会比极大图更少而不会再增大，所以解决了极大平面图的四色问题，同样也就解决了任意平面图的四色问题。
2、极大平面图的各种不可避免构形及其可约性的解决办法
待着色顶点的度是小于等于5的轮构形如图1—图6（各围栏顶点上所画的小短线，表示该顶点还连接着别的顶点），其待着色顶点V的度都是小于等于5的。其中图1—图4中的围栏顶点所占用的颜色数都是小于等于3的，待着色顶点V也都是可以直接着上四种颜色之一的。而只有图5和图6及其以后的图，其围栏顶点所占用的颜色数都已达到了4，待着色顶点V似乎是无色可着了。把这种情况就叫颜色冲突现象。但这种颜色冲突现象是可以运用坎泊在1879年所创造的颜色交换技术，从围栏顶点中空出一种颜色来，给待着色顶点V着上的。


把一条用两种颜色交替着色的道路叫做色链，简称链。交换该链中各顶点的颜色，可以达到改变链中任何一个顶点的颜色的目的。这就是坎泊所创造的颜色交换技术的实质。
在四种颜色中，把由A和B构成的色链和C和D构成的色链叫做一对相反链。因为相反链中没有相同的颜色，所以两条相反链是不能相互穿过的。当图5的4—轮构形中，没有从一个围栏顶点到其对角围栏顶点的连通链时，交换从任何一个围栏顶点出发的与其对角顶点的颜色所构成的色链，都可以改变该围栏顶点的颜色，而把该围栏顶点的颜色空出来给待着色顶点V着上。如果围栏顶点中有一条连通链时（如图7），而另外一组对角的颜色所构成的色链则一定不连通，交换从这一组不连通链的任何一个顶点起的对角链，也一定会空出一种颜色给待着色顶点V的。
对于图6的5—轮构形中，当没有从一个围栏顶点到其对角围栏顶点的连通链时，只能从围栏的A色顶点，或C色顶点和D色顶点之一起，交换与其对角顶点的颜色所构成的色链，空出该顶点的颜色A（或C或D）给待着色顶点V。这样交换的次数是最少的。


图8、图9是有一条对角链连通的情况，可交换不连通的关于A的对角链，空出一种颜色给待着色顶点V着上。图10、图11和图12是有两条对角链连通的情况，也可交换不连通的对角链，空出一种颜色给待着色顶点V。
从对图8到图12的5—轮颜色冲突构形的着色中，我们发现连通链的起始顶点（围栏顶点A），连通链的末端顶点（围栏顶点C和D）以及两条连通链的交叉顶点A或B，是四个非常关键的顶点。只要这四个顶点的任何一个顶点的颜色发生了变化，图8到图12可分别变成不含有任何连通链的构形或只含有一条连通链的构形（如图13各图）；或者虽然仍有两条连通链，但却实质上不是“十”字相交叉的构形（如图13（四）的左图）。都可以分别从围栏顶点中移去一种颜色给待着色顶点V着上。但连通链是单边链时则不可这样做（如图14），因为这样做的结果只是把两种颜色分别进行了交换，并没有使构形发生实质上的变化。






对图12再进行变化，增加B—D边或链和B—C边或链，并把两条连通链上的C点和D点直接连结（如图15），也是可以通过交换邻角链A—B和C—D，以及从交叉顶点交换A—B链，把构形转化成无任何连通链的构形，或者无真正意义上的“十”字交叉的连通链的构形。但在图15的基础上再增加顶点时，就有可能使构形成为在交换了一条关于B的链，移去一个B后，却新生成了从另一个B点到其对角的连通链，而不能连续的移去两个同色B的构形（如图16，图17和图18）。
应该说图15以前的构形，坎泊在1879年都已经解决了，都是可约的，也都是可4—着色的。但坎泊的证明中唯独就遗漏了图16，图17和图18中的三种类型的构形。这三类构形中都含有双环交叉链A—C和A—D（如图中的加粗边所示）。而在赫渥特提出了赫渥特图以后，坎泊也不能对赫渥特的图进行4—着色。所以直到现在，从四色猜测提出至今已有169年过去了，四色猜测还没有得到证明是否正确。


3、有双环交叉链的颜色冲突的5—轮构形的解决办法
由于连通链与待着色顶点V构成的是一个环，以上图16，图17和图18中都有相互交叉的两条连通链，所以可以叫做含有双环交叉链的构形，（相应的，只有一条连通链的构形就可以叫做单环链的构形）。这三个图的共同特点就是：从一个B开始交换了一条关于B的链后，虽移去了一个B，但又新生成了从另一个B到其对角顶点的连通链，使得不能连续的移去两个B。
3、1、含有经过了关键顶点的环形链的构形的解决办法


如何解决这个问题，我们还是从改变关键顶点的颜色入手。图16中有一条环形的C—D链（见这里的图16中的加粗边），交换经过环内、环外的两个关键顶点A的任一条A—B链（如图19），就可以使原有的双环交叉链断开，成为含有另一类双环交叉链的构形（对图15（一）而言），可以移去A、C、D三色之一给待着色顶点V（如图20）；或者使构形转化成无任何环形链的构形（对图15（二）而言），则可以空出任何一种颜色给待着色顶点V着上。图17中有一条环形的A—B链（也见这里的图17中的加粗边），交换经过环内两个关键顶点的C—D链或环外的任一条C—D链，都可以使双环交叉链断开（如图21），成为虽然仍有双环交叉链，但实质上并不“十”字交叉的构形，是可以移去两个同色B的（如图22）。
图16和图17都是含有经过了关键顶点的邻角环形链的构形，解决时都是交换经过了关键顶点的另一对相反的邻角链，以达到断开双环交叉链的目的，所以该交换的方法叫做断链交换法（相应的以上坎泊所用过的交换方法可以叫做可空出颜色的交换法）。
图16 和图17只所以可以进行断链交换，使构形转化成无双环交叉链的可约构形，主要是因为有经过了关键顶点的环形链。该环形链链会把与其相反的另一种色链分成了环内、环外互不连通的两部分。交换环内、环外任一部分色链时，都不会连带到另一部分。被环形链分隔成了两部分的相反链至少有一个部分是通过了关健顶点的，交换了这一部分链后，就至少会有一个关键顶点（双环交叉链的共同起始顶点A或相交叉顶点A）或两个关键顶点（双环交叉链的两个末端顶点C和D）的颜色发生变化，这就保证了双环交叉链一定不会再存在。
还有一种情况是A—B环形链和C—D环形链同时都存在，但互不相交，而是以“同心园”的形式相互嵌套在一起（见文后的附图）。这种情况实际上分别属于有以上两种情况的环形链中的一种，可分别用交换C—D链和A—B链的两种不同的断链法进行解决。
1890年赫渥特构造的赫渥特图，就是含有经过了双环交叉链的两个末端顶点C和D的环形的C—D链的构形。在1992年时，雷明以及董德周分另都是用了交换C—D环形链一侧的经过了两链的交叉顶点A的A—B链的断链交换法对其进行解决的。还有1921年埃雷拉构造的埃雷拉图，则是一个左、右呈轴对称的含有经过了双环交链的共同起始顶A的环形的A—B链的构形。在1935年，欧文也就是用了交换A—B环形链一侧的经过了两链的两个末端顶点C和D的C—D链的断链交换法对其进行解决的。另外，敢峰先生在1992年构造并解决了他的终极图（与埃雷拉图相同的一个图），也是用同样的办法解决的。赫渥特图，埃雷拉图和敢峰的终极图均见文后附图。
3、2、不含有经过了关键顶点的环形链的构形的解决办法
图18则是无经过关键顶点的环形链的构形，A—B链和C—D链都只有一条，且是直链，无法进行交换，就是交换了也不起任何作用。没有经过关键顶点的环形链，也就不可能使用断链交换法。既然A—B链，C—D链，A—C链，A—D链都不可能交换，B—C链和B—D链又不可能进行连续的交换，那么，就只能先交换一条关于B的对角链，使构形的峰点和两个同色顶点都先发生变化。逆时针方向转型交换的是B—D链，构形转化成DCD型；顺时针方向转型交换的是B—C链，构形转化成CDC型。所以把这种交换的方法就叫转型交换法。

对图18进行逆时针转型交换时，一次转型后仍是一个DCD型的有双环交叉链而无环形链的构形（如图23）；第二次转型后，就转化成了一个只有一条连通链B—C的可约构形了（如图24），再交换一次，即可空出B或D给待着色顶点V。第一次转型后虽是一个含有双环交叉链的构形，但却也是一个可以连续的移去两个同色D的可约构形，但也可以人为构造连通链，构成H—构形，再继续转型。
对图18进行顺时针转型交换时，一次转型后虽仍是一个CDC型的有双环交叉链的构形，但却是一个有经过了关键顶点的A—B环形链的构形（如图25），可改用断链交换法继续进行解决；第二次转型后，就转化成了一个无任何连通链的可约构形了（如图26），再交换一次，即可空出一种颜色给待着色顶点V。

对图18进行逆时针转型，一次转型就是一个可以连续的移去两个同色D的可约构形；顺时针转型，一次转型则是一个含有经过了关键顶点的环形链A—B的构形，可以改用断链交换法进行解决；但是再进行一次转型后，也可得到一个无任何连通链的可约构形。虽然用转型交换法可以解决这种构形的可约性问题，但最大的转型次数是多少，还是没有得到证明。没有最大转型次数的转型，也可以认为转型次数一定很大很大，以至无穷，象埃雷拉E—图那样，永远的周期循环下去，总不得解。所以还必须对最大的转型次数进行证明。这个问题就留给下一节4中去专门进行证明。
1935年欧文构造的欧文图，是一个左、右呈轴对称的但不含有经过双环交叉链的关键顶点的环形链的构形。用连续的转型交换法，无论从那个方向进行转型，都是只用四次转型就转化成为一个可以连续的移去两个同色的可约构形。张彧典先生在二○一○年出版的《四色问题探秘》一书中的第八构形，是一个具有代表性的不含有经过双环交链的关键顶点的环形链的构形。也只能用这种转型交换的办法进行解决，而不能使用断链交换法。欧文图和张先生的第八构形图以及第八构形的放大图也均见文后附图。
当然，不含有经过了双环交叉链的关键顶点的环形链的构形还有别的解决办法。有两类顶点：

一类顶点如这里图18中的两个加大的顶点B和C，其度都是4，都是偶数度。与该顶点相邻的偶数个顶点，分别只占了两种颜色A与C和A与D，改变顶点B的颜色为D时，该构形就转化成了一个有C—D环形链的构形了（如图27）；改变顶点C的颜色为A时，该构形就转化成了一个有A—B环形链的构形了（如图28）。可见含有经过了关键顶点的环形链的构形和不含有经过关键顶点的环形链的构形也是可以相互转化的。
另一类顶点是，如图29中在A—D链通链上有一个顶点A是处在一个只占用了三种颜色的4—轮（偶轮）的中心顶点上，改变该顶点的颜色为C时，这条连通链A—D也就断开了，构形就转化成只有一条连通链A—C的可约构形（如图30）。
张彧典先生的《四色问题探秘》一书中的第八构形中，就含有第二类顶点。如该构形中的顶点A3，是处在一个B、D二色偶轮的中心顶点，把该顶点由A色改成C色时，图中的一条A—D链通链断开了，构形成为只有一条连通链A—C的可约构形。同样，张先生的第八构形的放大图中，还含有两个第二类顶点。当把局部环形链的中心顶点A（或D）的颜色改变为B后，就会使连通链A—C（或A—D）断开，图也就会成为只有一条连通链A—D（或A—C）的可约构形了。

3、3、含有经过关键顶点的环形链的“九点形”构形的解决办法

如果把图16，图17和图18三个图分别变成“九点形”构形时，则如图31，图32和图33所示。三图中虽然都仍然含有双环交叉链，但其中只有图16所对应的图31仍是不可连续的移去两个同色B的颜色冲突构形，而必须使用断链法解决外，其他两个图却都是可以连续的移去两个同色B的可约构形。
4、最大转型交换次数的证明
4、1、对角链转型交换的最大转型次数
在图24和图26中虽然都得到了可约的构形，按道理图18的构形就可以得到解决。但是为了寻求转型交换的最大转型次数，我们还要在平面图的许可范围内，再人为的构造从另一个同色顶点到其对角顶点的连通链，使构形仍然是一个含有双环交叉链的构形，且是一个不可连续的移去两个同色的颜色冲突构形，一直到在平面图范围内不能再构造连通链为止。再看最大的连续转型交换次数是多少。
现在仍以图18为例行进行逆时针方向的连续转型交换（如图34）。

第一次转型后是不需要人为的构造连通链的，以后的第二，第三，第四次转型，都是可以人为再构造出连通链的（说明这些次转型后，问题就可以得到解决。图中的细虚线边以及顶点都属于人为构造的连通链所增加的部分）。第五次转型后，在平面图范围内就不可能再构造出连通的B—C链了，因为图中已有一条连通的A—D链（粗虚线所示的边），两条相反链是不能相互穿过的，连通的A—D链已把B—C链的连通隔断了。这就说明了第四次转型后的构形是一个可以连续的移去两个同色B的BAB型的可约构形。
这四次转型每一次得到的都是一个无经过关键顶点的环形链的构形，也都是一个可以连续的移去两个同色的构形。第四次转型得到的是一个可以连续的移去两个同色B的可约构形，第五次转型实际上只是移去了一个B，第六次交换再移去另一个B，从而空出了颜色B。最后的第7个图并没有进行交换，而只是把颜色B给待着色顶点着上。一共转型了四次，共六次交换。


为什么最大的转型次数是4次，而不象埃雷拉E—图那样无穷的周期循环转型呢？因为5—轮构形转型中所得到的新的构形，只在BAB、DCD、ABA、CDC四种类型间进行转化，每进行一次转型，构形就是一种类型，四次转型是一个周期，最大也就只是转型4次，就应可以空出颜色B来了。绝对不会形成无穷的周期循环转型的现象，因为这里所研究的无经过关键顶点的环形链的构形根本就不具备E—图那样的产生周期循环转型的条件——含有经过了关键顶点的环形链。
以上是逆时针方向转型的结果，若对图18再进行一次顺时针方向的转型时（如图35），同样的也不管是生成还是不生成有经过了关键顶点的环形链，只要是在平面图范围内，能再构造出另一条连通链时，就继续再构造，直到不能再构造为止。一共只转型了三次（交换了五次）就空出了颜色D给待着色顶点着上。其结论与逆时针转型也是相同的，总的转型次数仍不大于4次，总的交换次数不大于六次。


4、2、邻角链转型交换的最大转型次数
以上我们研究无环形链的构形的转型交换时，都是用的对角链的交换，现在再改用邻角链进行交换，看一看是什么情况。以前对B—C（或B—D）链进行交换时是从右（或左）B开始进行交换的，现在则要从左（或右）B开始进行交换。
对图18的构形逆时针方向从左B对邻角链B—C进行转型交换时（如图36，所交换的邻角链用粗实线边表示），第一次转形得到的是一个含有双环交叉链的BDB型的H—构形（但其中已含有经过了关键顶点的A—C环形链，可以改用断链交换法进行解决），第二次转型得到的仍是含有双环交叉链的BCB型的H—构形，第三次转型得到的是一个只有一条连通链A—C的可约的BAB型的K—构形，第四次交换就空出了D色，最后第5图把D色给待着色顶点V着上即可。


若对图18的构形顺时针方向从右B对邻角链B—D进行转型交换时（如图37），一次转型就得到只有一条连通链C—A的可约构形，就可以解决问题。
邻角链转型，除了顺时针转型一次可解决问题外，逆时针转型最多也只要进行三次转型就可以了。但以上只是对图18的构形进行了转型，却并没有对转型后的含有双环交叉链的构形进行分析，看其是不是可以连续的移去两个同色的可约的K—构形。如果是，就结束转型；如果不是，则再继续转型。因为第三次转形的结果已经是一个只有一条A—C连通链的可约的K—构形了，所以，现在只要对第一、第二次转型的结果进行分析就可以了。

具体分析中可能有两种情况，一种是交换了一条关于两个同色顶点的对角链后，会新生成从另一个同色顶点到其对角顶点的连通链，另一种是不会新生成这样的链。若能生成这样的链，就是H—构形，还得继续的进行邻角链转型；若生不成这样的链，转型后的构形就是可以连续的移去两个同色的可约的K—构形，问题也就得到了解决。这时，可能有人就要说话了，也可以再人为的构造这样的连通链嘛。是，是可以再构造的。但人为的构造了这种连通链后，构形就变成了另外的一个构形了，可以另当别论。
因为，我们这里说的是邻角链的转型交换，而不是对角链的转型交换。对角链的转型交换，本来就存在着会不会新生成从另一个同色顶点到其对角顶点的连通链的问题，是不需要检验的。若生成了就一定是H—构形，一定是不能连续的移去两个同色的构形，就必须继续的进行对角链的转型；若生不成时就一定是K—构形，一定是可以连续的移去两个同色的构形，可以接着从另一个同色顶点再进行交换，空出两个同色，终止转型。问题也就了得到解决。在这里，检验的对象是“对角链”“转型前”的构形，而检验的目的则是为了在没有新生成连通链时，人为的构造连通链，为了寻找转型的最大次数。
而现在，我们要所进行的工作却是在对“邻角链”“转型后”的“含有双环交叉链”的构形进行检验，看其是否是可以连续的移去两个同色的可约K—构形。如果不是，就继续进行邻角链转型，继续寻找最大转型次数；如果是，也就终止转型。问题也就得到了解决。因为在邻角链转型过程中，两个同色始终是不会改变的，一直都是两个B，不存在只剩下一个同色B的情况，所以也不需要再人为的构造从另一个同色顶点B到其对角顶点的连通链来寻找最大转型次数的问题。而在这里，检验的对象是“邻角链”“转型后”的构形，与上面的对角链转型检验的检验对象是“对角链”“转型前”的构形根本就不是同一个概念。所以，在这种情况下，是不再需要构造连通链的。如果给还需要进行继续转型，该转型的构形则应是“上次”转型后的构形，即检验前的图36（一）中的两个有双环交交叉链的构形，而不是检验后得到图38（一）或图39（一）中的那个可以连续的移去两个同色的、但又可以构造连通链的构形。
以下分析中的图38（一）和图39（一）分别是对图18的构形的第一次和第二次邻角链转型的结果是否是可以连续的移去两个同色的分析；图38（二）和图39（二）则分别是对以上两个分析中认为是可以连续的移去两个同色的构形连续的移去两个同色的具体过程。
第一次转型的结果分析如图38。


既然两次转型后的结果都是一个可以连续的移去两个同色的可约构形，那么就应该说图18的无经过关键顶点的环形链的构形逆时针邻角链转型时，一次转型也就可以解决问题。
第二次转型的结果分析如图39。


从以上的分析中可以看出，这样的转型交换，无论是逆时针方向还是顺时针方向，都是在一次转型后，就都是一个可以连续的移去两个同色的可约的K—构形。
也可以看出，这种转型交换的结果，各次交换所得到的构形都是双B夹×型的构形，只有A、C、D三种颜色轮流作构形的峰点，三次交换则是一个周期。正好第三次交换得到的是一个BAB型的构形（如图36（二）中左边的第3图），与图18的原构形的类型BAB是相同的。所以这种转型交换的方法最大的转型次数也就只是3次。
图36对图18的构形进行了连续的邻角链的转型，在不超过3次转型时，就得到了只有一条连通链的可约构形，解决了问题。而图39对图36中第二次转型的结果进行的分析，也是在不超过3次（实际上是两次）转型时，就得到了可以连续的移去两个同色的可约构形，也解决了问题。二者都达到了同样的可4—着色的目的。
还可以看出，邻角链转型交换要比前一种对角链转型交换简单得多，最大交换次数只是3次，而不是4次，不但最后空出颜色的交换也只要一次而不再是两次了，而且还甚至只转型一次，就可以使构形转化成可以连续的移去两个同色B的构形（如图36中间的第1图）。
4、3、无经过关键顶点的环形链的构形都是可约的
通过以上的证明，可以看出无经过关键顶点的环形链的构形也都是可约的，并且必须是要用转型交换的方法。转型的最大次数只是有限的4 次，绝对不会象埃雷拉E—图那样产生无穷的周期循环转型的现象。
5、四色猜测是正确的
现在我们已经证明了坎泊的平面图的不可避免构形集中的各种不可避免构形都是可约的了，特别是被坎泊漏掉了的含有双环交叉链的5—轮构形也都是可约的了。我们在证明时，把该类构形分为两类，一类是含有经过了关键顶点的环形链的构形，另一类是不含有经过关键顶点的环形链的构形。只有两种不同的情况，不是“有”就是“无”，非此即彼，不可能再有遗漏，也就不可能再有别的类型了。可见该类构形的这个不可避免构形集是完备的，可信的。然后再把含有经过了关键顶点的环形链的构形，再细分化为只含有环形链C—D的构形和只含有环形链A—B的构形两种，以及以上两种不同环形链都同时含有、但却不相交的三种构形（这后一种情况也都是分别属于前两种情况之一的）。这里也没有存在遗漏的地方。由这三种构形构成的含有经过了关键顶点的环形链的不可避免构形的集合也是完备的，可信的。这些不可避免构形在解决时，各自都有各自独特的解决方法，也都是可约的。现在，平面图的各种不可避免的构形在各种情况下的颜色冲突问题都已经解决了，这也就证明了四色猜测是正确。四色足矣！


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


附图：（见下页）







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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

wlc1

三色足矣

雷明85639720

,,,,,,,,

wlc1

！！！！！！！！！！！！！！！！！！！！！！！！！