待着色顶点移动法证明四色猜测

雷明85639720

待着色顶点移动法证明四色猜测
雷  明
（二○二一年八月十五日）

在对极大平面图的着色过程中或者到了最后，一定会遇到一个周围顶点都已全部着了颜色的顶点。把这样的还有一个顶点未着色的、别的顶点都已用四种颜色正确着色的图，就叫构形，把未着色的顶点叫待着色顶点，与其相邻的已着色的顶点叫围栏顶点。
1、任意度的待着色顶点的直接着色：
待着色顶点的度是小于等于3或围栏顶点已占用的颜色数小于等于3的待着色顶点，是可以直接着上四种颜色之一的。而待着色顶点的度是大于等于4或围栏顶点已占用完了四种颜色的待着色顶点，就不可能直接着上四种颜色之一了。但可以用待着色顶点移动的办法，使其移动到度是小于等于3的顶点或者围栏顶点占用的颜色数小于等于3的顶点上，再直接着色。因为任何平面图中一定存在度是小于等于5的顶点。
2、颜色冲突构形：
但这种度是小于等于5的顶点，却不一定是全部都存在于同一个图中的。如二十面体中就只有5度顶点，再无别的任何度的顶点；又如八面体，其中也只有4度顶点，再无别的任何度的顶点。这两个图都是独一无二的，再没有这样的全是度为4和5的顶点的极大平面图了。这也就是说，任意的极大平面图中，一定都会含有度是小于等于5的顶点的，但不一定每种度的顶点都一定同时存在。当遇到度是4或5的顶点作待着色顶点，其围栏顶点又占用完了四种颜色时，就把这样的构形就叫做颜色冲突构形。虽然有颜色冲突问题的存在，但在对某一个图着色时，由于着色人的不同，着色的方法不同，着色的路线不同，有时是可能会遇到颜色冲突问题，但有时却不一定都能够遇到。也并不是每一个图，每次着色都会遇到的。但是研究如何解决颜色冲突问题的方法还是很有必要的，也是少不了的。否则当遇到了颜色冲突问题时，将束手无策，无从下手。
3、待着色顶点移动法：
现在我们就来集中力量用待着色顶点移动的方法来证明只含有4度顶点的八面体的极大平面图和只含有5度顶点的二十面体的极大平面图一定是可以运用待着色顶点移动的方法进行4—着色的问题了。
待着色顶点移动法，就是把围栏顶点中的某种颜色直接强行的给待着色顶点着上（通常是取围栏顶点中用的次数最少的一种颜色），在围栏顶点上重新产生一个或多个新的待着色顶点，把原来的围栏顶点的“色圈”打破，又重新产生新的围栏“色圈”。所以也有人叫移动法为破圈法或强行着色法。
严格的来说，待着色顶点是可以移向任何一个围栏顶点的，但由于围栏顶点中使用同一种颜色的顶点的多少不同，移去后产生的新待着色顶点的多少也就不同，所以在一般情况下，总是把待着色顶点移向所用颜色次数最少的围栏顶点。
待着色顶点移动后，产生的新待着色顶点，可能不是颜色冲突顶点，可以进行直接着色，一步移动成功；也可能仍是颜色冲突顶点，不可直接着色，需要多次移动后才可能成功。所以可以不可以把待着色顶点移向哪个围栏顶点，都是相对的而不是绝对的。
4、八面体的4—着色（全4度顶点的图的着色）
    八面体中各顶点的度都是4度，各顶点都处在一个平等的地位。因为八面体中只有6个顶点，当4个顶点各占一色时，其他的两个顶点，就是两个待着色顶点（如图1，a）。两个待着色顶点分别用V1和V2表示。四个围栏顶点，四种颜色，每个围栏顶点各占用一色一次。

把图1，a中围栏顶点中的A色给V1着上，产生新的V1待着色顶点（如图1，b）；因V1只与A、B、D三种颜色相邻，所以把V1直接着上C色即可（如图1，c）；现在V2只与着有三种颜色B，C，D的顶点相邻，所以给V2直接着上第四种颜色A即可（如图1，d）。八面体着色完成（图1，c中，边中所带箭头表未待着色顶点移动的方向，以下同）。
5、二十面体的4—着色（全5度顶点的图的着色）
二十面体的各顶点的度都是5度，也都是处在一个同等的位置上的。所以如果发生了颜色冲突问题，一定是有一种颜色占用了两次的情况（如图2）。图2是一个二十面体对应的极大平面图的构形，围栏顶点外的所有顶点都是已经4—着色过了的顶点，都有自已的颜色。因为其着什么颜色均不是确定的，所以就未标出实际颜色来。在以后的研究中可以随时标出。
整体解决二十面体的4—着色的思路是：由于围栏顶点以外的顶点都是已经可4—着色的，只是图中未标出其具体的颜色。所以我们可以构造出一个局部的色图（构形），当这个局部的构形若能给待着色顶点着上图中已用过的四种颜色之一时，则整个图的可4—着色问题也就决了。但如果这个局部的构形的待着色顶点不能解决4—着色问题时，却不等于整个图就不能解决4—着色的问题。因为图中还有很多的顶点着了什么颜色还是不清楚的。这时就得对各局部构形进行组合后再进行具体的分析。若仍不能解决问题时，就继续把后一层的不能解决问题的各局部构形再进行组合，直到图中各个顶点都有了自已的具体颜色为止。这时再看待着色顶点能否通过移动的办法，着上图中已用过的四种颜色之一。若能，则是成功的；若不能，则是失败的，或者是二十面体就不可能4—着色。成功中只要是有一次是成功的，就算是成功了，它至少说明二十面体是可以4—着色的。在组合的过程中，若出现了相邻顶点用同一颜色时，显然是不允许的事，一定要舍去；若出现了同一顶点用两种颜色时，则要分别进行组合，分别对待。

上面的八面体，比较简单，只有6个4度顶点，除了一个4—圈的4个顶点用了4种颜色外，其他的两个顶点都是发生了颜色冲突的待着色顶点。而这里的二十面体却比较复杂，除了待着色顶点和5 个围栏顶点外，其他的顶点虽是可4—着色过的，但却不知道其具体都是什么颜色。只能用构造局部的构形，以及局部构形的组合构形进行分析解决。这种办法应该是更具有一般性的，是比较好的一种证明方法。只要最后的组合，达到了二十面体的12个顶点，且各顶点的度都是6的极大平面图时，组合体能够进行4—着色，就说明各顶点都是5度的二十面体是能够4—着色的。
5、1  待着色顶点V向单一色围栏顶点的移动：
5、1、1  V→A，两种情况。如图3，a，图3，b。均不可移动。因为移动后图仍是一个颜色冲突构形。


5、1、2  V→C，三种情况。如图4，a，图4，b，图4，c。只有图4，a可以解决问题，而其他两图均不可移动。
5、1、3  V→D，也是三种情况。如图5，a，图5，b，图5，c。也只有图5，a可以解决问题，而其他两图均不可移动。
5、2  V→双色顶点B，两种情况。如图6，图7。都不可能移动两个同色B。



5、3  双色B的各种组合形式：
5、3、1  图7的两种情况分别与图6的三种情况进行组合：
5、3、1、1  图7，a与图6，a的组合，如图8，a，可移动，可以解决问题。
5、3、1、2   图7，a与图6，b的组合，如图8，b，相邻两顶点出现了同一颜色，不可能存在，舍去。
5、3、1、3   图7，a与图6，c的组合，如图8，c，相邻两顶点出现了同一颜色，不可能存在，舍去。
5、3、1、4   图7，b与图6，a的组合，如图8，d，相邻两顶点出现了同一颜色，不可能存在，舍去。
5、3、1、5   图7，b与图6，b的组合，如图8，e，可移动，可以解决问题。

   

5、3、1、6   图7，b与图6，c的组合，如图8，f，是不可能移动两个B的。
只有图8，f是不可移动双B的，可与后面的不可移去C和D的局部构形再组合。
5、4  单一色C和D的局部构形的组合：
V向单一色C的移动中，图4，b和图4，c均不可移动（如图9）；V向单一色D的移动中，图5，b和图5，c也不可移动（如图10）。四个局部构形的组合分别是：


5、4、1  图4，b与图5，b的组合，如图11，a。不可解决问题。

5、4、2  图4，b与图5，c的组合，如图11，b。出现了同一顶点用两种颜色（加大顶点所示）和相邻顶点用同一颜色（加粗边）的情况，不可能存在。相邻顶点用同一颜色可以舍去。但当把图中最下面的顶点选B色后，却是可以的。V移向C是可以解决问题的。
5、4、3  图4，c与图5，b的组合，如图11，c。既出现了同一顶点用两种颜色，又出现了相邻顶点用同一颜色的情况，不可能存在。相邻顶点用同一颜色可以舍去。但当把图中最下面的顶点选B色后，却是可以的。V移向D是可以解决问题的。

5、4、4  图4，c与图5，c的组合，如图11，d。围栏顶点的C和D都不可能移去，也即V不可能移向这两个顶点,即不能解决问题。
这里只有图11，a和图11，d是不可移动C和D的，可与前面的不能移动双B的图8，f进行局部构形的再组合，共有四种情况（如图12）。其中一种（如图12，c）中有相邻顶点用同一种颜色的情况，应舍去。图12中只有11个顶点，距二十面体还差一个，也还有5个顶点的度是4。若在图的下方B点或A点的下边，再增加一个顶点，并与5个4度顶点用边相连，则这5个4度顶点就都变成了5度顶点。正好就是一个二十面体对应的极大图，各个顶点的度都成了5。图13，a与图13，b中所增加的这个顶点相邻的5个顶点也是占用了四种颜色，这个顶点正好也就是一个颜色冲突顶点，只好用V2表示；而图13，d中所增加的这个顶点相邻的5个顶点却只占用了C、D、A三种颜色，给该顶点可直接着上B色。同样的，图13，c也应是舍去了的。




5、5  现在就对图13的三个图（构形）进行着色如下：
5、5、1  对图13，a用移动法着色
5、5、1、1  V→C，如图14。



5、5、1、2  V→D，如图15。



5、5、2  对图13，b用移动着色
5、5、2、1  V→C，如图16。图16，d与图14，c相同了，继续按图14，c的办法移动就可以了。


5、5、2、2  V→D，如图17。



5、5、3  对图13，d用移动着色
5、5、3、1  1  V→C，如图18。



5、5、3、1  1  V→D，如图19。



以上我们只对图13，a,图13，b和图13，d作了待着色顶点V向围栏的C和D顶点的移动，同样的，待着色顶点也是可以向围栏的A移动的，读者可以自已作一下。
以上对八面体和二十面体的可4—着色的成功，说明在任何情况下，只要有颜色冲突的5度和4度的待着色顶点时，就一定能通过待着色顶点移动法，找到围栏顶点只用了三种及三种以下的颜色的顶点，是可以直接的进行着色的。这就为从理论上证明四色猜测的正确打下了坚实的基础。
以上的着色都说明了八面体和二十面体都是可4—着色的。也说明4度和5度的颜色冲突构形，在纯4度和5度顶点的图中都是可以解决的，也就说明了4度和5度的颜色冲突构形，在有更低度的顶点存在的图中更是可以解决的。
6、四色猜测的证明：
现在，我们已经对各种情况下的各种度的待着色顶点通过移动法进行了4—着色，说明极大平面图的任何构形都是可约的，极大图的四色猜测也就是正确的，且地图的四色猜测也就是正确的了。进而也就证明了任意平面图的四色猜测也是正确的了。
7、还要说明的问题：
到这里，是乎是四色问题已经就解决了。其实还并没有解决。为什么？我们想一想，如果我们最把待着色顶点只能移到某个4—度或5—度的顶点之上，这个顶点的围栏顶点也已是占用了四种颜色时，怎么办呢？虽然我们可以再把待着色顶点进行移动，想使它能够移动到围栏顶点只占用了三种颜色的顶点之上。若能移到，感谢老天爷，问题了解决；但若移动不到呢？所以说，到这里，四色问题还是没有得到彻底的解决。如何办呢？还得使用不可免构形可约的方法，通过对已着色的顶点的颜色进行调换的方法，把围栏顶点的颜色由三种颜减少到三种，把空出来的一种颜色给待着色顶点着上，问题才能得到彻底的解决。
解决的方法可以参看雷明在二○二一年七月十四日所写的《四色猜测是正确的，四色足矣！》一文，发表在《数学中国》网上，网址是：http://www.mathchina.com/bbs/for ... &extra=page%3D1。
4—轮构形和无双环交叉链的5—轮构形，早在1879年坎泊就用可以空出颜色的颜色交换技术就已经解决；所以在遇到5—轮构形时，首先要看其是否是含有双环交叉链：若没有，问题也是可以解决的；若有，再看其是否是可以连续的移去两个同色：若是，把两个同色移去，问题也就解决了；若不是，就再看是否是含有经过了关键顶点的环形链的构形：若是，就用断链交换法进行解决；若没有，就用转型交换法进行解决。都可以使构形转化成无双环交叉链的可约的K—构形，再用空出颜色的颜色交换法，空出一种颜色给待着色顶点，这样才算是彻底的解决了四色问题的证明问题。

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

附录：
现在再对图13的三个图（构形）用使颜色交换法进行着色如下：
1、对图13，a用交换法着色
图13，a是一个只有一条连通链A—D的而无连通A—C链的构形（如附图1，a），可以空出A、C之一给待着色顶点V。从C点开始交换C—A链，C变成A，空出C给V着上（如附图1，b）。这又是一个以V2为待着色顶点的颜色冲突构形。有D—A链和D—B链的“十”字相交叉，不可能移去两个同色B，只能移去A、B、C三色之一给V（如附图1，c，附图1，d，附图1，e，附图1，f）。



对附图1，a若从A点开始交换A—C链，A变成C,空出A给V着上（如附图2，a）。这是一个非颜色冲突构形，待着色顶点V2只与A、B、D三种颜色的顶点相邻，可直接给V2着上C（如附图2，b）。

2、对图13，b用交换法着色
图13，b是一个有两条连通链A—C和A—D,但两链中途却不相交叉的可以连续的移去两个同色B的构形（如附图3，a）。连续的移去两个同色B，并把B给V着上后，图又是一个以V2为待着色顶点的颜色冲突构形（如附图3，b）。有A—C链和A—D链的“十”字相交叉，不可能移去两个同色A，只能移去B、C、D三色之一给V（如附图3，c，附图3，d，附图3，e，附图3，f）。



3、对图13，d用交换法着色
图13，d是一个有两条连通链B—C和B—D，且两链中途又是“十”字相交叉的不可以移去两个同色B的构形（如附图4，a）。只能移去A、C、D三色之一（如附图4，b,附图4，c,附图4，d，附图4，e）。








   

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，