四色猜测的最终证明

英文标题：Final Proof of Four Colour Conjecture

雷  明

（二一九年八月十一日） 

【摘  要】本文把坎泊未能解决是否可4—着色的赫渥特构形，按其中是否含有经过围栏顶点的环形链，分为不可避免的三种类型，并且一一证明了这三种类型的构形都是可4—着色的，从而证明了赫渥特构形都是可4—着色的。加上坎泊在1879年早已证明了是可4—着色的构形，平面图的所有不可避免构形就都是可4—着色的了。这就证明了四色猜测是正确的。四色猜测可以上升为四色定理了。

英文摘要：[Abstract] As for Whether the Heawood^,s Configuration can be 4-Coloured,which Kemble didn^,t give the answer,this essay based on whether it contains ring chain passing the top of rail,shows 3 inevitable types,and proved all 3 types of configuration can be 4-coloured.Thus it proved that Heawood^,s Configuraion can be 4-coloured.Plus Kemple^,s proof of Configuration of 4-colour in 1879,all inevitable configurations of planar graph can be 4-coloured.Thus it proved that 4CC is correct,and the 4CC can be upgraded to Four Colour Theorem.

【关键词】四色猜测  图  平面图  构形  不可避免构形  着色  色链  可约

英文关键词：[Key words] four colour Conjecture, graph, planar graph, configuration, unavoidable configuration, colour, colour, co;our chain, reducible

 

四色猜测也叫四色问题。是由英图的绘图员法朗西斯（Francis Guthrie）在绘制英国地图的实践中于1852年提出的。即对任何行政区划地图（或者说把一个平面分成若干个部分的图）中的区域染色，在相邻区域不用相同颜色的情况下，最多四种颜色就够用了的地图四色猜测。这个猜测是否正确，还得要经过证明才能得出结论。虽然法朗西斯是提出猜测的第一人，后来也成为一名数学教授，任教于开普敦的南非大学，一直到1899年去世，但他对他所提出的问题却无任何建树。

一、证明前的理论准备：

1、地理问题转化成了数学问题：

从图论上看，行政区划地图就是一个连通且无割边的3—正则平面图,即是每个顶点都连有3条边的平面图。给地图中区域的染色就相当于给地图的对偶图——极大平面图（每个面都是三边形面的平面图）的顶点着色。这就把一个地理学中的问题转化成了数学中的问题了。地图四色猜测也就变成了平面图的四色猜测。

2、极大平面图的四色问题解决了，也就解决了任意平面图的四色问题：

在顶点数相同的平面图中，以极大平面图的边数为最多，如果任意的极大平面图的四色猜测是正确的，则极大图经减边或去顶后所得到的任意平面图的色数就只会是减少，而决不会再增加。所以说证明了极大平面图的四色猜测，也就证明了任意平面图的四色猜测。

3、四色问题研究的对象是无穷多的：

平面图有无穷多个，且每一个平面图中的顶点数也可以是任意多的，每一个平面图中的每一个顶点所连的边数（即度）也可以是任意多的，所以说四色问题所研究的对象是无穷多的。四色猜测也是不可能用对一个个的图去着色进行证明的，而必须把研究对象的无穷性变成有穷的。把一个无穷的问题转化成一个有穷的问题去解决。

4、坎泊提出的“构形”概念：

为了证明四色猜测，律师出身的坎泊在1879年提出了“构形”的概念。对任何极大平面图着色时，已着过色的顶点一定是符合着色要求的（相邻顶点不用同一颜色），也总能遇到待着色顶点是处在一个已着色的轮形图的中心位置的情况。把待着色顶点与已着过色的顶点共同构成的图叫做构形，并把与待着色顶点相邻的顶点叫做围栏顶点。由于待着色顶点也可以与任意多的围栏顶点相邻，所以构形的种类也是无穷多的。

5、平面图的不可避免构形——轮构形：

图论中可以证明，任何平面图中一定存在着至少一个顶点的度是小于等于5的。也就是说，在任何平面图中，度小于等于5的顶点是不可避免的存在的。用坎泊的地图术语来说，就是在任何地图中，都至少存在着一个国家与两个国家、三个国家、四个国家、五个国家相邻这四种情况中的一种。因此，所有顶点的度都是大于等于6的平面图和所有国家的邻国数都是大于等于6的地图，都是不存在的。这就为把无穷多的构形转化成有限多的5种不可避免的构形创造了条件。在着色过程中，我们总可以把待着色的顶点放在度是小于等于5的顶点上。只要证明了这五种不可避免的构形（简称不可免构形）是可4—着色的，也就证明了四色猜测是正确的。由于不可免构形的待着色顶点都是位于一个轮的中心顶点之上，所以也叫做轮构形。这就把一个研究对象是无穷的问题转化成了一个研究对象是有限的问题了。

6、3—轮以下的不可免构形都是可约的：

不可免构形的围栏顶点所占用的颜色数不大于３时，就至少还有一种颜色可以给待着色顶点着上。很自然的，不言而喻，3—轮以下的不可免构形和围栏顶点所占用的颜色数不大于3的所有构形，包括4—轮和5—轮两个不可免构形，就都一定是可约的了，即是可4—着色的。坎泊早在1879年就证明了这一点。“可约”一词也是坎泊早期提出的一个概念。

7、坎泊创造的颜色交换技术：

把用两种颜色交替着色的、由“顶点—边—顶点”构成的序列叫做色链，简称“链”。交换链中各顶点的颜色，可以达到改变链中任何一个顶点颜色的目的。这就是坎泊在1879年为证明四色猜测所创造的颜色交换技术。

8、4—轮构形的可约性：

若4—轮构形的围栏顶点已占用完了4种颜色（一个顶点占用一种颜色）时，就得使用坎泊所创造的颜色交换技术了。由4—轮的两组对角顶点的颜色分别构成的色链，对于两组对角顶点来说均不连通时（如图1，a），则可以从任何一个围栏顶点开始，交换该顶点与其对角顶点的颜色所构成的对角链，就可以空出该围栏顶点的一种颜色来给待着色顶点着上；若有一组对角链是连通的（如图1，b），该组对角链与待着色顶点就构成了一个“环”，则另一组对角链一定就不连通，并且分布在环的内、外两侧。这是因为两条互为相反链（相反链是指两条链中两种颜色完全不同的两条色链）的两条对角链中没有相同的颜色，是不能相互穿过的。这时，就可以从另一组对角的任何一个顶点开始，交换该组对角链的两种颜色，也可以空出该围栏顶点的颜色给待着色顶点着上。可见任何4—轮构形都一定是可约的。这就是坎泊对４—轮构形可约性的证明。

 

9、坎泊早已证明了无交叉链的5—轮构形都是可约的：

当5—轮构形的围栏顶点已占用完了4种颜色的情况下，至少有一种颜色在围栏顶点中是用了两次的。把由两个相同颜色的顶点所夹的顶点叫做构形的峰点，则双B夹A型的构形就用BAB表示，峰点着A色。坎泊在1879年早就用他所创造的颜色交换技术，证明了除图2,b的一种含有相交叉的A—C链和A—D链的5—轮构形外，其他不含相交叉链的5—轮构形都是可约的（以后人们就把坎泊已证明了是可约的构形叫做K—构形），就宣布他证明了四色猜测是正确的。但他却遗漏掉了含有相交叉链的这一种情况。

 

10、赫渥特构造了含有A—C链和A—D链相交叉的构形：

 

1890年，即在坎泊宣布他证明了四色猜测的11年之后，英图的赫渥特（Percy John Heawood）构造了一个其中含有A—C链和A—D链相交叉的图——赫渥特图（如图3，图中的b，r，y，g分别相当于这里所说的A，B，C，D四种颜色），指出了坎泊的证明有漏洞。但当时赫渥特和坎泊却都不能对他的图进行4—着色。后来在长达整整一个世纪的时间里，也一直没有人能对赫渥特图进行4—着色。四色猜测的证明一直处在停滞不前的状态。

11、赫渥特图是可以4—着色的：

赫渥特的图真是不可以4—着色吗，不是的。一个世纪后的1990年前后，就有我国的雷明，懂德周，英国的米勒等人仍然都还是用了坎泊的颜色交换技术，对该图在赫渥特原着色的基础上进行了4—着色，对坎泊证明中的漏洞进行了弥补。

12、对赫渥特图的分析：

赫渥特图中连通的A—C链和A—D链都是不能交换的，即就是交换了，也是空不出A，C，D三种颜色之一的。而B—C链和B—D链虽然不连通，但交换了其一B—C（或B—D）链，移去一个同色B后，又会生成连通的另一条B—D（或B—C）链，而不可能连续的移去两个同色B。既然是连通链，就不能进行交换，交换了也是空不出第二个同色B的。赫渥特图不能直接空出任何一种颜色这种情况的产生，则完全是由于A—C链和A—D链的相交叉所引起，所以该两链的相交叉就至少是构成H—构形的必要条件。把具有与赫渥特图这种相同结构和性质的构形，人们就叫做H—构形。又由于H—构形不能直接使用坎泊已用过的交换方法空出任何一种颜色给待着色顶点，所以人们也把这种构形也叫做“染色困局”。在H—构形中，以上的A—C，A—D，B—C和B—D四种链均不能交换，也空不出任何一种颜色来。那么，现在就只能再看一看A—B链和C—D链是否可以交换了。

二、H—构形可约性的证明：

1、H—构形的不可免集：

A—B和C—D两种链在图中的存在形式，只能有以下三种不可避免的形式：即A—B链是环形的且经过了B，A，B三个围栏顶点（如图4，a，图中加粗的线为环形链，其中的曲线是链而非单边，而直线是单边而非链。如果非围栏顶点的两顶点C、D间还有别的顶点时，图就成了可以连续的移去两个同色B的K—构形而非H—构形了。），或C—D链是环形的且经过了C，D两个围栏顶点（如图4，b，加粗线同上），或者经过围栏顶点的A—B链和C—D链都不是环形的，各是一棵树或一条直链（如图4，c，加粗线也同上）。虽然两种链都是环形链的构形也是存在的（如图5，加粗线也是环形链），但却分别属于含有A—B环形链一类或含有C—D环形链一类的构形，可以不再作为单独的一类处理。

 

 

除此三种情况外，再就没有别的类型了。这三类不可免的构形就构成了H—构形的不可免集，并且是非常完备的。这里请注意，以上所说的链都是指经过了围栏顶点的邻角链，以后再提到链时，也都是指这样的链。

2、不可免的H—构形的解法：

　含有经过B，A，B三个围栏顶点的A—B环形链的构形（如图6，a）：构形中A—C链和A—D链两链的末端顶点C和D一定同是分布在A—B环形链的同一侧，交换经过这两个顶点的C—D链，就一定可以使A—C链和A—D链断链，图成为K—构形而可约。

 

 

　含有经过了C，D两个围栏顶点的C—D环形链的构形（如图6，b）：构形中A—C链和A—D链的共同起始顶点A也一定是分布在C—D环形链的一侧，交换经过这个顶点的A—B链，也一定可以使A—C链和A—D链断链，图成为K—构形而可约。

以上两种有环形链的构形的解决办法，不仅适用于H—构形，而且也适用于K—构形。只要是含有环形链的构形，可以不去管它是否是H—构形，都可以用同样的方法进行解决。

　无任何环形链的构形（如图6，c）：构形中A—B链和C—D链均不能交换，现在也就只能先交换一条关于B的链，先移去一个B，使构形转型了。对于BAB型的构形，从左B交换了B—D链后，成为DCD型；从右B交换了B—C链后，成为CDC型。然后再看转型后的构形，是否已成为可以连续的移去两个同色D（或C）的K—构形，或者成为以上两种有环形链的可约的H—构形。若仍不可约时，就继续进行同方向的转型，一定是可以在有限次的交换内，空出颜色给待着色顶点的。这种“转型交换”的交换次数为什么是“有限的”，我们将在后面给以证明。

3、5—轮构形转型交换的周期是20：

5—轮构形有5个围栏顶点，围栏顶点共占用了4种颜色。进行连续的转型交换，使得构形又转型成为BAB型，峰点A又回到原来的5—轮最上方一个顶点时，需要的交换次数是4和5的最小公倍数20次。这时，围栏各顶点的颜色均与最初转型前的颜色完全相同。再继续进行转型交换时，构形将以每20次交换为一个周期，无穷的转型下去，永远也不能空出颜色来。无论是进行逆时针方向转型，还是进行顺时针方向转型，都有同样的特点。

4、敢峰—米勒图类构形虽是无穷转型也空不出颜色的图，但却是可4—着色的：

 

有没有无穷次转型交换也空不出颜色来的构形呢？有。这就是敢峰—米勒图类的构形（如图7和图8。两图是同一个图，只是两种不同的画法。）。该类构形的确是无穷次的转型交换也空不出颜色的，两个方向的转型均是如此。许多学者的研究都说明了该图的转型过程的确是无穷循环的，循环的周期是20。但由于该类构形中有一条经过了围栏顶点的环形的A—B链（见图8中的外圈加粗边），可以交换A—B环形链内、外的任一条C—D链，使图变成K—构形而可约。该构形虽是无穷转型的，但却是可以4—着色的。

5、无任何环形链的H—构形转型交换次数一定有限的理论证明：

无任何环形链的构形，在连续转型交换时，一定会分别在两个方向转型的第20次转型之前（包括第20次），图就一定会转化成为一个可以连续的移去两个同色的K—构形而可约。否则，图将是一个无穷转型交换也空不出颜色的图。但这却十在是不可能的事，因为无穷转型交换也空不出颜色的敢峰—米勒图类的构形，其中不但含有经过围栏顶点的A—B环形链，而且还含有不经过围栏顶点的C—D环形链，且A—B链和C—D链都是轴对称分布的，而现在这里所研究的对象（无任何环形链的H—构形）中，却是任何环形链也没有的构形，且A—B链和C—D链也不是轴对称分布的。

虽然1935年由Kittell给出了一个无任何环形链的轴对称的H—构形（如图9，其中a图是地图形式，b、c两图是两种不图画法的原图a的对偶图），但其“裸图”（即未着色时的图）也只有一个对称轴，且不是中心对称的；而敢峰—米勒图“裸图”却是有五个对称轴（即张彧典先生所谓的“十折对称”）的图，且是中心对称的。所以无任何环形链的H—构形，决不可能是可以无穷的转型交换下去而空不出颜色的构形。两个方向的转型交换，一定都是可以在20次转形交换之前，变成一个可以连续的移去两个同色的K—构形的。再进行两次空出颜色的交换，可以连续的移去两个同色，即可解决问题（见后面的图27和图28）。

 

 

由于转型是可以向不同的两个方向进行的，假设一个构形向两个方向转型时，都是在第20次转化成了可以连续的移去两个同色的K—构形，那么，两个第19次之内（包括两个第19次）就有39个H—构形。把顺时针转型第19次后所得到的构形（因为第19次所得的图仍是H—构形，而第20次后的图就成了K—构形了（如图10）），再进行逆时针转型时，一定是在第40次转型后，图就会转化成一个可以连续的移去两个同色的K—构形（同样的，把逆时针转型第19次后所得到的构形再进行顺时针转型时，也会得到同样的结果），再进行两次空出颜色的交换，就可以给待着色顶点着上图中已用过的四种颜色之一，共计42次交换。

设构形逆时针转型的次数是X，顺时针转型的次数是Y，从上面的结果可以看出，对于任何无环形链的H—构形，都有X≤40，Y≤40和X＋Y≤40的关系。再进行两次空出颜色的交换，共计交换总次数则是：X＋2≤42，Y＋2≤42和X＋Y＋2≤42。这就是由一个已知的构形构造转型交换次数不超过42次的不同构形的原理。

当然在转型过程中，若所得到的图中含有经过围栏顶点的环形链时，也可以交换环形链内、外的任一条相反链，使图变成K—构形，提前结束转型。

6、几个需要交换20次以上才能空出颜色的构形：

 

我们先给出一个逆时针转型时总交换次数是21次的构形（如图11，a），读者可以验证一下，是不是需要21次交换。再把这个构形进行顺时针转型，在第7次交换时就空出了颜色，那么第5次交换就是一个可以连续的移去两个同色的K—构形，则前4次交换所得的图分别是CDC型、ABA型、DCD型和BAB型的H—构形。对这些图再进行逆时针转型时，就是分别需要总交换次数是22次、23次、24次和25次的构形。图11，b就是逆时针转型时，需要25次交换才能空出颜色给待着色顶点的构形。

请注意，图11的这两个构形中都含有环形的C—D链，是可以用断链法很快解决问题的。为什么我们不这样去作，而要进行多达20次以上的连续转型交换呢？是因为有些人不但把所含有A—C和A—D两条相交叉链的构形统统都定义为H—构形，而且又把除了敢峰—米勒图类构形以外的其他H—构形也都统统叫做Z—构形的，并且认为统统都得用转型交换的方法来解决。所以我们所构造出来的图中虽然也含有环形链，也不去用断链交换法去解决，仍把它看成是Z—构形，而用连续的转型交换法进行解决的。这几个图连续转型交换的总交换次数都大于20，这就说明了有些人所说的Z—构形只有15类和最大的总交换次数不大于16的结论是错误的。

7、无任何环形链的H—构形转型交换次数一定有限的实践验证：

我们可以仿照敢峰先生构造终极图（即埃雷拉图）的办法，先画一个非常一般的不含连通链的H—构形，然后进行转型交换，每交换一次，都要人为的在平面图范围内再构造成H—构形。直到在平面图范围内不可能再构造成H—构形，图成为可约的可以连续的移去两个同色的K—构形为止。

图12是两个一般的无环形链的H—构形，左右结构正好是相反的,实际上同一个构形，所以我们只要研究图12，a就可以了。

现在我们对图12，a进行逆时针转型交换如下：

 

 

第一步，对图12，a从顶点1开始交换B—D链，得到的图13中虽然已生成了从顶点3到顶点5的连通的B—C链，但图却转化成了一个DCD型的H—构形，并且已经是一个可以连续的移去两个同色D的K—构形了。这一点可以从第二步转形交换得到的图14中没有形成从顶点1到顶点3的连通链可以看出。

第二步，对图13从顶点5开始交换D—A链，得到的图14中没有生成从顶点1到顶点3的连通链D—B，应该说问题已经可以解决。但在平面图范围内还可以构造出从顶点1到顶点3的D—B连通链（如图15），这是一个ABA型的H—构形。

第三步，对图15从顶点2开始交换A—C链，得到的图16中也没有生成从顶点4到顶点1的连通链A—D，问题也应得到解决。同样的，在平面图范围内也还是可以构造出从顶4到顶点1的连通的A—D链的（如图17），这是一个CDC型的可以连续的移去两个同色C的K—构形，而不再是H—构形了。

 

 

第四步，对图17从顶点5交换C—B链，得到的图18中虽没有生成从顶点2到顶点4的连通链C—A，但在平面图范围内再不可能构造从顶点2到顶点4的连通链C—A了，因为其前面有一条连通的相反色链B—D在阻隔着，C—A链是不可能通过的。很明显的是一个只有一条连通的B—D链的K—构形了。

第五步，对图18再从顶点2交换C—A链，就连续的移去了图16中的两个同色C，把C给待着色顶点V着上（如图19）。着色结速。

以上只进行了三次转型交换，加上最后的两次交换，共计是五次交换。这就是无环形链的H—构形的最大交换次数。以上是对图12按逆时针转型交换的，若按顺时针转型交换时，也会得出同样的结论（如图20到图26）。请读者自已也再试一试。

 

 

顺时针转型也只进行了三次转型交换，加上最后的两次交换，共计也是五次交换。两个方向的转型交换得出相同的结果，这就说明无环形链的H—构形的最大交换次数的确是不大于5的。如果把图12的任意图变成极大图时，则交换的次数将会更少。这就从对构形的着色实践上验证了无环形链的H—构形转型交换时的最大交换次数一定是“有限的”，这个“有限”的上界是5，最大也决不会超过42次。

 

对图9，c的轴对称的无环形链的H—构形，进行转型交换（如图27），第4次转型得到一个可以连续的移去两个同色B的构形（如图27，d），再交换两次，空出了B（如图7，f），共计6次交换，远小于42次。但该图却在第3次转型后，形成了具有环形链的构形（如图27，c和图28，a），然后按有环形链的构形去解决，5次交换就可解决问题。如果把该图某一个方向的第3次转型后的图（如图27，c）再进行相反方向的转型时，则总共只要9次交换就可以解决问题，距上界42次仍相差很远。

 

8、除了有环形C—D链的九点形构形仍是H—构形外，其他的九点形构形都是K—构形：

 

把图4中加粗的曲线链变成单边时，图就成了九点形构形（如图29），而图9，c的轴对称无环形链的构形变成九点形构形则是图28，b。可以看出，图29，a、图29，c和图28，b均变了可以连续的移去两个同色B的K—构形；而只有图29，b仍是H—构形（有环形C—D链的H—构形，赫渥特图就可以简化成图29，b），不可能连续的移去两个同色B，只能通过交换C—D环形链内、外的任一条A—B链后，图才能变成K—构形而可约。

然而这些九点形构形中却都含有连通且相交叉的A—C链和A—D链。这一现象再一次说明了连通且相交叉的A—C链和A—D链只是构成H—构形的必要条件，而并非是充分条件。没有它，不可能构成H—构形，但有了它的构形却不一定就都是H—构形。

三、平面图的着色流程：

图30就是平面图的4—着色流程图。

 

首先把着色时可能遇到的待着色顶点分为染色困局顶点和非染色困局顶点。非染色困局顶点用坎泊链法（即坎泊已用过的交换法或空出颜色的交换法），染色困局顶点用非坎泊链法（即坎泊没有使用过的颜色交换法）。非染色困局的顶点包括度是小于等于4的顶点和围栏顶点占用颜色数小于等于3的顶点。其他的围栏顶点占用了4种颜色的待着色顶点，不管其是不是H—构形，都按染色困局顶点对待。然后再按各种染色困局的解决办法分别解决。 

四、四色猜测是正确的：

现在各种情况下的不可免H—构形都是可约的了，加上坎泊早已证明了是可约的K—构形，平面图的任何不可免构形就都是可约的了，平面图的四色猜测也就得到了证明是正确的。当然地图的四色猜测也就是正确的了。从提出至今已有一百六十七年历史的地图四色猜测，就可以上升为地图四色定理了。结束这一个半世纪的证明历史了。

雷  明

二一九年八月十一日于长安

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

http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=3976