四色猜测的纯理论证明 ——即不画图，不着色的证明办法

雷明85639720

四色猜测的纯理论证明
——即不画图，不着色的证明办法
雷  明
（二○二○年二月二十二日）

1、由于地图是一个无割边的3—正则平面图（各个顶点都是3—度顶点的连通图），其对偶图是一个极大平面图（各个面都是三边形面的连通图），给地图面上的染色就相当于给其对偶图——极大平面图的顶点着色。这就把一个给地图的面的染色的地理学中的问题，转化成了一个给图论中极大平面图的顶点着色的数学问题了。
2、如果极大图的四色问题解决了，那么由极大图经“减边”或“去顶”而得到的任意平面图的色数，就只会减少而不会再增加。这样，任何平面图的色数也就一定是小于等于4的。地图的四色猜测和平面图的四色猜测也就都是正确的了。
3、又由于平面图中一定存在着度是小于等于5的顶点，而极大平面图的每一个顶点又都是处在一个轮的中心顶点的位置。所以我们在给极大平面图着色时，总可以把最后一个需要着色的顶点（称为待着色顶点）放在度是小于等于5的顶点之上。即放在一个轮的中心顶点上。以这种轮的中心顶点作为待着色顶点的这种只有一个顶点未着色的色图，就是平面图的不可避免的构形。在极大平面图中这种轮的构形只有四种，即轮的中心顶点的度分别是2、3、4和5的构形。这就是坎泊证明了的、且是完备的平面图的不可避免的构形集。只要证明了这四种不可避免的轮构形都是可约的，即其待着色顶点都可以着上四种颜色之一，则极大平面图的四色问题就解决了。这就把一个无穷的问题转化成了一个有穷的问题了。
4、坎泊的证明已经解决了轮构形中心顶点的度是小于等于4的不可避免的构形是可约的，但对于5—轮构形的解决却遗漏了一种情况，即具有双环交叉链的情况。比如在BAB型的5—轮构形中，存在着A—C链和A—D链既有共同的起始顶点1A，中途又有共同的交叉顶点8A（如图1）的情况，其中V是待着色顶点。现在解决四色问题，主要就是要解决这一种构形的可约性问题。

5、把坎泊已证明是可约的不可免构形叫做K—构形，则其所遗漏的如图1的这种不可免的构形就叫做H—构形，因为是赫渥特所构造出来的。这一构形与坎泊证明过是可约的K—构形的不同之处，是A—C链和A—D链不但对于围栏顶点是连通的，而且在中途又有交叉。那么我们能不能想办法从根本上解决问题，让A—C链和A—D链彻底的断开，成为地地道道的K—构形呢？应该说是可以办到的。
6、分析：既然A—C链和A—D链都是连通的，那么改变其共同的起始顶点1A（或交叉顶点8A）或者两链的尾端顶点4D和5C的颜色，不就可以达到目的吗？如果图中有一条经过了构形围栏顶点的环形的C—D链（如图1中的实线环），则交换环内、环外的任一条A—B链，就可以使1A或者8A的颜色改变为1B或8B，双环交叉链就均断开了，图也就变成了K—构形，一定是可约的；如果图中有一条经过了构形围栏顶点的环形的A—B链（如图1中的虚线环），则交换环内、环外的任一条C—D链，也就可以使4D和5C的颜色改变为4C和5D，双环交叉链也就均断开了，图同样也就变成了K—构形，也一定是可约的。这种方法叫“断链交换法”。相应的，也就把坎泊用过的交换叫做“空出颜色的交换”，也叫砍泊交换。但如果图中即没有A—B环，也没有C—D环（如图1中含有A—C链和A—D链以外的一实一虚的边）怎么办呢？这时就只有采用转型交换的办法，使构形进行转型了。可以证明这种转型是有一个最大的转型次数界限的，任一个无环形链的H—构形，都是可以在这个界限以内经这有限次的转型，转化成可以连续的移去两个同色的K—构形的。
7、转型交换就是从一个同色顶点开始，交换与其对角顶点的颜色构成的色链，使构形的峰点（两个同色顶点所夹的顶点）的位置和颜色都发生改变，同时两个同色顶点的位置和颜色也相应的发生改变。如从图1中的1B起交换B—D链，构形就变成了DCD型的构形了；从图1中的顶点3B起交换B—C链，构形就变成了CDC型的构形了。前者叫逆时针转型，后者叫顺时针转型。在转型的过程中，除了转化成可以连续的移去两个同色的K—构形外，还可以转化成有环形链的H—构形，可以继续转型，可以改换成断链交换法进行解决。
8、无环形链的H—构形有限转型最大转型次数的确定：有一个H—构形，就是雷拉图（如图2），其中含有经过了围栏顶点的A—B环形链，用断链法是可以解决问题的。但对这个图进行转型交换时，却是一个以每转型20次为一个周期的无穷循环的构形，转型的次数再多也是空不出颜色来的构形。但这个20次的周期，却为我们寻找无环形链的构形转型交换的最大次数提供了方便。

9、从转型交换的转型次数的有限与无限来分，可把构形分成有限转型的构形和无限转型的构形。要知道某一个构形是有限转型的构形还是无限转型的构形，至少要在进行了E—图转型的两个周期2×20＝40次转型后，才可以确定其是否是无限转型的构形，还是有限转形的构形。进入第三个周期的构形一定是无限转形的H—构形，否则在没有进入第三个周期（40次转型，包括第40次）前就转化成了可以连续的移去两个同色的构形，就是有限转型的构形。这时再进行两次坎泊的关于空出颜色的交换，就可以空出两个同色给待着色顶点着上。总共的交换次数是42次。
10、任何一个构形，从两个不同的方向（逆时针方向或顺时针方向）都可以进行转型，最后都一定可以得到可以连续的移去两个同色的构形，再进行两次坎泊的空出颜色的K—交换，就即可空出一种颜色给待着色顶点。这两个方向的转型次数的和也是不会大于40次的，整个的交换次数是不会大于44次的。这一情况说明了，一定是存在这样一个构形（不过我们现在还没有构造出这一构形），它是可以按某一种的方向（逆时针或顺时针）连续的移去两个同色的构形。对这个构形按其连续的移去两个同色的相反方向进行转型时，一定是会在第40次转型时，也能得到同样的是一个可以连续的移去两个同色的构形（该构形连续的移去两个同色时的方向与前者是相反的）。两个构形之间有39个不可空出任何颜色的H—构形。
11、对任何平面图着色时，不管用什么样的方法着，怎么着，但最后都一定要遇到最后一个顶点要着色，这个顶点就是一个不可免的构形的待着色顶点。看这个顶点是属于那一类不可免的构形，就用相应的解决办法去解决，把其着上四种颜色之一。这就是在着色的过程中对四色猜测的证明。对每一个图进行的着色，都是一次证明的过程。

雷  明
二○二○年二月二十二日于长安

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，，