证明地图四色猜测的新方法（修改稿）

雷明85639720

证明地图四色猜测的新方法（修改稿）
雷  明
（二○二○年五月八日）

四色问题也叫四色猜测。既然是猜测，就得进行理论上的证明。1852年英国的绘图员法朗西斯提出的地图四色猜测是：给任何一张地图的区域染色，使得有共同边界线的区域不用同一颜色，最多四种色就够用了。
1、极大平面图生成法证明四色猜测（纯理论法证明）
1、1  把一个地理问题转化成数学问题
地图是一个多分支（有公共无限面）并含有无顶环（国中之国的边界线）的无割边的3—正则的平面图，其对偶图是一个含有割点的且含有悬挂顶点的特殊极大平面图。给地图的面（区域）的染色就是对其对偶图——极大平面图的顶点着色。这就把一个地理学中的给地图的区域的染色问题转化成了数学中对极大平面图顶点的着色问题了。只要能证明极大平面图的四色猜测是正确的，地图的四色猜测也就是正确的了。同时，由于在相同顶点数的平面图中，以极大图的边数为最多，顶点间的相邻关系也最复杂，所以任何一个极大平面图经去顶或减边后，所得到的任意平面图的色数就只会比极大平面图的色数减少而不会再增大，所以任意平面图的四色猜测也就是正确的了。
1、2  证明过程
面数最少的地图是海地岛那样的地图，其中只有海地和多米尼加两个国家和一个海洋（即无限面）。它的对偶图是顶点数最少的极大平面图——K3图。在K3图的基础上，再给图中增加顶点和边，可以得到任意的极大平面图。图1和图2分别是在着有A、B、C三种颜色的K3图的面中增加顶点（如图中加大的顶点）和边得到的极大平面图和在K3图的边上增加顶点（也如图中加大的顶点）和边得到的极大平面图。所增加的顶点，在所用的四种颜色中，至少还是有一种颜色可着的。


在此基础上，若再在图中的某个三角形面内或边上增加顶点时，除了在边上增加4—度顶点外，其他情况都与图1和图2是相同的，只有在边上增加4—度顶点与图2，c有所不同（如图3，a）。此时增加的4—度顶点并不只是与同一个面中的顶点相邻，而是与两个面中的顶点相邻（如图3，a中的加粗边）。如果与所增加的顶点相邻的四个顶点占用完了四种颜色时（如图3，a），似乎该顶点没颜色可着了，因而不得不用第五种颜色，但事实上却并不是这样。
在与4—度顶点相邻的顶点占用完了四种颜色时，其两组对角顶点的颜色所构成的色链是不可能相互穿过的，所以最大只可能有一种对角色链在不经过待着色顶点（图中的加大顶点，即新增加的顶点）的情况下，是可以连通的，并与待着色顶点构成了一个圈（如图3,b中的加粗边），而另一种对角色链则一定是不连通的。这时就可以从不连通的那一组对角的任一个顶点开始交换该两个对角顶点的颜色所构成的色链，空出一种颜色来给待着色的新增加顶点（如图3，c）。在这里是从与待着色顶点（图中的加大顶点）相邻的D色顶点开始，交换与其对角的A色顶点构成A—D色链，把D色顶点变成了A色顶点，空出了D色给待着色顶点V的。坎泊早在1879年就已证明了4—度待着色顶点是一定可以着上图中已用过的四种颜色之一的。

就这样，在新生成的更新的极大平面图内，进一步的增加顶点和边，只要保持图仍然是极大平面图的情况下，一定就可以生成任意顶点数的、各顶点的度也是任意多的各种极大平面图。所增加的顶点一定都是可以着上图中已用过的四种颜色的。这就从理论上证明了任何极大平面图也都是可4—着色的，则任意极大平面图的四色猜测就是正确的。
2、不可免构形可约法证明四色猜测（着色实践法证明）
2、1  把一个无穷问题转化成有穷问题来处理
任何一个极大平面图的着色也都是一个顶点一个顶点的着色的，也都一定会遇到要对最后一个顶点进行着色，并与该顶点所相邻的顶点都已全部着色的情况。把这样的还有一个顶点未着色的图就叫做“构形”。极大平面图有无穷多种，每个极大平面图中的顶点数也可以是有无穷多个的，每个极大平面图中的每一个顶点的度也是任意的，也可以说是可以多到无穷大的。这就从极大平面图的个数，每个极大图中的顶点数，以及每个顶点的度数三方面看，四色问题都是一个无穷的问题。但在图论中却有定理可以证明，任何一个平面图（当然也就包括极大平面图在内）中都一定含有至少一个顶点的度是小于等于5的，这就为把无穷问题转化成有穷问题创造了条件。
在着色时，我们总可以想办法把最后一个待着色的顶点安排在度是小于等于5的顶点之上。那么只要证明顶点度是小于等于5的五种构形是否可约（即是否可4—着色），就可以解决四色猜测的证明问题了。这五种构形就是极大平面图的不可避免构形，由这五种构形就构成了平面图的“不可避免构形集”，简称“不可免集”。这就可以把一个无穷的问题转化成一个有穷的问题来处理了。
由于极大平面图中的任何构形的“待着色顶点”都是处在一个轮形图的中心顶点位置的，所以这种构形也叫“轮构形”，并把与待着色顶点直接相邻的顶点叫做“围栏顶点”。轮构形中除了待着色顶点外的其他顶点都是用四种颜色已经着了色并符合着色要求的图。解决构形的可约性问题就是解决如何把待着色顶点着上图中已用过的四种颜色之一的问题。
1879年坎泊已经证明了任何无双环交叉链的构形都是可约的，但却把含有双环交叉链的构形漏掉了。在1890年时，赫渥特指出了坎泊证明中的这一漏洞。所以，现在只要能证明含有双环交叉链的构形是可约的，四色问题也就解决了。人们习惯上把坎泊证明过的已经是可约的构形叫做K—构形，而把赫渥特发现的、具有双环交叉链的构形叫做H—构形。
2、2  含有双环交叉链的构形

图4和图5分别是含有双环交叉链A—C和A—D的H—构形，因为A—C链和A—D链分别与待着色顶点V构成了一个圈（环），并且A—C链和A—D链不但有共同的起始顶点1A，中途又有相交叉的顶点8A，所以叫做“双环交叉链”。

具有双环交叉链的构形只可能出现在5—轮构形中，其他的轮构形中是不可能出现双环交叉链的，所以说，4—轮以下的构形，实际上坎泊早就在1879年已经证明都是可约的了。具有双环交叉链的构形的共同特点是，A—C链和A—D链都是连通的，不能交换，也都空不出A、C、D三色之一给待着色顶点。虽然图4和图5中的各图中都含有双环交叉链，但图4，a，图4，c和图4，d三个图却都可以从围栏顶点中连续的移去两个同色B，给待着色顶点着上；而图4，b和图5中的4个图却都不能移去两个同色B。看来含有双环交叉链也只是构成H—构形的必要条件而不是充分条件。没有它，就不可能构成H—构形；但有了它，却未必全都是H—构形。
为什么同样都含有双环交叉链，有的能连续的移去两个同色B，而有的却不能呢？关键的是从任意一个B色的围栏顶点交换了与其对角顶点的颜色构成的色链后，是不是都能从另一个B色的围栏顶点新生成到其对角顶点的连通的对角链。只要有一个不能生成者，就可以连续的移去两个同色B，就是可约的K—构形，否则就是H—构形。图4，a，图4，c和图4，d三个图都具有这种性质，所以是K—构形；而其他图都没有这种性质，所以是H—构形。
BAB型的H—构形一定是含有双环交叉链A—C和A—D的，其交叉顶点也一定是着A色的。那么两链的交叉顶点（A色）的前后一定都是C色和D色的顶点（如图4和图5中与顶点8A所相邻的顶点），与顶点8A相关联的面至少有两个是共用了一个顶点8A的、由A、C、D三色构成的对顶的三角形面。这样，8A、6C和7D三顶点间的边则一定都是单边，该三个顶点构成的是一个面。如果在该面的那一条边上（特别是在6C—7D边上）再增加顶点，图就不再是H—构形了。
既然顶点8A、6C和7D构成的是一个面，那么在图的外部无限面内再增加任何顶点都一定是可以着上图中已用过的四种颜色之一的。加上图4和图5中的各图都是极大平面图，在其中的任何一个内部面内增加顶点，也都是可以着上图中已用过的四种颜色之一的，绝不会影响到图中其他顶点的颜色。所以只要以上图4和图5中的构形都是可约的，其他任何构形中只要含有以上的图4和图5作为分子图或分子构形，也一定都是可约的，解决的办法也都是相同的。这一观点可能就是张彧典先生所说的“构形最小”、“解法相同”的原理吧。
2、3  证明
2、3、1  H—构形的分类：
既然双环交叉链是构成H—构形的必要条件，那么只要想办法破坏了双环交叉链，图就应是可约的K—构形了。从图中可以看出，双环交叉链的关键顶点是1A、8A和4D、5C，只要这四个顶点的颜色发生了改变，双环交叉链也就不存在了，图也就转化成了无双环交叉链的、可约的K—构形了。所以无论是从顶点1A或8A交换A—B链，或是从4D或5C交换C—D链，都可以使双环交叉的A—C链和A—D链中的两条或一条断开，图中也就不存在双环交叉链了。这样的交换方法叫做“断链交换法”。
为了防止交换A—B链（或C—D链）时，图中的所有着A色和B色的顶点（或所有着C色和D色的顶点）的颜色都发生改变，使交换变得没有意义或失去作用，必须在有环形的A—B链时，才可交换C—D链，而在有环形的C—D链时，才可交换A—B链。为此，可把含有双环交叉链的构形分为有环形链的构形（如图4，b、图5，a、图5，b）和无环形链的构形（如图5，c和图5，d）。有环形链的构形用断链交换法解决，即可转化成无双环交叉链的构形（如图6。图６，b中似乎仍有双环交叉链，但这时的A—C和A—D两链却并没有真正意义上的“十”字交叉，不属于双环交叉链），而无环形链的构形则需要再转化成有环形链的构形后再进行解决。
图6，a中含有经过了1B、2A、3B三个围栏顶点的环形的A—B链，交换该环内、外的任一条C—D链，都可以解决问题。1921年埃雷拉构造的E—图就属于这一类，就可以这样来解决；图6，c中含有经过了4D和5C两个围栏顶点的环形的C—D链，交换该环内、外的任一条A—B链，也都可以解决问题。1890年赫渥特构造的H—图就属于这一类，也就可以这样来解决。但是1935年欧文构造的两个轴对称的图，虽然也都含有双环交叉链，但其却都不是H—构形，而是可以连续的移去两个同色B的可约的K—构形；而在欧文构造的图中，只有另外一个不对称的图才是一个无环形链的H—构形。这个图也许就是最早出现的无环形链的H—构形，因为它比张彧典先生2010年构造的第八构形（也是一个无环形链的H—构形）要早65年。

以上对H—构形的分类是从如何使双环交叉链“断链”的角度出发进行分析的，也还可以从各链能否进行交换的角度进行分析。四种颜色可能构成的六种色链中，已有A—C链，A—D链不能交换，空不出颜色A、C和D，B—C链和B—D链也不能进行连续的交换，也空不出两个同色B。现在只有再考虑A—B链和C—D链两种链是否可以交换了。这两种链正好是一对相反链，不能相互穿过。同样的，为了防止交换A—B链（或C—D链）时，图中的所有着A色和B色的顶点（或所有着C色和D色的顶点）的颜色都发生改变，使交换变得没有意义或失去作用，也必须在有环形的A—B链时，才可交换C—D链，而在有环形的C—D链时，才可交换A—B链。从这个意义上说，也应把H—构形分为有环形链的构形和无环形链的构形两类。
从两个不同的角度的分类结果看，都是相同的，说明这种分类是正确的，是完备的。对于有环形链的构形的解决，用断链交换法是完全可以的。现在就集中力量研究，如何把无环形链的构形转化成有环形链的构形或直接转化成可约的K—构形了。
2、3、2  无环形链的构形的可约性：
图5中的c和d两个构形只是左右分布上的不同，实际上都是无环形链的构形，所以只研究图5，c的可约性就可以了。
（1）把图5，c中的顶点9A改成9D时，图就转化成了有环形链C—D的构形了（如图7，b）；把图5，c中的顶点10C改成10A时，图也就转化成了有环形链A—B的构形了（如图7，d）。但构形峰点的位置和颜色都没有发生变化。但这一方法并不是对所有无环形链的H—构形都适用，而只对部分图适用，还有一部分图是不适用的。
（2）在图5，c（即图8，a）中，从顶点1B开始交换B—D链，图就转化成DCD型的、可以连续的移去两个同色D的可约的K—构形了。再进行两次坎泊的空出颜色的交换，即可空出D给待着色顶点V着上（如图8）。

（3）在图5，c（即图8，a）中从顶点3B开始交换B—C链，图就转化成了含有经过了两个围栏顶点的A—B环形链的构形了（如图9，a。但这时构形峰点的位置和颜色却都发生了变化，由BAB型的构形转化成了CDC型的构形了），可以按有环形链的构形用断链交换法进行处理了。若再继续进行第二次转型，图就会变成一个可以连续的移去两个同色A的可约的K—构形（如图9，b），再进行两次坎泊的空出颜色的交换，就可以空出颜色A来给待着色顶点（如图9的c和d）。
这里的（2）、（3）两种方法对于所有的无环形链的构形都是适用的，在后面还有证明。
把以上的各种方法用在欧文1935年构造的无环形链的图和张彧典先生2010年构造的第八构形（也是一个无环形链的构形）上进行验证，（2）和（3）都是正确的，而（1）只适用于张先生构造的图，却不适用于欧文构造的图，说明它并不是适用于所有无环形链的H—构形的。

（4）以上的构形都是A—B链和C—D链均是只有一条的情况，如果两链均不只是一条，而是有互不连通的多条情况时，将怎么办呢？张彧典先生的第八构形的放大图就是这种情况的反映。同一种链只要是有几条互不连通的几部分时，图中就一定是含有与其呈相反色链的环形链部分存在，交换该链环形部分内、外的任何一条相反的色链，都可使双环交叉链的一条或两条遭到破坏，即断开，使构形转化成可约的K—构形。

从张先生的第八构形的放大图的解决中，可以看出，这里所交换任一部分的A—B链或C—D链，实际上也是在进行着切断双环交叉链的断链交换。所以说，“经过了构形围栏顶点的环形链”，并不一定都是要环形部分经过了围栏顶点的，而只要是与环形部分相连通的相同色链的直线部分经过了围栏顶点，都可以认为是含有经过了围栏顶点的环形链的构形。这就使我们在处理H—构形时的方法更加灵活。还可以看出，环形链并不是一定要使环形部分通过围栏顶点，而只要是与环形链连通的直链部分通过了围栏顶点，都可以视为是含有经过了围栏顶点的环形链的构形，都可以使用断链交换法解决问题。
（5）到此就证明了所有的无环形链的H—构形一定都是可以转化成有环形链的构形的。前面已经证明了有环形链的H—构形用断链交换的方法是可以解决问题的，所以任何H—构形就都是可约的了。也就不需要对无环形链的H—构形的最大转换次数是多少进行专门的证明了。
2、3、3  无环形链的H—构形一定可转化成有环形链的构形和可直接转化成可约的K—构形的证明：
（1）可转化成有环形链的构形和直接转化成K—构形的证明
图10，a是一个无环形链的构形。

若能把图10，a中的顶点6C变成6B，则图就成了一个CDC型的、含有经过了两个围栏顶点的A—B环形链的有环形链的H—构形了。若对图10，a从顶点3B交换B—C链，顶点6C就变成了6B，可以达到目的，图也就转化成了一个有环形链的H—构形了（如图10，b）。这就是前面的图9，a。该图既可以按有环形链的构形进行处理，也可以继续的进行转型，变成可以连续的移去两个同色的可约的K—构形。
当对图10，a从顶点1B交换B—D链（如图10，c），得到一个DCD型的有双环交叉链的构形，C—A链和C—B链的交叉顶点是6C，从4D到6C有一条C—D道路，当继续按同一方向进行转型，从4D交换A—D链后，就生成了从4A到2A的连通的A—C链，阻断了从1D到3B的D—B连通链的生成，图就一定是一个可约的K—构形了。这就是前面的图8。
以上的证明是对所有的无环形链的H—构形都是适用的。
（2）对改变某链中的某个顶点的颜色，直接转化成有环形链的构形的证明

图11，a是两条互相不能穿过的一对相反链A—B和C—D。在C—D链中一定能找到一个顶点C或D，把其颜色改变成A或B后，A—B链就可以闭合成为环形的，而C—D链则被环形的A—B链分隔为互不连通的环内、环外两部分（如图11，b）。构形也就由原来的无环形链的构形，转化为有环形链的构形了。当然，用同样的办法也可以使构形转化成有环形链C—D的构形的。前面的图7就是利用这样的原理进行转化的。
同样的，象张彧典先生的第八构形的放大图一样，虽是无环形链的构形，但A—B链和C—D链各又都不至只有一条，那么交换其中的任一条A—B链或C—D链，都可以使双环交叉链的一条链或两条链断开，构形也就直接转化成可约的K—构形了。如同直接解决有环形链的构形一样。
3、四色猜测是正确的
现在我们已经用不同的两种方法——极大平面图生成的纯理论方法和平面图不可免构形的可约法对极大平面图的四色猜测进行了证明，都得到了极大平面图的四色猜测是正确的的结论，所以地图的四色猜测和平面图的四色猜测也都是正确的。

雷  明
二○二○年五月八日于长安

注：此文的初稿《证明地图四色问题的新思路》已于二○二○年五月四日在《中国博士网》上发表过，网址是：本修改稿《证明地图四色猜测的新方法》也于二○二○年五月十一日在《中国博士网》止发表过，网址是：

雷明85639720

,,,,,,,,,,

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

,,,,,,,,,,