四色猜测的证明历程

雷明85639720

四色猜测的证明历程
雷  明
（二○二三年十二月四日）

1，四色猜测是1852年由英国的绘图员法郎西斯提出来的。1879年坎泊给出了第一个证明。虽然提出了不可避免构形的概念，但对各不可避免构形的分类还没有做到很细致，也没有把不可免的构形分析构造完全，以致遗漏了一整类的H—构形没有对其进行可约性的研究。
1890年赫渥特构造了赫渥特图（H—图），就属于坎泊证明中遗漏了的H—构形。1921年埃雷拉也构造了埃雷拉图（E—图），也属于H—构形一类。虽是一类，但E—图与H—图还也有不同之处。
E—图与H—图虽然都含有经过了关键顶点的环形链，但所经过的关链顶点和色链均不相同。这又可把H—构形分成了两类。即有环形链的H—构形和无环形链的H—构形。H—图和E—图均属于有环形链的H—构形。
有了含有环形链的H—构形，就应有不含有环形链的H—构形。这种有无环形链的H—构形的概念，是在近年来研究E—图构形与H—图构形的可约性时，由雷明提出来的，并构造出了无环形链的H—构形的标准模式。
2，1880年泰特又根据“每一个平面三次图都含有哈密圈”的错误猜想，给出了四色猜测的第二个有漏洞的证明。但在1946年塔特构造了不含有哈密顿圈的平面三次图后，才发现泰特的证明实际上也只是研究了有哈密顿圈的平面三次图是可约的，而遗漏了对不含有哈密顿圈的平面三次图的可约性的研究。
3，自从1890年H—构形被发现后，至1990年的一百年间，其可约性的研究一直进展缓慢。四十五年后的1935年，欧文用了一种交换的办法（欧文叫做“正切链” 交换），交换了双环交叉链的两个末端顶点的颜色，解决了E—图的可约性问题，但没有引起大家的重视。这种正切链法与我们目前解决有环形链的H—构形所用的断链法（张彧典叫做Z—换色程序）实质上是相同的。但欧文的证明却很难懂，也没有指出为什么要这么做，更没有提出有无环形链的概念。直到再过了半个多世纪后的1990年以后，研究H—构形的人才多起来了。
首先是在1988年出版的《图论的例和反例》一书中，作者（美国人）在书中说，从H—图的围栏顶点中只能移去一个同色，而不能移去两个同色。他虽然看到了不能连续的移去两个同色这一关键向题，但却没有看到造成这一问题的根本原因是因为图中有两条链是由同一起始顶点开始的双环交叉链。更没有看到图中有一条经过了双环交叉链的两个末端顶点的环形链，也没有提出解决H—图可约性的办法。
4，1990年后就有我国的敢峰，张彧典，雷明，董德周，张忠输，许寿椿的团队等，以及英国的米勒和美国的瓦贡等，都分别对H—图和E—图这两个含有经过了关键顶点的环形链的H—构形进行了研究，并分别都取得了一定的好结果，也都说明了H—图和E—图都是可4—着色的。
4，1  米勒的团队用赫渥特颠倒法（即连续的从构形峰点同一侧的一个同色顶点起进行对角链的交换。张彧典叫做H—换色程序，我叫做转型交换），两次颠倒后，H—图就转化成了可约的K—构形。并在英国牛津大学《数学季刊》上发表了题为《理应已知的赫伍德范例》的论文。但正当他们兴高采烈的企图用此办法彻底解决四色问题时，却就遇到了E—图（他的E—图是怎么来的，从那里得来的，不清楚），使用赫渥特颠倒的结果出现了无穷的周期循环。即就是用了无限次颠倒也不能解决问题。于是他们就没有再继续研究别的方法，而放弃了最初企图想彻底解决四色问题的想法。
4，2  我国的敢峰从最基础的双环交叉链开始，用自己创造的“可控换色程序”，经过20步换色，构造了与埃雷拉E—图完全相同的自称为是所谓的“终极图”。敢峰本人虽然看到了该图是一个无穷周期循环可控换色的构形，换色次数再多，也是解决不了问题的。但敢峰却又发现了该图中有经过了双环交叉链共同起始顶点的环形链，交换了环形链内外的任一条与环形链呈相反色链的链后，H—构形就转化成了可约的K—构形。敢峰分别在1994年和2011年出版了《证明四色定理的新数学》和《4CC和1十1的证明》两本书。但他却没有发现这一交换，图中的双环交叉链就断开了的这一亊实。这种方法张彧典叫Z—换色程序，我叫断链法，敢峰也没有给其起名，并且也没有对H—图进行可约性的研究（可能他当时还未见到过赫渥特的H—图）。
4，3  张彧典对H—图和E—图的研究基本是在2000年以后的亊了。基本的研究方法是与米勒和敢峰的方法分别相同的。张彧典的H—图和E—图都是来源于1999年米勒所寄信件中的米勒的论文《理应已知的赫伍德范例》，并在2003年把E—图构形归并于他的八大不可避免构形集中，成为九大构形集了。这些内容在其2010年出版的《四色问题探密》一书中都有祥细的说明。
4，4  许寿椿团队用现代化手段——电子计算机也给出了H—图的多个4—着色的模式，在其于2008年出版的《图说四色问题》一书中就谈到这一问题。
4，5  董德周和张忠输对H—图的研究，分别都指出了以前只所以认为H—图用坎泊链法只能移去一个同色，而不能连续的移去两个同色，是因为在第二次使用坎泊链法时，交换的是一条连通链，当然是不能移去第二个同色的。产生这样的结果完全是因为含有双环交叉链而造成的。张忠输还在《自然杂志》第14卷第5期上发表了题为《数学的陷阱》的论文。
4，6  雷明对H—构形的研究
a，雷明在1990年前后研究H—图的可约性时（H—图来源于1988年出版的《图论的例和反例》一书），他不仅看到了图中有双环交叉链，也看到了其中还有经过了双环交叉链两个末端顶点（关键顶点）的环形链，对环形链内外的任一条与环形链呈相反色链的链进行交换后，构形就转化成了可约的K—构形，问题就得到解决。赫渥特图是可—4着色的这一成果，雷明本人1992年曾在陕西省数学会的年会上作过题为《赫渥特图的4—着色》的学术论文报告，首次向数学界宣布了自已取得了赫渥特图可进行4—着色的成果。得到了与会的专家学者们的好评。
b，雷明开始研究E—图的可约性问题已是2010年以后的亊了。当从张彧典2010年出的书中看到了E—图后，一眼就看到图中有双环交叉链，也不能连续的移去两个同色，是一个H—构形。更关键的是图中还有一条经过了构形峰点（关键顶点）的环形链。1992年有了对H—图4—着色的经验，雷明立即就认为，在环形链内外，任交换一条与环形链相反的色链，就可以解决问题。果真如此，E—图也是可4—着色的。雷明把这种处理的办法叫断链法（也就是张彧典的Z—换色程序），因为这样处理后，原有的双环交叉链就不存在了。
c，在H—图与E—图可4—着色的基础上，雷明对H—构形再进行了细分，首次把H—构形再细分为有环形链的H—构形和无环形链的H—构形。并构造了无环形链的H—构形的标准模式。有环形链时用断链法处理，无环形链时用转型法（即H—换色程序，也即张彧典的所谓“难点转化”）进行处理（理由是既然H—构形不能连续的移去两个同色，就先移去一个同色，使构形进行转型，再看转型后的结果是否可约），可以证明，这种构形一定是可以在有限的40次转型之内，使构形转化成可约的K—构形或有环形链的H—构形的（证明略）。
d，当然还可以再进行细分，有环形链的构形还可分为经过了双环交叉链的两个末端顶点的环形链和经过了双环交叉链的共同起始顶点或交叉顶点的环形链。虽然都可用转型法进行处理，但前者交换的是经过了两链的共同起始顶点或交叉顶点的链，后者交换的却是经过了两链的两个末端顶点的链。雷明在2018年出版的《四色猜测的手工证明》一书中就有解决各种H—构形的方法的论述。
4，7  瓦贡研究E—图构形主要体现在他1998年发表的《肯普再研究》的论文中，该论文主要是解读欧文1935年用正切链法解决E—图着色的方法问题的。瓦贡也认为E—图构形是不能用坎泊链法从围栏顶点中空出颜色的，但他还想用移去两个同色来试一试。我想这可能就是瓦贡把他的论文题目叫做《肯普再研究》的原因吧。瓦贡认为移去两个同色就意味着最后要把两个同色的颜色给待着色顶点着上，两个同色的顶点就必然成为两个新的待着色顶点。若要使这两个待着色顶点着上与其对角顶点相同的颜色，就必须使新待着色顶点的围栏顶点由5点4色分别都变成5点3色。而正好在交换了正切链（即双环交叉链的两个末端顶点构成的链）的颜色后，两个新待着色顶点的围栏顶点也就分别变成了5点3色。分别把两个待着色顶点着上各自对角顶点的颜色，问题就解决了。我认为这个解释还是比较合理的。这种解释方法与敢峰先生给他的“终极图”（实际上就是E—图）进行的强行着色中，强行的先给待着色顶点着两个同色顶点所用的颜色的方法是相同的。强行着色法也可叫待着色顶点移动着色法。
5，现在坎泊证明中的漏洞都已经补上了，平面图的四色猜测也就证明是正确的了。
6，自从1946年塔特发现含有无哈密顿圈的平面三次图存在后，沿着泰特的方法去力图解决四色问题的至今无见他人。最近我对泰特的证明思路进行了研究，现提出仿泰特的方法对四色猜测进行证明如下。
6，1  泰特的猜想是“平面三次图（即3—正则图）的可3—边着色等价于其可4—面着色”。既然泰特的证明依据的是“每一个平面三次图都含有哈密顿圈”的错误猜想，就说明泰特在他的猜想中所说的平面三次图就都是指有哈密顿圈的平面三次图。我们现在就可以看一下有哈密顿圈的平面三次图是否都是可3—边着色的。由于平面三次图的顶点数一定是偶数，所以有哈密顿圈的平面三次图中的任何一个哈密顿圈在边着色时都一定是一个可用两种颜色着色的边二色圈（偶圈）。哈密顿圈上的边用去了两种颜色，而不在哈密顿圈上的其他边也都是不相邻的单边，着上相同的第三种颜色完全是可以的。这时，图中就只有三种颜色的边，每一个顶点都各连有三种颜色的边各一条。这就证明了有哈密顿圈的平面三次图都是可3—边着色的。这个结论是否也可推广到任何平面三次图呢？请继续向后看6，3节。
6，2  在用了三种颜色进行边着色的图中，由两种颜色的边构成的面（边数≥2的偶数边面）只可能有三种，而由三种颜色的边构成的面（边数≥3的面）只可能有一种，共计最大可能只是四种面。每种面用一种颜色，就只有四种颜色的面。这就证明了可3—边着色的有哈密顿圈的平面三次图都是可4—面着色的。泰特猜测也是正确的。即可3—边着色的且有哈密顿圈的平面三次图是等价于其可4—面着色的。
6，3  现在来看看无哈密顿圈的平面三次图是否也是可3—边着色的。虽然图中仍有偶数个顶点，但却不可能有经过了所有顶点的边二色圈（因力图中无哈密顿圈），也不可能简单的把未着色的边都着成相同的第三种颜色。只得与有哈密顿圈的平面三次图一同归并在一起，用判别任何图边着色色数的办法进行判断。任何图的边着色色数一定都等于其最大度△（最大度△即图中顶点最多所连结的边数），而平面三次图各顶点的度不但均是3而且也都是最大度△，所以任何平面三次图，不管其中有没有哈密顿圈，其边着色的色数也都是3。这就证明了任何平面三次图的边着色色数一定都是3。根据6，2中已证明是正确的泰特猜测，任何可3—边着色的平面三次图也都是可4—面着色的。
6，4  由于地图本身就是一个平面三次图，所以任何地图不但都是可3—边着色的，而且也都是可4—面着色的。地图四色猜测是正确的。
6，5  现在再逆向证明一下泰特猜测。若有一个可4—面着色的平面三次图，四种颜色的面两两相邻所得到的边共有六种。这六种边还可分成三对，每对中的两种边都是互斥边，即形成这两种边的面的颜色各不相同。互斥边是不可能相邻的，边着色时用同一种颜色是完全可以的。这时图中就只有三种颜色的边了，每个顶点所连结的三条边各占用一种颜色。这就从逆向方向也证明了泰特猜测是正确的。
7，四色猜测是正确的。

雷  明
二○二三年十二月四日于长安