地图四色问题的证明

雷  明

（二○二○年四月十一日）

1、极大图边生成、边着色的纯理论证明：

1、1  的地理学上的问题转化成一个数学问题：

地图是一个含有“国中之国”（这种国家只有一条孤立的环形边界线，其上没有任何顶点，更没有“三界点”，如位于南非境内的莱索托和大洋中的岛国等）的3—正则平面图（即每个顶点都连有3条边，其度是3，也叫“三界点”），地图的对偶图则是一个含有悬掛顶点的各个面都是3边形面的极大平面图。给地图中的区域（面）的染色就相当于给其对偶图的顶点着色。四色问题是由给地图的区域（面）的染色而提出，解决问题还得从其对偶图——极大平面图的顶点着色入手。在相同顶点数的平面图中，以极大图的边数是最多的，顶点间的相邻关系也是最复杂的。对极大图通过“去顶”和“减边”而得到的任意平面图的色数，只会比极大图的色数减少而不会再增大。所以，极大平面图的四色问题解决了，地图的四色问题和任意平面图的四色问题也就都得到了解决。这就把一个地理学中的问题转化成了一个数学问题了。

1、2  证明过程：

面（区域）数最少的地图是海地岛的地图，其上有海地和多米尼加两个国家和“海洋国”，共有三个面和两个3—度顶点。其对偶图就是只有三个2—度顶点的极大平面图，这也是最小的极大平面图。这个最小的极大平面图就是K₃图。用“增加顶点和边”的办法从K₃图可以生成任意顶点数的、且各顶点的度也是任意多的极大平面图。这些极大平面图一定都是可4—着色的。证明如下：

任意极大平面图的生成过程，是从顶点数是3的最小极大平面图K₃开始的，因为K₃图只有3个顶点，所以三种颜色就够用了。

（1）若在K₃图中增加一个1—度顶点（在顶点上），2—度顶点（在边上），3—度顶点（在面内），再增加边，保持图仍是极大平面图的情况下，这三种顶点至少各还是有一种颜色可着的（如图1中的加大顶点及其可能着上的颜色）。若在K₃图中增加一个4—度顶点（在边上），再增加边，保持图仍是极大平面图的情况下，这个顶点还是有一种颜色可着的（如图2中的加大顶点）。图2似乎不象是极大图，但稍加拓扑变形后就是很清楚是极大图了（如图3）

（2）以后再在顶点数大于4的极大图中增加顶点时，1—度顶点，2—度顶点，3—度顶点仍都是有颜色可着的，只有增加的4—度顶点时，有时可能会与着了四种颜色的顶点相邻。但这种情况，坎泊早在1879年已经证明了4—轮构形一定是可约的（可4—着色的）。其原理是：

必须从4轮的四个轮沿顶点（即围栏顶点）中空出一种颜色来。由A、B、C、D四种颜色所构成的一对相反色链A—B和C—D一定是不会相交的，两种链在围栏顶点以外，最大只可能有一条是连通的，另一条一定不连通。这样就可以从另一条链位于围栏上的一个顶点起交换该链，一定可以把该顶点原来所着的颜色空出来给待着色顶点（这里就是新增加的顶点）着上。

（3）给图4的有4个顶点（K₄图）以上的极大平面图的边上增加一个顶点的情况如图5。在B—D边上增加一个顶点1，其相邻顶点已点用完了四种颜色，但对于顶点1来说，其围栏顶点的B—D色链并不连通（如图5），从B色顶点起交换B—D色链，使B色顶点变成D色，就空出了B色给待着色的顶点1（如图6）；对于增加在A—C边上的顶点2来说，其围栏顶点只用了A、C、D三种颜色，还有一种B色可以给其着上（如图6）。

（4）就这样一直不停的把图的顶点增加下去，边增加顶点、边着色，就可得到任意顶点数的、且各顶点的度也是任意多的（如图1中的顶点A的度就是6）任意的极大平面图，其所用的颜色总数总是不会超过4种的。这就证明了任何极大的平面图都一定是可4—着色的。四色猜测是正确的。证毕。

这样的在极大平面图内增加顶点的方法，是不会出现所增加顶点的度是大于4的情况的。

2、不可免构形可约法的着色实践证明：

前一方法是在极大图生成的过程中用边生成、边着色的方法，只要停止了继续生成，图的可4—着色就已经完成。下面要谈的不可免构形可约法证明，则是先给出具体的极大平面图，然后再给其进行着色的证明方法。

2、1  把无穷的问题转化成一个有穷的问题来处理：

着色时一定是会遇到最后一个顶点未着色的情况，把这种还有一个顶点未着色的图就叫做“构形”。因为任何平面图中一定存在至少一个顶点的度是小于等于5，在对任何极大平面图着色时，一定是可以把最后一个未着色的顶点放在度小于等于5的顶点上。所以研究四色问题时，就可以只研究待着色顶点的度是小于等于5的有限的六种构形就可以了。这五种构形就是平面图的“不可避免构形”，简称“不可免构形”。这就可以把一个看似无穷的问题转化成了一个有穷的问题来解决了。

2、2  证明过程：

（1）当构形的待着色顶点的度是小于等于3，或者与待着色顶点直接相邻的围栏顶点所占用的颜色数小于等于3时，待着色顶点至少还是有一种颜色是可着的。当构形的围栏顶点已占用完了四种颜色时，坎泊早在1879年已证明了不含“双环交叉链”的构形都是可约的（可以叫做K—构形）；但却遗漏了对一种含有“双环交叉链”的构形是否可约进行证明。现在证明四色猜测，主要就是要证明具有双环交叉链的构形是否可约的问题。把具有双环交叉链的构形叫做H—构形，是因为它是赫渥特首先发现（构造）的。

（2）具有双环交叉链，只是构成H—构形的必要条件，而不是充分条件。因为有些图虽具有双环交叉链，但却并不是H—构形，因为这些构形可以直接通过坎泊交换，从围栏顶点中空出一种颜色给待着色顶点。如图7，图8，图9三个图就不是H—构形，而是可以连续的移去两个同色B的可约的K—构形；只有图10才是H—构形，因为这个图从围栏顶点中不可能直接空出任何一种颜色给待着色顶点。这四个图中的加粗边就是双环交叉链A—C和A—D。

（3）从图10中可以看出，只有不能直接空出任何一种颜色给待着色顶点的图才是H—构形。具有图10一样特征的图，又可分为以下图11和图12的“有环形链的构形”和图13（或图14）的“无环形链的构形”两种类型。现在证明四色猜测，就是要解决这两种不可免的H—构形的可约性的问题。

（4） 对于图11和图12的有经过了构形围栏顶点的环形链的构形，交换经过构形的围栏顶点的与环形链呈相反色链的链，就可以使双环交叉的A—C链和A—D链断开，破坏了构成H—构形的必要条件，使图成为无双环交叉链的可约的K—构形。图11可以交换环形链A—B环内、外的任一条C—D链（埃雷拉图就是这样解决的）。图12可以交换环形链C—D环内、外的任一条A—B链（赫渥特图就是这样解决的）。有的环形链虽不经过构形的围栏顶点，但只要该环形链内、外的相反色链经过了双环交叉链，也一定是可以达到破坏双环交叉链的目的的。这里也就不再画图了，爱好者朋友，可以自已画一画。

（5）对于图13（或图14）的无环形链的构形，由于A—B链和C—D链均是直链，不能交换（就是交换了也空不出颜色来），所以只能先交换一个同色顶点B与其对角顶点所构形的色链，先移去一个同色B，使构形转型（即使构形峰点的位置和颜色都发生变化）的转型交换，再看转型后的构形是什么样的构形，再作新的打算。

通过对各种各样的无环形链的构形的转形交换，可以发现：

  有些构形可以只转型交换一次就可以转化成含有经过了两个围栏顶点的环形链的新构形。如张彧典先生的第八构形就是这样。

  有些构形可以只交换一次就可以转化成可以连续的移去两个同色B的构形。张先生的第八构形也是这样的。

  我们在进行转型交换时，如果遇到交换了一条关于两个同色的色链后，不能生成从另一个同色顶点到其对角顶点的连通链时，本来就可以解决问题，但我们却人为的去构造出这样的连通链，以保证图仍然是无环形链的含有双环交叉链的H—构形的情况下，最多不超过5次转型交换，图就可以转化成含有经过了两个围栏顶点的环形链的H—构形，或者可以连续的移去两个同色的可约的K—构形（在第6次转型时，就不可能再人为的构造出从另一个同色顶点到其对角顶点的连通链了）。

  我们对张彧先生的15种Z—构形都进行了转型交换，已经证明了上述这一结论是正确的：这15种Z—构形也都是在不大于5次的转型交换时，图就转化成了一个有环形链的H—构形，或是转化成了一个可以连续的移去两个同色的可约的K—构形了。所谓的需要转型交换20次以上的构形，其本身就是有环形链的构形，就不需要用转型交换来处理。

  至于为什么不会超过5次转型交换，我认为是因为这种构形的围栏顶点共有5个，每一个围栏顶点各作一次峰点时，正好需要转型交换5次。转型交换的次数达到5次，图仍然还是无环形链的H—构形的这一情况，这是不可能出现的。我的这种解释虽然有点免强，但转型交换的实践，的确说明了不超过5次转型交换，无环形链的H—构形就可以转化成有环形链的H—构形或可以连续的移去两个同色的可约的K—构形却是肯定的。

  还有些无环形链的构形，在改换了A—B链或C—D链某条链上的某个顶点后，图就可以直接转化成有C—D环形链或A—B环形链的有环形链的构形。张先生的第八构形就可以这样来处理。

  还有些构形中的A—B链和C—D链不只是一条，而是多个不连通的部分，其上又含有双环交叉链上的顶点，交换这种链的某一部分，也是可以使构形直接转化成可约的K—构形的。张彧典先生的第八构形的放大图就可以这样来处理。

3、四色猜出测是正确的：

通过研究，我们还得出：无论是有环形链的H—构形，还是无环形链的H—构形，也不管构形是极大图还是非极大图，都是有多种方法使其可约的。构形本身不但可以作为一个单独的图，是可约的；而且把构形本身作为一个分子图（分子构形），嵌入到某个极大图的一个面内，构成一个极大的或非极大的平面图时，也一定都是可约的。

至此，已证明了各种情况下的不可免的H—构形已都是可约的，再加上坎泊已证明是可约的K—构形，平面图的所有不可免构形就都是可约的了。四色猜测也就是正确的了。

雷  明

二○二○年四月十一日于长安

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

http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=4210&show=0