四色猜测的历史评述和最终证明（第四稿）（一）

雷明85639720

四色猜测的历史评述和最终证明（第四稿）（一）
英文标题：Historic Review and Final Proof of Four Colour Conjecture(4CC)
雷  明
（陕西金堆城钼业公司退休高级工程师   邮编：710100
Email：lm85639720@163.com）
(二○一九年八月十日)

【摘  要】本文把坎泊未能解决是否可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

1、地图四色猜测：
四色猜测也叫四色问题。是由英图的绘图员法朗西斯（Francis Guthrie）在绘制英国地图的实践中于1852年提出的。即对任何行政区划地图（或者说把一个平面分成若干个部分的图）中的区域染色，在相邻区域不用相同颜色的情况下，最多四种颜色就够用了的地图四色猜测。这个猜测是否正确，还得要经过证明才能得出结论。虽然法朗西斯是提出猜测的第一人，后来也成为一名数学教授，任教于开普敦的南非大学，一直到1899年去世，但他对他所提出的问题却无任何建树。
2、萌芽状态的四色猜测被打压：
四色问题提出来后，法朗西斯无法证明是否正确，就向他的弟弟弗内德里（Frederick Guthrie）求救，弗内德里也无法证明，于是在1852年10月23日，就又请教他正在就读的伦敦大学的老师——著名的数学家莫根（Augustus De Morgan）。莫根认为这是一个崭新的问题，但他也无法解决，于是就立即在当天写信把这一问题告诉了他在三一学院的好友——著名的数学家和物理学家哈密顿（Williarn Rowan Hamilton）。可惜哈密顿并没有重视这一问题，三天后的10月26日写了回信给莫根说：“我可能不会很快就考虑你的颜色‘四元组’问题。”以后就再无下文，直到他1865年去世，也没有对此问题进行过研究。可是莫根却仍在以各种方式对四色猜测进行着传播。1860年4月14日莫根在四色问题提出8年后，在一篇书评中还再一次的传播着这一问题。由于莫根的努力，四色问题才引起了数学界的重视。
3、四色问题得到了数学界的重视：
猜测提出26年后的1878年6月13日伦敦的数学会上，四色问题又活跃了起来。6月17日英国数学家凯莱（Cayley）正式询问了地图四色问题是否得到解决。在第二年的英国皇家地理学会上凯莱再一次提出了这个问题，并在该会创办的第一卷会刊上发表。于是，四色问题才开始吸引了一批有才华的人去研究它，才开始引起了数学界的重视。并分别于1879年和1880年先后有坎泊（Alfred Kempe）和泰特（Peter Guthrie Tait）等人都宣布自已证明了四色猜测是正确的。但这时还并没有弄清楚提出猜测的人是谁。然而就在这时的1880年，法朗西斯的弟弟（当时已是一位物理学家了）才在爱丁堡皇家学会的刊物上发表了一篇短文，说大约在30年前，他还是莫根班里的一名学生的时候，是他的哥哥法朗西斯首先告诉了他地图四色问题的，因为他无法解决，才去请教他的老师莫根的。虽然最先提出猜测的人虽已弄明白了是法朗西斯，但时间却过去了28年。
4、地理问题转化成了数学问题：
从图论上看，行政区划地图就是一个连通且无割边的3—正则平面图,即是每个顶点都连有3条边的平面图。给地图中区域的染色就相当于给地图的对偶图——极大平面图（每个面都是三边形面的平面图）的顶点着色。这就把一个地理学中的问题转化成了数学中的问题了。地图四色猜测也就变成了平面图的四色猜测。
5、极大平面图的四色问题解决了，也就解决了任意平面图的四色问题：
在顶点数相同的平面图中，以极大平面图的边数为最多，如果任意的极大平面图的四色猜测是正确的，则极大图经减边或去顶后所得到的任意平面图的色数就只会是减少，而决不会再增加。所以说证明了极大平面图的四色猜测，也就证明了任意平面图的四色猜测。
6、四色问题研究的对象是无穷多的：
平面图有无穷多个，且每一个平面图中的顶点数也可以是任意多的，每一个平面图中的每一个顶点所连的边数（即度）也可以是任意多的，所以说四色问题所研究的对象是无穷多的。四色猜测也是不可能用对一个个的图去着色进行证明的，而必须把研究对象的无穷性变成有穷的。把一个无穷的问题转化成一个有穷的问题去解决。
7、坎泊提出的“构形”概念：
为了证明四色猜测，律师出身的坎泊在1879年提出了“构形”的概念。对任何极大平面图着色时，已着过色的顶点一定是符合着色要求的（相邻顶点不用同一颜色），也总能遇到待着色顶点是处在一个已着色的轮形图的中心位置的情况。把待着色顶点与已着过色的顶点共同构成的图叫做构形，并把与待着色顶点相邻的顶点叫做围栏顶点。由于待着色顶点也可以与任意多的围栏顶点相邻，所以构形的种类也是无穷多的。
8、平面图的不可避免构形——轮构形：
图论中可以证明，任何平面图中一定存在着至少一个顶点的度是小于等于5的。也就是说，在任何平面图中，度小于等于5的顶点是不可避免的存在的。用坎泊的地图术语来说，就是在任何地图中，都至少存在着一个国家与两个国家、三个国家、四个国家、五个国家相邻这四种情况中的一种。因此，所有顶点的度都是大于等于6的平面图和所有国家的邻国数都是大于等于6的地图，都是不存在的。这就为把无穷多的构形转化成有限多的5种不可避免的构形创造了条件。在着色过程中，我们总可以把待着色的顶点放在度是小于等于5的顶点上。只要证明了这五种不可避免的构形（简称不可免构形）是可4—着色的，也就证明了四色猜测是正确的。由于不可免构形的待着色顶点都是位于一个轮的中心顶点之上，所以也叫做轮构形。这就把一个研究对象是无穷的问题转化成了一个研究对象是有限的问题了。
9、3—轮以下的不可免构形都是可约的：
不可免构形的围栏顶点所占用的颜色数不大于３时，就至少还有一种颜色可以给待着色顶点着上。很自然的，不言而喻，3—轮以下的不可免构形和围栏顶点所占用的颜色数不大于3的所有构形，包括4—轮和5—轮两个不可免构形，就都一定是可约的了，即是可4—着色的。坎泊早在1879年就证明了这一点。“可约”一词也是坎泊早期提出的一个概念。
10、坎泊创造的颜色交换技术：
把用两种颜色交替着色的、由“顶点—边—顶点”构成的序列叫做色链，简称“链”。交换链中各顶点的颜色，可以达到改变链中任何一个顶点颜色的目的。这就是坎泊在1879年为证明四色猜测所创造的颜色交换技术。
11、4—轮构形的可约性：

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

当5—轮构形的围栏顶点已占用完了4种颜色的情况下，至少有一种颜色在围栏顶点中是用了两次的。把由两个相同颜色的顶点所夹的顶点叫做构形的峰点，则双B夹A型的构形就用BAB表示，峰点着A色。坎泊在1879年早就用他所创造的颜色交换技术，证明了除图2,b的一种含有相交叉的A—C链和A—D链的5—轮构形外，其他不含相交叉链的5—轮构形都是可约的（以后人们就把坎泊已证明了是可约的构形叫做K—构形），就宣布他证明了四色猜测是正确的。但他却遗漏掉了含有相交叉链的这一种情况。1880年，又有泰特根据另外一个错误的猜想“每个平面三次图都有哈密顿圈”给出并宣布了四色猜测的另一个“证明”。与此同时，泰特还提出了一个猜想：无割边且连通的3—正则平面图的可3—边着色，等价于其可4—面着色。一时间人们误以为四色难题就这样被解决了，于是攻克四色难题的热战也就这样的降温了。除了以上两个证明外，当时还有由Frederick Temple发表的另一个错误的证明。
13、赫渥特构造了含有A—C链和A—D链相交叉的构形：
1890年，即在坎泊宣布他证明了四色猜测的11年之后，英图的赫渥特（Percy John Heawood）构造了一个其中含有A—C链和A—D链相交叉的图——赫渥特图（如图3，图中的b，r，y，g分别相当于这里所说的A，B，C，D四种颜色），指出了坎泊的证明有漏洞。但当时赫渥特和坎泊却都不能对他的图进行4—着色。1896年de la Vallee-Poussin也独立的发现了坎泊的这一错误，直到1972年Saaty也还给出了与赫渥特图同样的图，但他们也都没有把坎泊的漏洞弥补起来。后来在长达整整一个世纪的时间里，也一直没有人能对赫渥特图进行4—着色。四色猜测的证明一直处在停滞不前的状态。

1890年以后，四色猜测的证明在整整的停止了30年后，1920年（有一说是1939年）又开始复燃起来。但这时的证明则成了在地图中不断的增加国家数量的办法，在许多人的接力赛中，地图中的国家数由1920年最初的22个增加到1975年的52个（有一说是95个），进展非常的缓慢，平均每年只增加0.55个（或1.33个）国家。而这种证明只能说是对地图染色的实践，算不上是理论证明。直到1976年6月，才有了阿贝尔（Kenneth Appel）等人的所谓用高速计算机对四色猜测的“证明”。
又是在泰特宣布他也证明了四色猜测64年之后的1946年，著名图论大师塔特（Tutte）构造出一个没有哈密顿圈的平面三次图，这时人们才又发现，泰特的证明又错了。但泰特提出的“无割边且连通的3—正则平面图的可3—边着色，等价于其可4—面着色”的猜想，却被证明是正确的。
14、赫渥特“证明”了错误的“五色定理”和得到了正确的多阶曲面上的地图着色公式：
正是由于赫渥特构造的图是坎泊证明中所遗漏了的一类构形,当然按当时坎泊的水平,他也一定是不能对其进行4—着色的。否则,不就没有赫渥特找出了坎泊证明中有漏洞的这回事了吗。于是就发生了坎泊在英国数学会上承认自已“弄错了”的一幕。虽然如此，但赫渥特却用坎泊的颜色交换技术，生搬硬套的“证明”了错误的“五色定理”。有人说，赫渥特并不是对他的图不能4—着色，而只是指出了坎泊的证明中有漏洞，也并不是对四色猜测的否定。那么请问，为什么赫渥特图能留传到一个多世纪后的今天，而赫渥特对他的图进行了4—着色的方法和着色模式，就不能留传到今天呢。既然赫渥特图是可4—着色的，那么，赫渥特为什么还要“证明”所谓的“五色定理”呢。这不是相互矛盾的吗。这不就是对四色猜测的否定吗。
赫渥特一生研究四色问题整整六十年，但最终却没有弥补上坎泊证明中的漏洞，也没有能解决他的图的4—着色问题。虽然如此，赫渥特却给出了一个多阶曲面上的地图着色公式γn≤  （n≥0）。这个公式断言，能够嵌入亏格为n的曲面上的所有图的色数γn一定是小于等于 的（式中n是曲面的亏格）。由于赫渥特不能对自已的图进行4—着色，所以他在公式之后仍注有（n≥0）的字样。但实际上当图的亏格n＝0时，平面图的色数γ0≤4也是正确的。这就是四色猜测，哈拉里在他的《图论》一书中，已经指出了这一点。其实，这个公式是可以通过欧拉公式推倒出来的，对于亏格为0的平面图也是适用的，后面的附加条件（n≥0）是可以不要的。
15、赫渥特图是可以4—着色的：
赫渥特的图真是不可以4—着色吗，不是的。一个世纪后的1990年前后，就有我国的雷明，懂德周，英国的米勒等人仍然都还是用了坎泊的颜色交换技术，对该图在赫渥特原着色的基础上进行了4—着色，对坎泊证明中的漏洞进行了弥补。同时还有我国的许寿椿团队，也用了现代化的手段，用他们自已所编写的着色程序（算法），在电子计算机上对赫渥特图裸图（即一个顶点也未着色的赫渥特图）也进行了4—着色。这就从不同的角度上都说明了赫渥特的图是完全能够4—着色的。
16、对赫渥特图的分析：
赫渥特图中连通的A—C链和A—D链都是不能交换的，即就是交换了，也是空不出A，C，D三种颜色之一的。而B—C链和B—D链虽然不连通，但交换了其一B—C（或B—D）链，移去一个同色B后，又会生成连通的另一条B—D（或B—C）链，而不可能连续的移去两个同色B。既然是连通链，就不能进行交换，交换了也是空不出第二个同色B的。但赫渥特却硬是要交换这种连通链，能空出颜色来吗。1990年前后，我国的雷明，董德周，张彧典和刘福等爱好者，陆续的都看出了赫渥特在对他的图着色中交换了连通链的这一步是错误的。赫渥特图不能直接空出任何一种颜色这种情况的产生，则完全是由于A—C链和A—D链的相交叉所引起，所以该两链的相交叉就至少是构成H—构形的必要条件。把具有与赫渥特图这种相同结构和性质的构形，人们就叫做H—构形。又由于H—构形不能直接使用坎泊已用过的交换方法空出任何一种颜色给待着色顶点，所以人们也把这种构形也叫做“染色困局”。在H—构形中，以上的A—C，A—D，B—C和B—D四种链均不能交换，也空不出任何一种颜色来。那么，现在就只能再看一看A—B链和C—D链是否可以交换了。
17、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—构形的不可免集，并且是非常完备的。这里请注意，以上所说的链都是指经过了围栏顶点的邻角链，以后再提到链时，也都是指这样的链。
18、不可免的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—构形而可约。1990年前后，我国的雷明和董德周二人就是看到了赫渥特图中有环形的C—D链，用交换该环形链内、外的任一条A—B链的这种办法，使A—C链和A—D链断链，使图成为K—构形，对赫渥特图在赫渥特原着色的基础上进行4—着色的。
以上两种有环形链的构形的解决办法，不仅适用于H—构形，而且也适用于K—构形。只要是含有环形链的构形，可以不去管它是否是H—构形，都可以用同样的方法进行解决。
③　无任何环形链的构形（如图6，c）：构形中A—B链和C—D链均不能交换，现在也就只能先交换一条关于B的链，先移去一个B，使构形转型了。对于BAB型的构形，从左B交换了B—D链后，成为DCD型；从右B交换了B—C链后，成为CDC型。然后再看转型后的构形，是否已成为可以连续的移去两个同色D（或C）的K—构形，或者成为以上两种有环形链的可约的H—构形。若仍不可约时，就继续进行同方向的转型，一定是可以在有限次的交换内，空出颜色给待着色顶点的。这种构形及其解法，就是我国的张彧典先生的第八构形及其解决办法。这种“转型交换”的交换次数为什么是“有限的”，在后面第22节到第24节将给以证明。
19、5—轮构形转型交换的周期是20：
5—轮构形有5个围栏顶点，围栏顶点共占用了4种颜色。进行连续的转型交换，使得构形又转型成为BAB型，峰点A又回到原来的5—轮最上方一个顶点时，需要的交换次数是4和5的最小公倍数20次。这时，围栏各顶点的颜色均与最初转型前的颜色完全相同。再继续进行转型交换时，构形将以每20次交换为一个周期，无穷的转型下去，永远也不能空出颜色来。无论是进行逆时针方向转型，还是进行顺时针方向转型，都有同样的特点。
20、敢峰—米勒图类构形虽是无穷转型也空不出颜色的图，但却是可4—着色的：

有没有无穷次转型交换也空不出颜色来的构形呢？有。这就是敢峰—米勒图类的构形（如图7）。该类构形的确是无穷次的转型交换也空不出颜色的，两个方向的转型均是如此。许多学者的研究都说明了该图的转型过程的确是无穷循环的，循环的周期是20。但由于该类构形中有一条经过了围栏顶点的环形的A—B链（见图7，b中的外圈加粗边），可以交换A—B环形链内、外的任一条C—D链，使图变成K—构形而可约。该构形虽是无穷转型的，但却是可以4—着色的。
我们只知道敢峰—米勒图是在1992年前后，分别由我国的敢峰先生和英国的米勒构造出来的。但米勒解决不了该图是否可约的问题，而敢峰先生却用交换环形的A—B链内、外的任一条C—D链的方法解决了该图的可约性问题，所以我把该图叫做敢峰—米勒图。后来看到张彧典先生在网上发文介绍，说敢峰—米勒图实际上早在1921年就由埃雷拉（A•Errera）给出过，并且在1935年已由Kittell对该图进行了4—着色，同样也是走了交换A—B环形链外侧的C—D链才使构形变得可约的，移去了两个同色B。由于这一情况我们知道得较晚，已经把敢峰—米勒图叫了出去，并且已经叫习惯了，所以仍叫它为敢峰—米勒图（看来以后还得要把该图叫做埃雷拉图或Errera—图了）。
张彧典先生介绍Kittell解决埃雷拉图（E—图）的文章一篇叫《对已部分4—染色地图的一组操作》作者是Irving•Kittell,发表时间是1935年；另一篇叫《坎泊再研究》，作者是Joan Hutchinson and Stan Wagon（琼•哈钦森和斯坦•马车），发表时间是1998年。两文说的Kittell解决的办法都与敢峰先生的解决办法是完全相同的。
后来在2010年我国的张彧典先生也用与Kittell和敢峰先生同样的办法解决了敢峰—米勒图的4—着色问题。虽然敢峰—米勒图是无穷次的转型交换也空不出颜色的构形，但其转型的每一步所得的结果，却都是含有环形链A—B的构形，交换环形的A—B链内、外的任一条C—D链，都可使图变成K—构形而可约。
21、敢峰—米勒图类构形的特征：
敢峰—米勒图中含有经过了围栏顶点的A—B环形链和不经过围栏顶点的C—D环形链（见图7,b中的加粗边）。而在敢峰—米勒图中增加了一些“四色构件”（即在图中增加一些顶点和边，并对所增加的顶点进行4—着色，但却不能影响图中原来任何顶点的颜色）的图，虽然图中原有的经过了围栏顶点的A—B环形链和不经过围栏顶点的C—D环形链依然存在，但有些图依然是敢峰—米勒图一类的构形（如图8，a），仍是无穷次转型交换也空不出颜色来的；而有些图却不再是无穷次转型交换也空不出颜色来的构形了，如图8，b逆时针转型交换13次就空出了颜色B，而顺时针转型交换4次又可以空出颜色A。

而在敢峰—米勒图中增加了四色构件的图中，即就是原有的A—B环形链依然存在，但只要不存在原有的C—D环形链了，或者改变了该图中某些四边形对角线的图，或者根本就没有敢峰—米勒图特征的图，就都不再是或者不是敢峰—米勒图类的构形了。无任何环形链的H—构形就是这种构形，根本就不具备敢峰—米勒图的任何特征，所以一定是可以经过有限次的转型交换，就可以空出颜色来的构形。

（未完，接下贴）

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，