《四色猜测的手工证明——证明四色猜测的十多种方法汇编》（一）

雷明85639720

三十多年研究四色问题的总结：

《四色猜测的手工证明——证明四色猜测的十多种方法汇编》（一）
                                  雷  明
                                      
  

                          二○一七年七月•西安

四色问题简介

四色猜测也叫四色问题。
四色猜测是1852年由英国的绘图员法朗西斯在绘制英国地图的过程中提出的。即是把一个平面分成若干个区域，给每一个区域染上一种颜色，使得有共同边界的区域不着同一颜色，大概最多四种颜色就够用了。
由于法朗西斯自已不能对其进行证明是否正确，便请教他当时正在大学读书的弟弟，弟弟也不能解决，经哥哥的同意后，便请教自已的老师——伦敦大学的教授、著名的数学家莫根。可莫根也无法解决，但他认为这是一个崭新的东西。便又把这个问题写信告诉了他在三一学院的好友、著名数学家和物理学家哈密顿。可惜哈密顿并没有重视这一问题，三天后他对莫根回信说：“我可能不会很快就考虑你的‘四元组’问题”。但以后再无下文。虽然是这样，莫根仍在大力的对四色问题进行着传播。由于他的努力，四色猜测也才引起了数学界的重视。
四色猜测自提出以后，整整过去了二十六年，到了1878年6月13日在伦敦的数学会上，著名的英国数学家凯莱正式询问四色问题是否得到解决。在次年的英国皇家地理学会上，凯莱再次提出了这一问题，并在该会创办的学会会报上发表。这时四色问题才引起了人们的高度重视。吸引了一批有才华的人才去研究四色问题。
1879年，律师出身的坎泊，在《自然》杂志上发表文章宣布他证明了四色猜测；1880年泰特又根据一个错误的猜想——每个平面三次图都有哈密顿圈——也给出了一个证明。但在11年后的1890年，赫渥特构造了一个图，找出了坎泊证明中的漏洞；而又在六十六年以后的1946年，著名图论大师塔特构造了一个没的哈密顿圈的平面三次图，证明了泰特的证明也是错误的。
在1890年以后的一个多世纪里，虽有大量的人才去对四色猜测进行研究，但都没有从理论上使四色猜测得到彻底的证明，直到现在，四色猜测是否正确，仍然还是一个迷。
四色猜测自1852年提出后，已有二十八年过去了，也无人知道四色猜测是谁提出的。到了1880年，四色问题引起了人们的高度重视后，提出者——法朗西斯的弟弟（当时已成为一名物理学家）才在杂志上发表文章说：大约在三十年前，他当时还是莫根班里的一名学生的时候，他的哥哥法朗西斯首先告诉他地图四色问题。因为他无法解决，所以才去请教他的老师莫根的。二十八年过去后，总算找到了猜测的提出人。法朗西斯自已后来也成为一名数学教授，任教于开普敦的南非大学，一直活到1899年。可惜他对自已提出的四色猜测并无任何建树。尽管如此，但他却是第一个提出四色猜测的人，时间是1852年。

现在，四色问题早已由一个给地图的面（区域）上染色的地理学的问题，转变成了一个给图论中平面图的顶点着色的数学问题了。把地图中各相邻区域的中心城市（顶点）用曲线（边）经过两个区域的边界线连接起来，就构成了一个平面图。给平面图顶点的着色也就相当于给地图的区域的染色问题。 同样也有任何平面图的色数都不大于4的猜测。这就是数学中的四色问题。

作者从1985年开始，全部利用业余时间独立的对四色问题研究了三十多年，现将自已的研究结果，整理成此册，献给四色爱好者，或许也能对四色问的研究起到一点促进作用。

作者：雷  明
二○一七年四月三十日于长安

目    录

代前言：四色问题简介                                 （2）
目录                                                 （5）

1、我研究四色问题的思想方法                              （8）
（1）把一个无限的问题变成有限的问题                   （8）
（2）5—轮构形都是可约的                             （12）
（3）四色猜测是正确的                                （17）
2、四色猜测是可以手工证明的                             （18）
（1）H—构形的不可免集                               （18）
（2）H—构形不可免集完备性的证明                     （20）
（3）不可免的H—构形可约性的证明                     （23）
（4）有环形链的H—构形一定可以通过“断链”交换
转化成K—构形的证明                                 （26）
（5）无环形链的H—构形也一定可以通过“转型”交
换转化成K—构形的证明                               （27）
（6）四色猜测的证明                                  （29）
3、无割边的3—正则平面图是可3—边着色的，四色猜测正确！ （31）
（1）泰特猜想是正确的                                （31）
（2）无割边的3—正则平面图都是可3—边着色的         （39）
（3）对无割边的3—正则平面图都是可3—边着色的检验   （42）
（4）四色猜测的证明                                  （49）
4、用增加图的色数证明四色猜测的两种方法                 （51）
（1）根据不可同化道路原理，证明四色猜测是正确的      （51）
（2）根据米歇尔斯基操作原理，用反证法证明四色猜测    （54）
5、公式推导证明四色猜测的三种方法                       （61）
（1）用平面图中可嵌入的最大完全图的顶点数来证明      （61）
（2）用平面（或球面）上不存在五色地图来证明          （62）
（3）用赫渥特地图着色公式来证明                      （65）
（4）林格尔公式与赫渥特地图着色公式是互为反函数的，
可以相互推导，但不能用以相互证明                     （66）
6、不用“不可免集”证明四色猜测的四种方法               （68）
（1）用哈德维格尔猜想来证明                          （68）
（2）用图的色数一定等于图的最小完全同态
的顶点数来证明                                       （68）
（3）用不可同化道路的条数小于等于图的
密度的一半来证明                                     （69）
（4）用米歇尔斯基操作来证明                          （71）
7、证明四色猜测的其他三种方法                           （74）
（1）用反证法进行证明                                （74）
（2）用数学归纳法进行证明                            （74）
（3）用断链法进行证明                                （76）
8、附录一：多阶曲面上图的欧拉公式是如何得来的           （79）
   （1）亏格为0的平面图的欧拉公式的推导                （79）
   （2）亏格为1的非平面图的欧拉公式的推导              （80）
   （3）亏格为0和1的图的欧拉公式                      （82）
   （4）多阶曲面上图的欧拉公式                          （84）
9、附录二：赫渥特地图着色公式也适用于亏格为0的平面图   （87）
（1）赫渥特地图着色公式的推导                        （87）
（2）任意图顶点平均度的界                            （88）
（3）韦斯特对赫渥特地图着色公式的证明               （100）
（4）赫渥特地图着色公式同样也适用于亏格为0的平面图 （103）

编后记：                                           （106）

我研究四色问题的思想方法
雷  明
（二○一七年元月十日）

1、把一个无限问的题变成有限的问题
图有平面图，有非平面图；平面图中又有道路，树，圈，轮，完全图，极大图等多种种类；每一种类中又有无限多的图，每个图的顶点又可以是无限多的，每个顶点的度也可以是无穷多的；四色问题就是与这些取值是无限多的参数交织在一起，也成了一个无限的问题。
1、1  平面图的着色
不管平面图是如何的复杂，着色时总是一个一个顶点去着的，当遇到待着色的顶点的相邻顶点已占用完了四种颜色时，总可以把该顶点周围的色圈想办法断开，使这个色圈中减少一种颜色。这就是“破圈”。
1、2  破圈着色法
可以把待着色顶点外面的色圈中使用次数最少的颜色的顶点，作为切入点，把该顶点的颜色去掉，并把该种颜色给这个待着色的顶点着上。与此同时，又将产生一个或多个待着色的顶点。新的待着色顶点周围若仍占用完了四种颜色时，就再继续的“破圈”，否则，新的待着色顶点就可着上图中已用过的四种颜色之一。
1、3  待着色顶点的着色
当图中除了待着色顶点外，所有的顶点都已着上了四种颜色的一种，也不存在相邻两顶点着有同一颜色时，有以下几种情况：
1、3、1  当待着色顶点的相邻顶点所占用的颜色少于四种或者该顶点的度小于等于3时，直接就可以给该顶点着上第四种颜色。
1、3、2  当待着色顶点的相邻顶点已占用完了四种颜色，且其度大于等于6时，就用破圈法；一直破下去，一定能找到一个新待着色顶点的度是小于等于5的；因为任何平面图中一定存在着至少一个顶点度是小于等于5的顶点。
1、3、3  以顶点度小于等于5的顶点构成的轮形构形，就是平面图的不可避免构形，轮的中心顶点叫做待着色顶点，用V表示，轮沿顶点叫做围栏顶点，简称“围栏”。这些不可避免的构形只要是可约的，即待着色顶点是可以着上四种颜色之一时，平面图的四色猜测就是正确的。由这些不可避免的构形构成的集合，就是平面图的不可免集。
1、3、4  若最后一个待着色顶点的度是小于等于4的，它一定是可以着上四种颜色之一的，因为坎泊已经用他创造的颜色交换技术的三种作用之一——“空出颜色”的交换，证明了这种构形是可约的。
1、3、5  所谓颜色交换技术，就是把由两种颜色交替进行着色的道路（这种道路在着色中叫做色链，简称“链”）中各顶点所着的颜色互换，就叫做颜色交换，简称“交换”。把可空出颜色给待着色顶点的交换，即通过交换可以从围栏顶点中空出一种颜色来，给待着色顶点着上的交换就叫“空出颜色”的交换。这种交换一定是从围栏顶点开始的，交换的链是由两个对角围栏顶点的颜色构成的色链，但该链在两个对角围栏顶点间必须是不连通的，也就是说所交换的链中，只可能含有一个顶点是5—轮围栏上的顶点，否则是不能空出颜色的。
1、3、6  但是，在有些平面图中却不一定都存在度小于等于4的顶点，如正二十面体所对应的图，各顶点的度都是5，没有顶点度小于等于4的顶点，所以证明5—轮构形是否可约也就成了一个关键。
1、4  5—轮构形
把5—轮构形的轮沿顶点的名称用1，2，3，4，5表示，相应的各顶点所着的颜色用B，A，B，D，C表示。这样的5—轮构形可表示成123—BAB型5—轮构形（如图1）。

1、4、1  1879年，坎泊只证明了5—轮构形中的：①无连通链，②只有一条连通链，③有B—C和B—D两条交叉的连通链和④有A—C和A—D两条连通链有共同的起始顶点2A、且链的中途没有交叉顶点的这四种情况下，5—轮构形都是可约的；而没有证明A—C和A—D两条连通链既有共同的起始顶点2A，但两链在中途又有相交叉顶点时的这一情况是否可约。这是坎泊证明中的一个疏漏。
1、4、2  在A—C和A—D两链既有共同的起始顶点2A，中途又有相交叉顶点（如图2中的顶点8）的情况中，也有可以同时移去两个同色B，空出B给待着色顶点着上的构形。如“九点形”构形中的含有A—B环形链（如图2，a），和既不含有A—B环形链，也不含有C—D环形链的情况（如图2，b和图2，c），都可以同时移去两个同色B。其他的一种情况（如图2，d，图中含有环形的C—D链）则是不能同时移去两个同色B的构形。这就是坎泊证明中漏掉了的那种构形。

1、4、3  1890年，赫渥特构造了一个图，图中的A—C和A—D两链既有共同的起始顶点2A，中途又在顶8A处相交叉的情况的图，该图也是不能同时移去两个同色B的。赫渥特就是用这个图指出了坎泊的证明中有漏洞的。可惜赫渥特和坎泊都并没有把这个漏洞补上。
不能同时移去两个同色B是赫渥特图型构形的特点，把这种构形叫赫渥特构形，用H—构形来表示；而把坎泊已证明是可约的构形和所有可以同时移去两个同色B的构形统一叫做坎泊构形，用K—构形来表示。所以就目前看，证明H—构形是否可约就成了证明四色猜测的一个最关键的问题了。
到此，我们就把一个无限的四色问题变成了一个有限的问题。
2、5—轮构形都是可约的
2、1  H—构形
2、1、1  H—构形又有四种情况：①只含有一条A—B环形链的（图3，a）；②只含有一条C—D环形链的（图3，b）；③既含有A—B环形链，又含有C—D环形链的（图见下一篇文章中的敢峰—米勒图。本文中以下的图都与下一篇《四色猜测是可以手工证明的》（简称《手工证明》）中的图相同。此处应见《手工证明》一文中图1和图2中的e图，下同）；以及④任何环形链都不含的（图3，c和图3，d）；共四种（如图3）。图中只要顶点6和顶点7之间不是直接相邻时，图就成了可以同时移去两个同色B的K—构形，而不是H—构形了。
在H—构形中，A—C链和A—D链是连通的，不能交换，因为它空不出颜色，所以A，C，D三种颜色均不可能空出来给待着色顶点V；B—C链和B—D链又不能同时交换，所以也不能空出B给待着色顶点V。但可以想办法破坏连通的A—C和A—D链，使其成为不连通的，使构形变成K—构形而可约。
2、1、2  含有A—B环形链的构形，A—B环必然把C—D链分成环内、环外互不连通的两部分（如图3，a），交换环内、环外的任一部分C—D链，都可以使A—C和A—D链断开。使构形变成为不含有连通的A—C和A—D交叉链，又可以同时移去两个同色B的K—构形（图3，a就可以变成这种构形，具体操作见《手工证明》一文中的图5）。这种情况与含有A—B环形链的“九点形”（如图2，a或图3，a中去掉小黑点顶点后的图）构形则是不同的。这里的含有A—B环形链的构形是不能移去两个同色B的，而“九点形”构形则是可以同时移去两个同色B的构形。所以这种含有A—B环形链的“九点形”构形是属于K—构形一类。

2、1、3  含有C—D环形链的构形，C—D环也必然把A—B链分成环内、环外互不连通的两部分（如图3，b），交换环内、环外的任一部分A—B链，也都可以使A—C和A—D链断开。使构形变成为不含有连通的A—C和A—D交叉链，但又不可以同时移去两个同色B的K—构形，或者也可以同时移去两个同色B的K—构形（图2，d和图3，b都可以变成这种构形，具体操作见《手工证明》一文中的图6）。赫渥特图就是这样着色的。这就是赫渥特图型的H—构形。这种情况与含有C—D环形链的“九点形”构形（如图2，d或图3，b中去掉小黑点顶点后的图）的解法是相同的，用的都是断链法。所以这种含有C—D环形链的“九点形”构形却是一个H—构形。
2、1、4  既含有A—B环形链，又含有C—D环形链的构形（图见《手工证明》一文中的图1和图2中的e图），既可以交换A—B环内、外的任一条C—D链，也可交换C—D环内、外的任一条A—B链，都可以使构形变成为K—构形。敢峰—米勒图就是这样着色的，所以敢峰—米勒图是一个H—构形。这种构形，可以单独成为一类，也可以归入以上图3，a和图3，b两类中的任一类中，因为该图具有以上两类构形的特点，解决办法又是用其中任一种的解决办法都可以，所以不单独列为一类也是可以的。
2、1、5  这里虽然也用的是坎泊的颜色交换技术，但其交换的目的却不是空出颜色，而是“断链”，这就是坎泊的颜色交换技术的第二种作用——“断链”的作用，所以叫“断链交换”。这种交换并不是为了空出颜色给待着色顶点，而是为下一步空出颜色的交换作好技术上的准备。
这种断链交换可以是从非围栏顶点（即非5—轮的轮沿顶点）开始的，交换的链中不含有5—轮的轮沿顶点，如图2，d和图3，b从顶点8A开始的A—B的交换,以及图3，a从顶点6C（或7D）开始的C—D链（边）的交换；也可以从5—轮的轮沿顶点开始，但交换的链中至少含有两个以上的顶点是5—轮的轮沿顶点，如图2，d和图3，b从顶点2A开始的A—B链的交换，以及图3，a从从顶点4D（或5C）开始的C—D链（边）的交换。
2、1、6  在H—构形中，唯独不含A—B和C—D任何一种环形链的构形（如图3，c和图3，d）是不能用这种“断链”的方法处理的，这就是张彧典先生的第八构形，我们叫它Z—构形，因为它是类似于张彧典先生的第八构形型的H—构型。
2、2  Z—构形
2、2、1  Z—构形的特点：在不含任何环形链的H—构形——Z—构形中，A—C链和A—D链都是连通链，不能交换；A—B链和C—D链也都是直链，且只有一条，也不能交换。即就是交换了，也只等于整个链中的两种颜色互换了一下位置，不起任何作用；B—C链和B—D链又不能同时交换。那么我们就只有先交换一个关于B的链。
2、2、2  转型交换：从任一个同色顶点B进行交换时，5—轮构形的类型就会发生改变：若从顶点1交换了B—D链，构形就由原来的123—BAB型变成了451—DCD型（图见《手工证明》一文中的7）；若从顶点3交换了B—C链，构形则也由原来的123—BAB型变成了345—CDC型（图见《手工证明》一文中的图8）。虽然也是在进行坎泊的颜色交换，但交换的目的却是在于使构形进行转型，所以把这种交换叫做“转型交换”。注意，这种转型的交换也是从围栏顶点开始的，并且必须是从两个同色B中的一个同色顶点B开始的。
2、2、3  从“九点形”构形看，不含任何环形链、但可以同时移去两个同色B 的构形（如图2的b和c）与H—构形（如图2，d）是可以相互转化的；而Z—构形与“九点形”中可以同时移去两个同色B的构形又有相同的特点，即A—B链和C—D链都是直链且只有一条，它一定也应是可以转化为类似b类的H—构形的。理论和实践都已经证明了这一点是正确的（因为Z—构形的最简模型是一个“十五点形”，其中就有一个只缺少一个B色顶点的A—B圈，当从顶点1（或3）交换了B—D（或B—C）后，正好就使得这一缺少得到了弥补，该顶点正好就变成了B，构形变成了一个451—DCD（或345—CDC）型的有A—B环形链的类似b类的H—构形。（图见《手工证明》一文中的图10），证明了Z—构形是可以通过转型交换转化成为赫渥特图型的H—构形的。这是一个必然的结果，而并非偶然；另外，实践和理论也能证明，Z—构形还可以通过与以上的交换是相反方向的转型交换后，可以直接转化成为可以同时移去两个同色C或D的K—构形（图见《手工证明》一文中的图9）。总之，这都说明了Z—构形是可以转化为K—构形的，是可约的。
2、2、4  到此，坎泊的颜色交换技术的三种作用都已经设及到了。现在还要说的一点是：当图是可以同时移去两个同色B的构形时，一定是要进行两次交换才能达到同时移去两个同色B的目的。第一次交换是属于转型交换，把123—BAB型的构形转化成为451—DCD型的构型，或者转化成为345—CDC型的构形，而第二次交换则是属于空出颜色的交换。空出来的颜色B对于原来123—BAB型的构形来说，是两个同色的B，而对于新的构形类型来说，则是非两个同色C或D之外的B。
到此，我们也就证明了所有的5—轮构形都是可约的。
3、四色猜测是正确的
到此，平面图的所有不可免的构形都是可约的了，当然平面图的四色猜测也就是正确的了；平面图的顶点着色又相当于是对地图的面在染色，这也就证明了地图的四色猜测也是正确的；这就证明了四色猜测是正确的。


雷  明
二○一七年元月十日于长安


注：此文已于二○一七年元月十一日在《中国博士网》上发表过，网址是：
原文是以与张彧典先生交换意见的形式出现的，这次录用时去掉了与张先生交换意见的部分，并对保留部分的文字稍作了修改，也增加了图。

（未完，接下贴）

雷明85639720

，，，，，，

雷明85639720

，，，，

雷明85639720

，，，，

simpley

四色猜想计算机证明方法是什么？

雷明85639720

simpley:
1、我也不清楚电子计算机是怎么证明的。但我知道计算机是人造的，是人脑智慧的产物，它完全是按人的意志去工作的。所以我认为人还不能解决的问题，计算机也是不能解决的。
2、所谓最子计算机“证明”了四色猜测，我认为只不过是用计算机对大量的图进行了4—着色而已，与人用手工对一些图进行的4—着色，具有相同的作用。不能算作是证明，因为其所着过色的图再多也只是个别的，仍不能代表一般。
3、计算机只所以会着色，是因为人会着色，人可以把着色的方法步骤编成程序，交给计算机，再给计算机输入仍是属于个别的、但又是大量的图，让计算机代替人去进行着色。
4、不能说因为计算机对大量的图进行了4—着色（人是不可能办到的），就说明计算机是证明了四色猜测，其实它着色再多，仍与人手工对几个图的着色作用是相同的，都不是把所有的图都着色完了的。所以四色猜测仍未被子证明是正确还是不正确。
5、你给你介绍一个网址，你自已去看一看吧。阿贝尔的《四色地图问题的解决》一文。网址是： 网址发的结果是，我没有权在这里发，那就只能你自已打题目去在网上去搜索了。
再见。

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，