着色法证明四色猜测是正确的（修改稿）

雷明85639720

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

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

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

5—轮构形中围栏顶点占用完了四种颜色的着色模式只能是有一种颜色是用了两次的（如图1，a）。当构形中不存在任何连通链时，四种颜色均是可以空出来给待着色顶点V着上的；当构形中只有一条连通链时，V至少还有两种颜色可着；当1B—4D和3B—5C有一条或两条都是连通链时（两链都连通时一定交叉，但只可能有一个相交顶点），可以空出A、C、D三色之一给V；当2A—4D和2A—5C有一条是连通链时，可空出C或D给V；当2A—4D和2A—5C两条都是连通链且两链只有一个共同顶点2A时，可空出B给V。以上是坎泊已经证明过了的构形，都是可约的。我们叫做K—构形。
2、有两条连通链且有两个相交顶点的5—轮基本模型
如果2A—4D和2A—5C两条都是连通链且两链有两个共同顶点2A和8A时（如图1，b），这就是5—轮构形中有两条相交叉链的基本模型。
在如图1，b中，由于2A—5C和2A—4D两链分别是连通的，所以两链都不能进行交换，也不能空出A、C、D三种颜色之一给待着色顶点V。也还是因为A—C和A—D链分别是连通的，所以B—D链和B—C链则一定不连通。不连通就有可能空出颜色B来。以下就分析看看颜色B道底能不能空出来给V。
3、可以同时移去两个同色B的非H—构形

图1，b若是三角剖分（极大图）时，可能有以下几种情况：如图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，都是属于可约的构形。交换的方法分别是：图2中1B—7D和3B—6C的交换是没有先后次序的；图3则必须先交换1B—7D，后交换3B—6C；图4与图3交换的顺序正好相反，则必须先交换3B—6C，后交换1B—7D。
以上的图2、图3和图4三构形，是在有两条连通链且有两个相交顶点的构形中，可以同时移去两个同色B的构形，是可以直接通过交换空出颜色给V的。但坎泊在证明时却没有遇到这种情况，所以仅管该三构形能同时移去两个同色B，也不属于坎泊的K—构形；这三个图都有两条连通的、且有两个相交顶点的链，与赫渥特图有相似的特点，所以我们叫它非H—构形。其中图2是彻底的非H—构形，而图3和图4我们则叫它半H—构形。
4、H—构形的着色方法
除了图2、图3和图4，只有图5无论怎样交换，都只能移去一个同色B，而不能同时移去两个B，该构形与赫渥特图有相同的特点，所以我们把它叫做H—构形。这种构形，不可以直接通过交换空出颜色，但可以转化构形的类型，为下一步交换空出颜色准备条件。
图5就是一个H—构形，是由赫渥特图简化而来的“九点形”。由于图中有环形链C—D，分A—B链为互不相通的两部分，交换其中任一部分A—B链，都可以使图变成一个K—构形，再通过一次交换后，可以给V着上A、C、D三种颜色之一。
5、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—构形，再通过交换后，则可以给V着上B。
6、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，使构形发生变化呢。当然可以。

的确，Z—构形无论交换那一条关于B的链，都可以使构形由Z—构形转化为可以同时移去两个同色的半H—构形或H—构形。上面已经说了，半H—构形和H—构形都是可以4—着色的，都是可约的，那么这个Z—构形也就是可以4—着色的，也是可约的。
7、四色猜测的证明
还有没有别的5—轮构形呢，没有了。上面我们不仅分析了5—轮构形中没有任何连通链（如图1，a）和只有一条连通链（如图8）的情况下，待着色顶点一定是可以着上四种颜色之一的；而且分析了1B—4D和3B—5C两链同时连通，且有交叉顶点（如图9）的情况，是可以通过交换直接空出A、C、D三色之一给V的；又分析了2A—5C和2A—4D两链同时连通，且只有链的起始顶点是同一个顶点（如图10）的情况，也是可以通过交换直接空出两个同色B给V的；还分析了2A—5C和2A—4D两链同时连通，且不但有同一个起始顶点，且链中还有另外的交叉顶点（如图1，b）的最复杂情况。


在最复杂的图1，b的情况下，又分析了A—B链和C—D链是不是环形链的四种情况，分别是：① A—B是环形链，C—D不是环形链（如图2的非H—构形）；② C—D是环形链，A—B不是环形链（如图5的H—构形）；③ A—B和C—D两条链都是环形链（如图6的M—构形）；和④ A—B和C—D两条链都不是环形链（如图3和图4的K—构形以及图7的Z—构形）的四种情况。在这四种情况下的构形都是可以通过交换使构形先转型后，再进一步通过交换进行4—着色，也都是可约的。
图3和图4表面上看，好象是通过交换直接空出了B给V的，实际上它他们也都是在交换了一个关于B的链后，使构形进行了转型，变成了只有一条连通链的K—构形。第二次交换关于另一个B的链实际上是在K—构形下进行的交换。当然图2所谓同时移去两个同色的实质也是如此。图2和图3交换了一个关于B的链后，构形都转变成只有一条连通链A—C的K—构形，当然是可以空出另一个B了，如图11和图12。由于图2的非H—构形是左右对称的，所以从另一个B交换的结果也只是与图11的左右不同而已；另一个半H—构形也一样，交换的结果只是与图12 左右不同而已。


还有没有别的构形呢，没有了。因为上面我们已经把各种情况都分析到了，不可能再有别的情况的构形出现了。因此，也就证明了5—轮构形都是可约的。再加上一百多年以前坎泊已证明的可约构形，就可以说平面图所有的不可免构形都是可约的，当然也就证明了四色猜测是正确的。

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

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

修改后的论文于二○一六年二月十日发表在《中国博士网》上，网址是：

雷明85639720

,,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，