再谈构形与不可免构形——兼论四色猜测的证明

雷明85639720

再谈构形与不可免构形——兼论四色猜测的证明
雷  明
(二○二○年三月二十日)

有些研究四色问题的人，对构形和不可免构形至今没有弄明白，问我如果遇到你那几种情况的组合时怎么办呢？我不明白他的意思是什么，要他画出图来说明，可一直看不到他画出的具体图来。我估计他连他自已的想法是什么也不知道呢！鉴于这种情况，我想再谈一下构形和不可免构形还是必要的。
1、构形：
当我们对任何一个平面图，特别是对极大平面图着色时，总是在最后要遇到一个要着色的顶点，其所相邻的顶点都已着色，把这样的只有一个顶点还未着色的图就叫做“构形”。未着色的顶点叫待着色顶点，与待着色顶点直接相邻的叫围栏顶点。围栏顶点与待着色顶点共同构成了一个轮，所以平面图的构形也叫轮构形。要注意的是，在整个图中，除了待着色顶点以外的所有顶点都已进行了着色，且是符合着色要求的，两个相邻顶点是不用同一颜色的。
2、平面图的度定理：
在图论中，可以证明任何平面图中至少存在着一个顶点的度是小于等于5的。这也就是说，度全是大于等于6的平面图是不存在的。也就是说，度小于等于5的顶点在平面图中是不可避免的。“度”就是各顶点所连的边的条数。这样，我们在着色时，就可以把最后着色的待着色顶点放在度是小于等于5的顶点上，这就为把一个顶点数是无穷的、每个顶点的度也可以是任意的无穷问题转化成有穷的问题创造了条件。只研究待着色顶点的度是小于等于5的几种构形的可4—着色就可以了。
3、不可免构形和不可免构形集：
既然度小于等于5的顶点在平面图中是不可避免的，那么构形中待着色顶点的度是小于等于5的构形在平面图中也就是不可避免的了。这样的构形就叫平面图的不可避免构形，简称不可免构形。由各种不可免构形构成的集合就是不可免构形集。
4、围栏顶点数小于等于3的构形和围栏顶点占用的颜色数小于等于3的构形，可直接给待着色顶点着色：
围栏顶点数小于等于3时，围栏顶点最大只能占用3种颜色，至少还有一种颜色可以给待着色顶点着上；围栏顶点占用的颜色数小于等于3时，也至少还有一种颜色可以给待着色顶点着上。
5、4—轮构形一定是可约的：
“可约”就是可4—着色。围栏顶点数等于4且占用完了4种颜色时，一定是可以给待着色顶点着上图中已用过的4种颜色之一的。这是坎泊早在1879年就证明过了的，这里不再说明了。
6、坎泊对5轮构形的研究有“漏洞”：
围栏顶点数等于5且围栏顶点占用完了4种颜色的构形，坎泊只证明了无“双环交叉链”的情况下的构形是可约的，但却遗漏了有“双环交叉链”的情况下的构形是否可约。这种具有双环交叉链的构形是赫渥特在1890年发现的，所以也叫赫渥特构形，简称H—构形。现在研究四色问题主要就是研究这种具有双环交叉链的构形的可约性的问题了。
7、对具有双环交叉链的H—构形的分析：
在5—轮构形的围栏顶点占用完了A、B、C、D 4种颜色的情况下，一定是有一种颜色是用了两次的，如B，其他三种颜色只各用了一次。若把用两种颜色交替着色的序列叫做色链（简称链），则双环交叉链就是指A—C链和A—D链不但都是连通的，且有共同的起始顶点A，在中途还有相互交叉的顶点A。这两条链各因其在两个对角顶点间是连通的，是不可能通过交换链中各顶点的颜色而空出A、C、D三色之一来的。另外，这种构形无论是从那一个B色顶点开始，交换与其对角的顶点的颜色构成的色链后，都会新生成从另一个B色顶点到其对角的顶点的连通链。也不可能空出颜色B来给待着色顶点。
8、H—构形的不可免集：
由4种颜色可能构成的色链一共有六种，现在已有A—C、A—D、B—C、B—D四种不能交换和空出颜色，那么还有A—B链和C—D链是否可以交换和空出颜色，或交换后变成坎泊已证明过是可约的K—构形呢？这就是要认真研究的问题了。A—B链和C—D链是一对相反链，是不能相到穿过的，即是不能相交叉的。根据A—B链和C—D链可能的存在形式，只可能有：通过围栏顶点的A—B链是环形的，而C—D链是非环形的；通过围栏顶点的C—D链是环形的，而A—B链是非环形的；通过围栏顶点的A—B链和C—D链都是环形的但不相交；通过围栏顶点的A—B链和C—D链都是非环形的四种。这四种形式其实按有无经过围栏顶点的环形链，可只把H—构形分为有环形链的构形和无环形链的构形两大类。除此，再无别的存在形式了。这就是H—构形的不可免集。不知有些人怎么还能提出前面所说的问题呢？
9、不可免H—构形的解决办法：
双环交叉链A—C和A—D的起始顶点A、交叉顶点A和终了顶点C或D，都是关键顶点，这些顶点只要有一个的颜色改变了，就不存在双环交叉链了，构成H—构形的必要条件就不存在了，构形也就变成了可约的K—构形了。
有环形链的构形可以用断链交换法解决：有A—B环形链时，交换经过围栏顶点的C—D链，双环交叉链就断开了；有C—D环形链时，交换经过围栏顶点A或A—C链和A—D链的交叉顶A的A—B链，双环交叉链也就断开了；既有A—B环形链又有C—D环形链时，任意交换经过围栏顶点的C—D链，或交换经过围栏顶点A或A—C链和A—D链的交叉顶A的A—B链，也都可以使双环交叉链断开；无任何环形链但两链各只有一条时的构形，可以通过改变一条链上某一顶点的颜色，让其转化成使另一相反链呈经过了围栏顶点的环形链的构形；若两条链有一条是两条以上时的构形，可以把任一条链当做是环形的，直接按解决有环形链构形的办法解决就可以了。
看来解决H—构形的可约性的问题主要就是解决有环形链的构形的可约性问题了。以上这些问题，已经都是经过了证明的，这里也就不再画图进行一一具体的证明了。
10、四色猜测是正确的：
H—构形的不可免构形一个个都是可约的了，加上坎泊已证明了是可约的不可免的K—构形，则平面图的不可免构形就都是可约的了，那么四色猜测也就证明是正确的了。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，