着色法证明四色猜测是正确的

雷明85639720

着色法证明四色猜测是正确的
雷  明
（二○一六年二月五日）

【摘  要】分析了5—轮构形的各种情况，证明了所有5—轮构形都是可约的，四色猜测得到证明是正确的。
【关键词】四色猜测  平面图  构形  色链  交换  着色

本文只研究坎泊没有证明的5—轮构形是否可约的问题。
1、有两条相交叉链的基本模型

两条链有两个共同顶点的基本模型如图1。图中两条相邻链A—C和A—D，既有同一起始顶点2A，又有交叉顶点8A。由于A—C和A—D链分别是连通的，所以不能进行交换，也不能空出A、C、D三种颜色之一给待着色顶点V。也还是因为A—C和A—D链分别是连通的，所以B—D链和B—C链则一定不连通。不连通就有可能空出颜色B来。以下就分析看颜色B道底能不能空出来。
2、可以同时移去两个同色B的K—构形
图1若是三角剖分（极大图）时，可能有以下几种情况：如图2、图3、图4和图5。图2中有一条环形链A—B，分C—D链为环内环外两部分；图5中有一条环形链C—D，也分A—B链为环内环外两部分；图3和图4则都没有环形链，A—B链和C—D链分别都是一条道路（直链）。但图2、图3和图4都可同时移去两个同色B给待着色顶点V，都是属于可约的K—构形。交换的方法是：图2，1B—7D和3B—6C的交换是没有先后次序的；图3则必须先交换1B—7D，后交换3B—6C；图4与图3交换的顺序正好相反，则必须先交换3B—6C，后交换1B—7D。而只有图5无论怎样交换，都是不能同时移去两个同色B的构形，它与赫渥特图有相同的特点，所以我们把它叫做H—构形。

3、H—构形的着色方法
图5就是一个H—构形，是由赫渥特图简化而来的“九点形”。由于图中有环形链C—D，分A—B链为互不相通的两部分，交换其中任一部分A—B链，都可以使图变成一个K—构形，再通过一次交换后，可以给V着上A、C、D三种颜色之一。
4、M—构形的着色方法
图2的A—B是环形链，C—D链是直链；图5的C—D是环形链，而A—B链是直链；现在要问，有没有A—B链和C—D链都是环形链的构形呢。回答是，有。这就是米勒构造的米勒图，也叫M—构形，如图6（这是米勒的画法，图中不显示待着色顶点V）。图中A—B链和C—D链都是两条，各有一条是环形的，另一条是直链。两条环形链A—B和C—D链是相互包含的，即相当于一个圈内还套着一个圈一样，且两个圈没有共同的顶点（即两圈不相切）。
在M—构形中交换任何一条A—B链都是无用的，图仍然是一个M—构形的图。但交换了任一条C—D链却可以使图变成一个K—构形，再通过交换后，则可以同时移去两个同色B给V着上。

5、Z—构形的着色方法

现在还要问，在不能同时移去两个同色B的情况下，还有没有A—B链和C—D链都不是环形链的情况呢，回答也是“有”。这就是张彧典先生构造的第八个构形一类的图，我把该构形的顶点数尽量减少，又把图变成左右对称的图，得到如图7（这是张彧典先生的画法，5—轮位于图的最下方）。由于是张先生构造的类型，所以我把它叫Z—构形。
    Z—构形中两条交叉链A—C和A—D均是连通的，不能交换；A—B链和C—D链又都是直链，且只有一条，谁也没有把谁分隔开来，交换后也不起任何作用；B—C链和B—D链虽都不连通，但却不管是交换一条，还是交换两条，都只能移去一个B，而不能同时移去两个B。怎么办，我们可以想：既然不能同时移去两个同色B，那么我们就只交换一条关于B的链，先移去一个B，使构形发生变化呢。当然可以。的确，无论交换那一条关于B的链，都可以使构形由Z—构形转化为可以同时移去两个同色的K—构形或H—构形。上面已经说了，K—构形和H—构形都是可以4—着色的，都是可约的，那么这个Z—构形也就是可以4—着色的，也是可约的。
3、四色猜测的证明
还有没有别的5—轮构形呢，没有了。上面我们分析的是有交叉链的最复杂的情况。在此情况下，又分析了A—B链和C—D链是不是环形链的四种情况，分别是：① A—B是环形链，C—D不是环形链；② C—D是环形链，A—B不是环形链；③ A—B和C—D两条链都是环形链；和④ A—B和C—D两条链都不是环形链的四种情况。在这四种情况下的构形都是可以4—着色的，都是可约的。且再也不可能有别的情况的构形出现了。因此，也就证明了所有含有交叉链的5—轮构形都是可约的。再加上一百多年以前坎泊已证明的可约构形，就可以说平面图所有的不可免构形都是可约的，当然也就证明了四色猜测是正确的。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，