用逆向思维的方法证明四色猜测（中等篇幅）

雷明85639720

用逆向思维的方法证明四色猜测
雷  明
（二○二一年六月一日）

目前虽然已有很多人都宣布自已证明了四色猜测是正确的，但还没有一个得到数学界的公认。既然不能直接证明任意的极大平面图都是可4—着色的，那么我们可以反过来想，能不能想办法只用四种颜色构造出任意的极大平面图来呢？若能构造，那不也就等于就证明了任何极大平面图都是可4—着色的吗？
1、解决四色问题还得从地图入手
这里所说的地图主要是指行政区划地图。地图是一个特殊的平面图，它是一个不含割边的、但可以含有“国中之国”的3—正则的平面图。地图中各顶点的度都是3，各面的边数都大于等于1（“国中之国”的边数等于1）。地图的对偶图是一个含有悬挂顶点（“国中之国”）的极大平面图，极大平面图中各个面都是3边形面，各顶点的度都大于等于1，且处在一个轮的中心位置。给地图中各面的染色就相当于对其对偶图的顶点着色。这就把一个地理学的问题转化成了一个数学问题。
四色猜测的提出因对地图的染色而开始，证明时也应从地图开始着手，即先从地图的对偶图——极大的平面图——的着色开始。证明了极大平面图的四色猜测是正确时，一个4—着色的极大平面图经“增顶”、“加边”、“去顶”和“减边”后，所得到的任意平面图的色数就只会是减少，而决不会再增加。这也就证明了任意平面图的四色猜测也是正确的。
如果我们能构造出色数总不大于4的任意的极大平面图，当然也就能说明极大平面图的四色猜测是正确的，地图的四色猜测也就是正确的了。
2、构造色数总不大于4的任意极大平面图
首先给出一个顶点数最少的极大平面图K3图（如图1），只用三种颜色着色。在其一个面内增加一个顶点时，就是一个K4图，仍是一个极大平面图。新增加的这个顶点与三种颜色的顶点全都相邻了，只能用第四种颜色（如图2），这就是地图中的“三国环国”的情况。

从现在起我们再继续在这个极大平面图K4图内增加顶点，可以增加在某一个面内，也可以增加在某一条边上。
增加在某一个面内的顶点，也只与着有三种颜色的顶点相邻，可以直接着上第四种颜色（如图3）；而增加在某一条边上的顶点V，已经与两个着有颜色的顶点相邻了，但这时的图却不是极大平面图（如图4）；把这个顶点再与其两侧未相邻的两个顶点用边连结起来后，图就成了一个极大图（如图5）。这时所增加的这个顶点就与四个已着色的顶点相邻了，其本身又是处在一个4—轮的中心位置上。这就是极大平面图的一个不可避免的4—轮构形，也是地图中的“四国环国”的情况。
在图5中，4—轮的围栏顶点已占用完了四种颜色，出现了颜色冲突情况（以后将可以看到，随着图中顶点数的增加，在边上增加顶点时，遇到颜色冲突的情况就会越来越少。如图12中在A—B边上增加一个顶点V，就不会遇到颜色冲突现象）。

但在图5中，有一条对角链B—C与V却构形了一个环（如图6中的加粗边），把由另外两个对角的颜色构成的相反色链A—D隔在了环的内、外两侧。从该环内、外两侧的任一个围栏顶点开始交换A—D链，都可空出颜色D（如图7）或A（如图8）给待着色顶点V着上。这说明在极大图的某一条边上增加顶点V时，一定是可以着上图中已用过的四种颜色之一的。4—轮构形的可约性问题坎泊早就已于1879年解决了。

以上所增加的顶点的度都是3和4，在增加新顶点的同时，其他原来在图中已有的部分顶点的度也在发生着增大的情况（如图2中A、B、C三个顶点的度都由原来的2增大到了3，图3中A、B、D三个顶点的度都由原来的3增大到了4；图5中B、C两个顶点的度也由原来的3增大到了4）。
当然，也可以在极大平面图内增加度是1和2的顶点，反映出地图中的“国中之国”和“两国夹国”的情况。如图3中增加的顶点C只与一个顶点D相邻时（如图9），新增加的顶点C就是其相邻国D的“国中之国”的情况；若图3中的C不与原来的顶点D相邻，而只与A和B相邻，且在顶点A到B之间再增加一条平行边时（如图10），顶点C就是一个处在A和B之间的“两国夹国”的情况。当然，其他的4度顶点也反映的是“四国环国”的情况。
同样的，在图4中，再在A到D间增加两条平行边时（如图11），待着色顶点V反映的也是相同的“四国环国”的情况。总之，图中最大有几度顶点，就说明地图中最大只有一个国家与几个国家相邻情况的区域。
3、四色猜测是正确的
以后照样不断的在新形成的极大平面图的某一个面内，或者在新形成的极大平面图的某一条边上增加新的顶点，所得到的图都一定还是极大平面图，待着色顶点都一定能够在图中已用过的四种颜色之内进行着色。无穷次的这样做下去，就可得到顶点数是任意多的，各顶点度也是任意大的极大平面图，所用的颜色数总是不会超过四种的。这不也就证明了四色猜测是正确的吗？
4、本证明方法与坎泊的不可避免构形可约的证明法的关系
坎泊的不可免构形可约法证明中的不可避免构形共有五种，即待着色顶点的度是从1到5的五种不可避免构形；而本证明法中只用到了一种待着色顶点的度是4的不可避免构形。坎泊的证明中既能遇到不可避免的4度待着色顶点的颜色冲突构形，也能遇到不可避免的5度待着色顶点的颜色冲突构形；而本证明只会遇到不可避免的4度待着色顶点的颜色冲突构形。解决不可避免的4度待着色顶点的颜色冲突构形时，却都是用了坎泊的颜色交换技术。所以说本证明与坎泊的证明既有区别又有联系，不能截然分开。本证明方法最重要的是避开了解决5度待着色顶点的颜色冲突构形。
5、解决不可避免的4度待着色顶点遇到颜色冲突的原理
在着色过程中，如果遇到了与要着色的待着色顶点相邻的顶点都已着色，且占用完了四种颜色的情况，就叫做发生了颜色冲突，或叫做染色困局。这时的待着色顶点该着什么颜色呢？似乎是无颜色可着了，只能着第五种颜色。其实并不是这回事！
把用两种颜色交替着色的一个序列叫做色链，简称链。把两种颜色全部都不相同的两条链叫相反链。把某条链中的两种颜色相互交换位置，可以改变链中某一顶点的颜色，这就是坎泊的颜色交换技术。
并不是所有的4度待着色顶点都能遇到颜色冲突问题（如图12）,而是在有些情况下，4度待着色顶点才会遇到颜色冲突问题。但这时待着色顶点外围的围栏顶点正好是一个顶点占用一种颜色。两对对角顶点的颜色所构成的色链一定是相反链。
相反链由于各链中两种颜色均不相同，所以两链是不可能相互穿过的。如果有一条链在围栏顶点外是连通的，并与待着色顶点V构成了一个环时，则另一条链一定是不连通的。如图6中以4度顶点V为中心的4—轮中，有一对对角顶点的颜色B和C构成的B—C链是连通的，并与V构成了一个环，这时，由另外两个对角顶点的颜色A和D构成的A—D链则一定是不连通的（当然也有两对对角顶点的颜色所构成的色链都是不连通的情况）。既是不连通的，那么就可以从A和D中的任何一个顶点开始交换A—D链，使V的围栏顶点中有两个顶点同着D色或A色，空出一种颜色A或D来，给待着色顶点V着上。4度待着色顶点遇到的颜色冲突问题就得到了解决。这就是坎泊解决4度待着色顶点颜色冲突问题的原理。即只要是由构形中的对角顶点的颜色构成的色链不连通，就可以对该链进行交换，空出颜色来给待着色顶点。
6、构造只用四种颜色着色的特定图
虽然如此，但在需要构造一个特定的图时，就要看要求的特定图中各顶点的度是多少，顶点与顶点间的相邻关系如何，真正使构造出来的图要与要求的图一模一样。比如正二十面体对应的极大平面图中有12个顶点，各顶点的度都是5度。在构造这个图的过程（如图13）中，当构造出了第11个顶点时，图中只有9个顶点是5度的，还有两个顶点的度是4，且还缺少一个5度顶点（如图13中的第7步）。这时就得把包括有这两个4度顶点在内的一个5边形（由三个三角形面构成）内的两条对角线去掉，使之真正成为一个5边形面。在这个面中再增加一个顶点就是5度顶点，正好图的顶点数也就达到了12个。同时位于5边形顶点上的那两个4度顶点也就都变成了5度顶点（如图13中的第8步），再给这个顶点着色就行了。需要注意的是，这个5度顶点也可能会遇到颜色冲突问题，用解决5度顶点的颜色冲突问题的办法（见较长篇幅的论文中）解决就行了。现在，一个可4—着色的正二十面体对应的极大平面图的着色也就完成了。





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

注：此文曾于二○二一年六月一日以《与张彧典先生共同商讨另一种证明四色猜测的方法》为题在《中国博士网》上发表过，网址是：
http://www.chinaphd.com/cgi-bin/ ... pic=4412&show=0，稍作修改并增加了图后，重新与二○二一年六月九日在《中国博士网》上发表，并把题目改为《用逆向思维构造可4—着色的任意极大平面图来证明四色猜测》，网址是：
http://www.chinaphd.com/cgi-bin/ ... pic=4414&show=0，这次又将短篇改为中篇，题目改为《用逆向思维的方法证明四色猜测》，并于二○二一年六月十六日在《中国博士网》上发表，网址是：
http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=4416

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，