四色猜测再证明

雷明85639720

四色猜测再证明
雷  明
（二○一八年八月八日）

1、链和交换
图的顶点着色中，把用两种颜色交替着色的道路，树或圈，就叫做由某两种颜色构成的色链，简称链。如果要改变链中某一顶点的颜色时，可以把该链中所有的颜色相互交换一下，即可达到目的，这一过程就叫做颜色交换，简称交换。
在平面图的轮构形中，由轮沿的对角顶点的颜色所构成的链叫对角链；由轮沿的邻角顶点的颜色所构成的链叫邻角链。如果两条链中的颜色全不相同（如A—B链和C—D链），则把这样的两条链叫做相反链；当然两链中有一种颜色相同时（如A—C链和A—D链），就叫相邻链。
如果轮构形的某一条对角链（如A—B链）对于两个对角顶点是连通的，则它一定与待着色顶点V构成了一个环，其相反链（C—D链）就一定是不连通的。如果轮构形的某对对角顶点构成的链是不连通的，则不管其相反链是否连通，都可以从轮沿顶点中着有该链的任一种颜色的顶点起，对该链进行交换，以达到改变交换的起始顶点的颜色的目的，可以使轮沿顶点中减少一种颜色或减少着某种颜色的顶点个数。比如5—轮构形中至少应有某一种颜色是用了两次的，这样的交换就可以使着这种颜色的顶点由两个减少到一个。

2、坎泊链、坎泊构形和坎泊链法
坎泊在1879年已经用这种交换（对角链的交换，也即坎泊链的交换）证明了4—轮构形，以及除了含有连通且相交叉的A—C对角链和A—D对角链外的其他5—轮构形都是可约的，即是可4—着色的。坎泊所遗漏的一种情况在11年后的1890年由赫渥特构造的赫渥特图给指了出来。但当时，赫渥特和坎泊谁也都不能对赫渥特图进行4—着色，所以才有了坎泊承论自已“弄错了”的事情发生和赫渥特所谓的“五色定理”的出现。但从现在来看，赫渥特图并不是不可4—着色的，所以可以理直气壮的说，赫渥特图不是四色猜测的“反例”，而只是坎泊着色方法或证明方法（坎泊链法）的反例。
现在我们可以说，能通过一次交换或最多两次交换就可以空出颜色给待着色顶点的构形就是坎泊构形，简写成K—构形。而坎泊链法就是只交换轮构形中的对角链，而空出颜色给待着色顶点的方法。相应的把轮构形的中的对角链也就可以叫做坎泊链。赫渥特图不能用坎泊的交换方法进行解决，所以我们就把这类构形叫做赫渥特构形，简写成H—构形，以与K—构形相区别。
3、H—构形的特点
赫渥特所构造的图的特点是什么呢，其中与坎泊构形不同的地方就是含有两条连通且交叉的A—C链和A—D链。赫渥特图从一个B色顶点交换B—D链或B—C链时，就新生成了从另一个B色顶点到其对角顶点的B—C链或B—D链，而不可能连续的移去两个同色B，其待着色顶点仍没有颜色可着。由此看来，含有两条连通且交叉的A—C链和A—D链，只能是构成H—构形的必要条件，而不是充分条件。因为有些图中虽含有这两条链，但却是可以连续移去两个同色B的。如九点形中除了含有环形的邻角链C—D的那一种是H—构形外，其他的三种都不是H—构形，他们都是可以连续移去两个同色B的构形，都应该归入K—构形之列。
但不能连续移去两个同色B的构形，也不是构成Ｈ—构形的充分条件。比如５—轮构形中，1B和4D间有连通的B—D链，3B和5C间有连通的B—C链，不能连续移去两个同色B，但却是一个K—构形，通过一次别的对角链的交换，就可以空出A、C、D三色之一给待着色顶点V着上。所以说，构成H—构形的充分必要条件是：图中既含有两条连通且交叉的A—C链和A—D链，又必须是不能连续移去两个同色B的构形，才是H—构形。或者说空不出任何颜色给待着色顶点V着上的图就是H—构形。
这样我们在今后的着色或证明中，只要是可以连续移去两个同色B的构形，就都可认为是K—构形，而不当成H—构形看待。K—构形的证明与着色，坎泊已经解决了，现在我们主要的就是解决H—构形的问题了。只要H—构形的问题解决了，四色猜测的问题也就得到了解决。
4、H—构形的不可免集
按5—轮的顶点顺序1、2、3、4、5，依此着色分别是B、A、B、D、C，A—C链和A—D链不但连通而且还相交叉。四种颜色可能构成的六种链中，A—C链和A—D链，已不能交换了，也不能空出A、C、D中的任何一种颜色给待着色顶点V，因为他们都是连通链的对角链；B—C链和B—D链又不能连续交换，也不能连续移去两个同色B；那么剩下来的就只有A—B和C—D两条邻角链可以交换了。
5—轮的邻角链A—B和C—D是一对相反链，两链是不可相互穿过的，所以这两条链在图中是不可能交叉的。对于每一条链来说，要么是道路或树，要么是圈。这样A—B链和C—D链在图中可能就存在以下的几种分布情况：①只有一条经过5—轮的1B、2A、3B三个轮沿顶点的A—B环形链的A类构形；②只有一条经过5—轮的4D和5C两个轮沿顶点的C—D环形链的B类构形；③以上任何环形链都没有的C类构形；和④以上两种环形链都有，但都不互相穿过的构形。但第④种情况的构形，又分别含有第①种和第②种情况的构形的特点，分别可当入A类构形和B类构形中，可不必单独作为一类构形列出。除这三种类型的构形外，再无别的类型了。这就是我构造的H—构形的不可免集。只要这三类不可免的H—构形都是可约的，那么四色猜测也就是正确的。
5、H—构形不可免集可约性的证明
5、1  A类构形中有环形的A—B邻角链，把邻角链C—D分隔成了环内、环外互不连通的两部分。因为4D和5C分别正好是A—D链和A—C链的终点顶点，所以交换了4D和5C的邻角链C—D后，就可以使A—D链和A—C链断开，图成为K—构形而可约。
5、2  B类构形中有环形的C—D邻角链，把邻角链A—B分隔成了环内、环外互不连通的两部分。因为2A也正好A—D链和A—C链的共同起始顶点，所以交换了1B、2A和3B的邻角链A—B后，也可以使A—D链和A—C链断开，图成为K—构形而可约。
以上解决A类和B类H—构形的方法中，交换的都是邻角链，且都能使得A—C链和A—D链断开，所以这种方法我们就叫做“断链”法，相应的，也可以把坎泊的方法也可以叫做“空出颜色”法。
5、3  C类构形中没有环形链，A—B链和C—D链都是直链，即就是交换了，也不起任何作用，所以也就没有再可以交换的A—B链或C—D链了。但B—C链和B—D链虽不能连续交换，但总可以只先交换一个，先移去一个同色B，使构形转型，再根据转型后的构形再进行研究。这就是“转型”法。转型有两种转法,一种是逆时针转型，即从顶点1B开始交换B—D链；一种是顺时针转型，即从顶点3B开始交换B—C链；只要转型交换一次，就可使构形转化成DCD型或CDC型。但无论是那种转型交换，都可能得到以下的两种结果：
一种结果是成为一个DCD型或CDC型的可以连续移去两个同色D或C的K—构形，然后再进行两次空出颜色的对角链的交换，一次移去一个同色，把空出来的同色给待着色顶点V着上即可解决问题。总共进行了三次交换；转型交换后的另一种结果是成为一个DCD型或CDC型的含有经过5—轮两个轮沿顶点的A—B环形链的B类H—构形。再按解决B类构形的办法去解决就行了。解决B类构形需要进行两次交换（一次是邻角链C—D链的断链交换，一次是对角链的空出颜色的坎泊交换），总共还只是进行了三次交换也就解决了问题。
以上我们研究的C类H—构形，只是不对称的构形。如果构形是有一条以A—B链为对称轴的对称构形，那么就必须多进行两次同方向的连续的转型交换（也就是张彧典先生所说的连续颠倒），使构形先转化成不对称的C类构形,再按不对称的C类构形去解决。总共需要五次交换。所以把这一种不对称的C类构形单独列为一类，也是可以的；直接归入C类构形也是可以的。这种构形的代表就是1935年美国人Irving Kittell构造的对称地图的对偶图。这个图也与赫渥特图一样，待着色顶点并没有着上颜色，构造者Irving Kittell而是把该图作为一个“染色困局”图而出现的。现在我们已对该项图进行了4—着色，所以它也是可约的。
6、四色猜测是正确的
至此，我的H—构形的不可免集中的三种不可免构形，已经都是可约的了，所以也就证明了四色猜测是正确的。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

wangyangke

雷明85639720说得对：wangyangke ，你真无耻！