四色猜测证明大事记和最终证明

雷明85639720

四色猜测证明大事记和最终证明
雷  明
（二○一九年九月二十九日）

1、四色猜测证明的大事记
1、1、第一阶段：四色问题的提出（1852——1878年）
1852年10月以前，英国的绘图员法朗西斯在给英国地图染色时，首先提出了地图四色猜测。
1852年10月，法朗西斯请教他的弟弟弗内德里如何能够证明。
1852年10月23日，弗内德里请教他的老师伦敦大学的教授、著名数学家莫根。
1852年10月23日，莫根认为这是一个斩新的事物，但由于他也不能进行证明，当天就写信给他在三一学院的好友、著名数学家和物理学家哈密顿，告诉并请教他地图四色猜测的证明问题。当天写信就充分说明了莫根对这一问题的极大重视。
1852年10月26日，哈密顿回信说“我可能不会很快就考虑你的颜色‘四元组’问题。”当即又给了地图四色问题当头一棒，以后便再无下文了。使得这一斩新的事物被封杀了整整26年。
1860年4月14日，莫根仍在坚持对四色问题进行着传播，在一个书评中还留下了他传播四色猜测的信息。
1878年6月13日，伦敦的数学会上，四色问题又活跃了起来。
1878年6月17日，英国数学家凯莱正式询问了地图四色问题是否得到解决。
1879年，在英国皇家地理学会上凯莱再一次提出了四色问题，并在该会创办的第一卷会刊上发表。
1、2、第二阶段：第一次证明热潮（1879——1890年）
1879年7月17日，律师出身的业余数学家坎泊（Alfred Bray Kempe）在《自然》杂志上发表论文，宣布他证明了四色猜测。坎泊首先提出了在证明四色猜测过程中常用的“色链”和“构形”的术语，并创造了颜色交换技术。所谓色链，就是用两种颜色交替着色的一个序列，并简称“链”；所谓构形，就是除了待着色顶点以外，其他顶点都已用四种颜色进行了着色，且符合4—着色要求的只有一个顶点未着色的部分着色图；所谓颜色交换技术，就是对一条链中各个顶点的颜色都进行交换，以达到改变链中各顶点颜色的目的的一种着色方法与技巧。由于平面图的构形都是以待着色顶点为中心的轮形图，所以平面图的构形也叫轮构形。
虽然坎泊在证明四色猜测方面，首先向前迈出了一大步，并取得了决定性的成功，但他却遗漏了一种在5—轮构形中存在双环交叉链的情况，这就为后来的赫渥特对他的证明进行否定埋下了伏笔。大家习惯上把坎泊已证明过的是可4—着色的构形叫做K—构形，把坎泊所用的交换方法叫坎泊链法。
为什么说只要证明到5—轮构形在各种情况下都是可4—着色时，就认为四色问题得到了解决呢？这是因为可以证明，在任何平面图中都一定存在着度是小于等于5的顶点；顶点度全是大于等于6的平面图是不存在的。用地图的术语来说就是：任何地图中都一定存在着一国与两国相邻，一国与三国相邻，一国与四国相邻和一国与五国相邻这四种情况中的一种；所有国家都与六个以上国家相邻的地图是不存在的。据说这个结论还是由莫根最早给出证明的。有了这个证明，就可以把一个研究对象是无穷无尽的平面图的无穷问题，转化成一个研究对象只是有限的几个平面图的不可避免的构形的有限问题了。
1880年，泰特根据另外一个错误的猜想“每个平面三次图都有哈密顿圈”也给出了四色猜测的另一个错误的证明。与此同时，泰特还提出了一个猜想，即无割边的3—正则连通平面图的可3—边着色，等价于其可4—面着色。无割边的3—正则平面图就是地图，每个顶点都连着3条边，地图中也是只有三条边界线相交于一点（即三界点，三不管地区）的情况。
1880年，法朗西斯的弟弟弗内德里（当时已是一位物理学家了）在爱丁堡皇家学会的刊物上发表了一篇短文，说大约在30年前，他还是莫根班里的一名学生的时候，是他的哥哥法朗西斯首先告诉了他地图四色问题的，因为他无法解决，才去请教他的老师莫根。
1880年，虽然这时已弄明白了提出四色猜测的第一人是法朗西斯，但时间却已经从1852年过去了28年。
1890年，英国数学家赫渥特（Percy John Heawood）构造了坎泊证明中所遗漏的一种有双环交叉链情况的构形——赫渥特图（如图1），并对坎泊的证明进行了“否定”，但他却与坎泊都不能给他图中的待着色顶点V（顶点V在图1中未画出，这是隐形画法）着上图中已用过的四种颜色之一。图1是赫渥特图的简化模型，这个图中不但含有双环交叉链（如图1中的细实线的A—D链和细虚线的A—C链），而且还含有经过了构形的两个围栏顶点的环形链（如图1中的粗实线的C—D闭合链）。这个图是不能用坎泊已经用过的简单交换的方法解决问题的。

赫渥特图只所以不能用坎泊用过的简单交换解决问题，主要是因为当从顶点1交换了B—D链移去了顶点1的一个B后，便生成了从顶点3到顶点5的连通的B—C链，再不能移去第二个B；同样的，若从顶点3交换了B—C链而移去顶点3的B后，也会生成从顶点1到顶点4的连通的B—D链，也不能移去第二个B。但这里还要注意的是，图1中除了5个围栏顶点间是单边外，顶点6C和7D间也必须是单边，否则，这个图就成了可以连续的移去两个同色B的坎泊构形了。除此以外的其他边都可以认为是由该边的两个端点顶点的颜色所构成的色链。
大家习惯上也把与赫渥特图具有同样的双环交叉链的构形叫做H—构形，也叫染色困局。解决这个染色困局的办法就是只有把困局构形转化成坎泊已证明过是可4—着色的K—构形，再把围栏顶点所占用的四种颜色移去一种，使围栏顶点只占用三种颜色时，这样，待着色顶点就有颜色可着了。
1890年，赫渥特又根据坎泊的证明方法，证明了与四色问题并无关系的所谓的弱一点的“五色定理”。
1890年以后，赫渥特又得到了多阶曲面上的地图着色公式γn≤＜（7＋√（1＋48n））/2＞（n＞0），式中γn是亏格为n的多阶曲面上的色数，＜　＞表示其中的数字向下取整。由于赫渥特不能对他的图进行4—着色，所以他专门在他的这个公式之后，注明了图的亏格是大于0的附加条件。但实际上，赫渥特的图也是能够进行4—着色的，该公式同样也适用于亏格为0的平面图。
1、3、第三阶段：证明处于低潮（1891——1975年）
1891年——1920年，至少有长达30年以上的时间，四色猜测的证明实际上是处于停止不前状态的。
1896年，Vallee-Poussin也独立的发现了坎泊的证明中有漏洞这一现象，与赫渥特指出的错误是相同的。
从1921年——1976年的56年期间，所有的研究者都是在对具体的地图进行着4—着色的探索，所研究的地图中的国家数由22个逐步增加到了95个，也都是可4—着色的。平均每年只增加1.3个，进展非的常缓慢。
1921年，埃雷拉（A•Errera）给出了埃雷拉图（简称E—图，如图2，这是一个具体的图，一条边就是一条边，不能再认为是链了），其中也含有与赫渥特图相同的被坎泊证明时所遗漏了的双环交叉链（如图2中的细实线的A—D链和细虚线的A—C链）。但这个图中却含有经过了构形三个围栏顶点的环形链（如图2中的粗实线的A—B闭合链）。在这一点上埃雷拉图与赫渥特图还是有所不同的。

1935年，美图人Kittell对埃雷拉图进行了4—着色。Kittell只是对5C和4D的C—D链（当时Kittell称为“正切链”，实际上就是我们现在说的邻角链）进行了交换。他只看到了这一交换后，图变成了非染色困局，图中也没有了双环交叉链。而没有看到这一交换，原来的双环交叉链已经断开，成了不连通链；而现在图中的两条双环但不交叉的链却是新生成的连通链。原来的A—C链和A—D链都各有6个顶点，且两链在顶点8A处相交；而现在的A—C链和A—D链不但是新生成的连通链，且两链各都只有4个顶点，也并不相交。
Kittell的着色方法，也就是我们现在所说的断链交换法。因为交换了这条链后，埃雷拉图中的双环交叉链就都断开了（但Kittell当时却没有看到这一点，并且只字未提及），图也变成了坎泊已证明过的是可4—着色的构形了。
1946年，著名图论大师塔特构造出了一个没有哈密顿圈的平面三次图，说明了泰特的证明也是错误的。但泰特猜想笔者仍然认为是对的，因为笔者已经证明了无割边的3—正则平面图的可3—边着色与其可4—面着色的确是等价的，并且也证明了任何无割边的3—正则平面图的确是可3—边着色的。从此，四色猜测的证明完全的从对地图的面上的染色，转移到了对平面图的顶点的着色上来了。
1972年，Saaty也给出了一个与赫渥特图同样的图。说明了到此时的1972年，赫渥特图还是没有能够进行4—着色的。也说明了坎泊证明中的漏洞还是没有被弥补上来的。1988年4月，湖南科学技术出版社还出版了聂祖安所译的美国的M•卡波边柯与J•莫鲁卓合著的
《图论的例和反例》一书，其中再一次说赫渥特图是不可4—着色的，就说明在1990年以前，赫渥特图还没有能够进行4—着色，是一个有力的证据，是对赫渥特图并不是不能4—着色论点的一个有力的回击。
1、4、第四阶段：第二次证明热潮（1976——2019年）
1976年6月，美国的阿贝尔宣布他们用高速运转的电子计算机证明了四色猜测。由于阿贝尔证明的结果是不可视的，也是不能去进行验证的，所以许多人至今仍都认为阿贝尔的证明是不可信的。实际上电子计算机的所谓“证明”，只是在对大量（近2000个）的平面图进行了4—着色的验证，并不是在进行证明。因为平面图是无穷多的，再快的计算机也是无法验证完的。计算机对大量图的4—着色与人们用手工对某些个别图的4—着色的效果是等价的，都应是对个别图的验证，而不是证明。
1992年．中国的雷明和董德周分别独立的发现了赫渥特对他的图在着色过程中的错误做法。赫渥特的目的是想连续的移去两个同色B，但当他第一次交换了B—D链后，却生成了从另一个B色顶点到其对角顶点的B—C连通链。这样的连通链是不能进行交换的，交换了也空不出颜色。但赫渥特还是要这样交换，那怎么能空出颜色来呢？
而雷明和董德周却巧妙的交换了经过了顶点1B，2A和 3B的A—B链，使得双环交叉的A—C链和A—D链都变得不连通，创造了断链交换法，并在赫渥特原着色的基础上对赫渥特图进行了4—着色。其原理是，因为赫渥特图中含有经过了构形两个围栏顶点的环形链C—D，把A—B链分隔成了互不连通的两部分。交换了该C—D环形链一侧的经过构形三个围栏顶点的另一条相反色链A—B，不但不会使图中所有的A色和B 色顶点都换色，而且还可以使连通且相交叉的双环链A—C和A—D断链，使图成为坎泊已证明过的是可4—着色的构形。不但使赫渥特图的4—着色问题得到解决，也使得具有类似赫渥特图的一类图的4—着色问题都能得到解决。
1992年的同时，英国的米勒等也给赫渥特图在原着色的基础上进行了4—着色，创造了连续转型交换法。其原理是，交换5—轮构形围栏顶点中关于两个同色顶点的颜色的两个对角链之一，使构形的两个同色顶点的颜色以及构形的峰点位置都发生改变。经过有限的三次连续转型交换，就空出了颜色，给赫渥特图进行了4—着色。米勒他们感到这是一种解决四色问题的好途径，但当他们用同样的办法对埃雷拉图进行转型交换时，便产生了无穷周期循环转型的现象，总也空不出颜色来，他们也再没有对埃雷拉图用其他办法进行4—着色。以致他们又放弃了企图用这种转型交换的方法解决四色问题的想法。
还是在1992年，中国的敢峰先生用他创造的演绎转型法，从一个最基本的具有双环交叉链的构形开始，一步一步的通过演绎转型，构造了与埃雷拉图一模一样的图，并称之为终极图。这个终极图与埃雷拉图相同，也是一个无穷周期循环转型的构形。与米勒们不同的是，敢峰先生又注意到了埃雷拉图（或终极图）中有一条经过了构形三个围栏顶点的环形链A—B，也是在交换了该环形链一侧的经过了构形两个围栏顶点的另一条相反色链C—D后，就可以使连通且相交叉的双环交叉链A—C和A—D断链，使图成为坎泊已证明过的是可以4—着色的构形。同样的，这样做，不但使埃雷拉图的4—着色问题得到解决，也使得具有类似埃雷拉图一类图的4—着色问题都能得到解决。这就为后来雷明把具有双环交叉链的构形分为有环形链的构形和无环形链的构形打下了基础。
敢峰先生是在完全不知道地球西边的美国人Kittell已解决了埃雷拉图的可4—着色的情况下，于55年以后，在地球的东边由中国人完全独立的用了与Kittell完全相同的方法解决了埃雷拉图的4—着色问题的。实际上这两人的方法，都是属于雷明先生现在所说的断链交换法。
1999年，中国的张彧典从英国的米勒处得到埃雷拉图后，也独立的用与敢峰先生同样的方法对埃雷拉图进行了4—着色，但张先生把这一方法叫做Z—换色程序，实际上也就是雷明先生的断链交换法。从此，张先生把具有双环交叉链的构形分为无穷周期循环转型的埃雷拉图类构形和有限转型的非埃雷拉图类构形。无穷周期循环转型的埃雷拉图类构形的4—着色用Z—换色程序进行解决，而有限转型的非埃雷拉图类构形的4—着色用有限的转型交换（张先生叫做赫渥特颠倒法）进行解决。
虽然埃雷拉图以及埃雷拉图的转型产物中，都含有经过了构形围栏三个顶点或两个顶点的环形链，但这只是构成无穷周期循环转型的埃雷拉图类构形的必要条件，并不是充分条件。因为有很多含有经过构形围栏顶点的环形链的构形，并不都是无穷周期循环转型的埃雷拉图类构形，而是有限转型的非埃雷拉图类构形。赫渥特图就是一个例子，其中虽有环形的C—D链，但却是有限转型的非埃雷拉图类构形。这些构形，在后面就可以看到，它们实际上又是属于雷明先生提出的有环形链的构形，也是可以用断链交换法解决其4—着色的问题的。其实张先生的Z—换色程序就是雷明的断链交换法。
2010年以后，雷明又注意到了张彧典先生的《四色问题探索》一书中引用的埃雷拉图，其中含有经过了构形三个围栏顶点的环形的A—B链，交换了该链一侧经过构形两个围栏顶点的另一条相反色链C—D后，就可使该图的4—着色问题得到解决。结合自已对赫渥特图类构形的解决办法，从而提出了把具有双环交叉链的构形分为有经过构形围栏顶点的环形链的有环形链的构形（如图1和图2）和无经过构形围栏顶点的环形链的无环形链的构形（如图3，还有一种与图3是左右正好相反布置的构形，与图3都是同一类，这里就不再画图了。图3与图1类似，都是待着色顶点隐形画法的简化图，除了各围栏顶点间和6C和7D是单边外，其他的边也都可以看成是由该边两个端点顶点的颜色构成的色链）两大类。解决有环形链的构形的办法都是用的是断链交换法，而解决无环形链的构形的办法则是转型交换法。

解决有环形链的构形用的是断链交换法，赫渥特图与埃雷拉图的4—着色都是用这种断链交换法解决的。该方法的主要依据是因为处在环形链两侧的另一条相反色链是不可能连通的，交换一侧的相反链，并不会影响到另一侧的相反链中其他顶点的颜色。这样就不会再形成新的双环交叉链。那么解决无环形链的构形的转型交换法的原理又是什么呢？在无环形链的构形中，A—C和A—D链是连通的，不能交换，也是空不出A、C、D三色之一的；A—B链和C—D链又都是单一的直链，也不能交换，就是交换了，也不起作用，虽然原来的双环交叉链断开了，但又会产生新的双环交叉链；两个B也不可能连续的移去，而只能先移去一个，使构形的峰点和两个同色顶点的颜色和位置都发生改变，这就是转型。
转型后，再看新的类型的构形是否是可以4—着色的K—构形，再决定是采用断链法还是继续采用连续的转型交换法。如果在转型过程中产生了可以使用断链交换法的含有经过构形围栏顶点的环形链的构形时，就要立即改成断链交换的着色方法，以尽早的结束转型交换的过程。但是，如果不产生有环形链的构形，是否就一直的转型下去呢，不会的。一定是存在有一个转型次数的最大限度的界。否则，四色猜测就不可能证明是正确的。

关于有环形链的构形，以上说的都是只有一种环形链的情况，有没有两种环形链都存的情况呢？有，图4就是一个例子。这个图也是一个有环形链的构形，交换A—B环形链一侧的经过5C和4D的C—D链，就可以使图转化成可4—着色的K—构形。
2015年，雷明还注意到了埃雷拉图的转型交换的无限周期循环的特性，从其循环周期是2O次可以得到，非埃雷拉图类构形的有限转型交换的次数最大是不会超过42次的。其原理是，非埃雷拉图类构形的转型交换一定是有限的，该类构形无论是进行那个方向的转型交换，都必须在第40次转型（包括第40次转型）之内的某一次转型后，图就必须转化成为可以连续的移去两个同色的K—构形。因为转型的次数只有大于40次，转型进入到第二个循环周期时，才能看出一个构形的转形是否是无穷周期循环转型的。如果转型的次数没有达到40次，即就是已转型的次数是大于了一个循环周期的20次，也不能说它就是无穷周期循环转型的构形。
否则，如果在转型40次后，图还不能转化成可以连续的移去两个同色的K—构形时，图将是一个无穷周期循环转型交换的构形了。但这却是不可能的事，因为我们这里所说的构形就指的是有限转型交换的非埃雷拉图类的构形。然后再对这个可以连续的移去两个同色的构形进行两次关于空出颜色的坎泊交换，就一定可以空出一种颜色来给待着色顶点（如图5所示）。所以任何一个非埃雷拉图类的构形，总共的交换次数是不小于2次，而不大于42次的。

实际上无环形链的构形只是有限转型的非埃雷拉图类构形中的一部分，我们对这部分构形的具体构形也进行了实际转型交换，其最大转型交换次数也是远小于42的。然而我们却已经构造出了转型交换次数为一个周期20次的，以及21次至26次的构形。而这些构形，都是含有经过构形围栏顶点的环形链的构形。这就再一次的说明了，有经过构形围栏顶点的环形链，只是构成无穷周期限循环转形的埃雷拉图类构形的必要条件，而并非是充分条件。没有经过构形围栏顶点的环形链，就构不成无穷周期循环转型的构形，而有了经过构形围栏顶点的环形链的构形，却不一定都是无穷周期循环转型的构形。
关于埃雷拉图转型交换的循环周期问题，敢峰先生研究得更多、更深入一些。上面的转型是关于两个同色的顶点的颜色与其对角顶点的颜色构成的对角链的交换的转型，其转型的循环周期是20。这个循环周期是由四种颜色，五个围栏顶点，四种颜色都可能处于构形的峰点位置的这三个数4，5，4的最小公倍数是20而得到的。所以就有了非埃雷拉图类构形对角链转型的最大交换次数是不大于42次的结论。
然而5—轮构形的两个同色顶点的颜色与其邻角顶点的颜色所构成的邻角链也是可以进行转型交换的。这种转型的循环周其则是60，是由四种颜色，五个围栏顶点，但只有三种颜色可能处于构形的峰点位置的这三个数4，5，3的最小公倍数是60而得到的。这一种转型中，两个同色顶点的颜色始终是B，且构形峰点的颜色也是总不会用到B的。所以也就有非埃雷拉图类构形邻角链转型的最大交换次数是不大于122次的结论。
从雷明和张彧典二人对含有双环交叉链的构形的分类中，可以看出：张先生的埃雷拉图类构形和非埃雷拉图类构形中含有经过构形围栏顶点的环形链的构形都是属于雷明的有环形链的构形。而雷明的无环形链的构形和有环形链的构形中除了埃雷拉图类构形外的构形都是属于张先生的非埃雷拉图类构形的构形。把二者综合起同来可以得到三类构形：埃雷拉图类构形，无环形链的构形，有环形链的非埃雷拉图类构形三类。埃雷拉图类构形用断链交换法或Z—换色程序解决，无环形链的构形用连续转型法交换法或连续的赫渥特颠倒法解决，有环形链的非埃雷拉构形则用以上两种方法都可以解决。
2、四色猜测的最终证明
只有有了这个对于非埃雷拉图类构形的转型交换次数的上界，才能说明任何非埃雷拉图类构形都是可4—着色的。如果没有这个上界，转型交换的最大次数就可认为是任意的，任意就有可能是无穷的。这样就不能说明任何非埃雷拉图类构形都是可4—着色的，因为可能有些非埃雷拉图类构形的转型是无法进行完的。
现在，有了这个上界，无论是从转型的次数角度把构形分为无穷周期循环转型的埃雷拉图类构形和有限转型的非埃雷拉图类构形两大类，还是从有无经过构形围栏顶点的环形链角度把构形分为有环形链的构形和无环形链的构形两大类，两种分类情况下的各种构形都是可4—着色的了。加上坎泊已证明了是可4—着色的无双环交叉链的构形，平面图所有的不可避免的构形就都是可4—着色的了。这也就证明了四色猜测是正确的。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，