图解四色定理

图解四色定理

一、概述

1852年，伦敦大学毕业的格斯里在一家科研单位从事制图工作时，提出四色猜想：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同颜色”。

1976年，数学家凯尼斯.阿佩尔和沃夫冈.哈肯设计出“放电法”程式、借助计算机运行1200小时验证，首次证明四色定理。但图论爱好者认为依赖计算机的证明过程不够完美，相信一定存在某种不依赖计算机的证明方法。

本文在各种已知定理基础上，论述一种简洁的、无需借助计算机运算的四色定理证明过程。

四色定理的论证历史及衍生命题，可参考维基百科或百度百科。

二、关键概念

1) 正规地图

正规地图是指：没有一个国家包围其他国家，或没有三个以上国家相遇于一点的地图为正规地图(维基百科中称为三度图)。

如上图所示，国家数量相同，在地图上的位置也相同的情况下，正规地图的着色数量一定不少于非正规地图。

2) 不可避免构形

1878年，著名的律师兼数学家肯普（Alfred Kempe）提交了证明四色猜想的论文。

肯普的证明阐述了两个重要概念，第一个概念是“不可避免构形”。他证明了在每一张正规地图中至少有一国具有二个、三个、四个或五个邻国，不存在每个国家都有六个或更多邻国的正规地图，也就是说，由二个、三个、四个或五个邻国组成的“构形”是不可避免的，每张地图都至少含有这四种构形中的一个。

证明过程引用了欧拉公式(v:顶点-e:边+r:面=2)，得出任意平面地图，一定会存在至少一个国家，该国的邻国数量<=5：

1. 欧拉公式:

v-e+r=2；

2. 平面地图:

3*v<=2*e；

3. 将欧拉公式代入公式(2)得:3*r-e>=6；

4. 假设正规地图中每个面平均有x条边，有:x*r=2*e；

5. 将(4)代入(3)得: 6*r-x*r>=12，从而得平均边数: x<6；

因此，平面地图中一定存在至少一个国家，其邻国数量<=5；

3) 构形可约

肯普提出的另一个概念是“可约”性。即将不可避免构形（二、三、四、五邻构形）中心的国家约掉，一定不会增加地图的着色数量。

在约减不可避免构形中心的国家时，地图上其余的>=6邻国构形的国家边数会降低，剩余的国家数量也会逐渐减少，最终会得到一份国家数量有限、且仅包含不可避免构形的地图。如果这份约减后的地图是四色足够的，则初始的地图也一定是四色足够的。

二邻、三邻国构形约减掉构形中心的国家并不会影响地图其它区域着色，四邻构形约减掉中心国家虽然影响其它区域着色，但是利用肯普链交换可以保证四色足够。

肯普的证明中，认为五邻国构形也可被着四色，约减后利用肯普链恢复五邻国构形时也一定不会引入第五种颜色。如下图所示，当五邻国构形周围的五个国家存在（A-C）（A-D）两条肯链时，按如下方式换着四色。

4) 希伍德反例和五色定理

1890年希伍德(Heawood)指出“肯普链”方法中的缺陷，存在无法使用肯普链变换着四色的五邻国构形。

在希伍德构造的16国反例图中，五邻国构形周围的五个相邻国家，存在（A-C）与（A-D）两条“交叉”肯普链。使用肯普链变换，四种颜色在这五个周边邻国中恰好能循环往复，无法降到三种颜色，从而无法证明五邻国构形（共六个国家）可以被着四色。

对于该缺陷，肯普自己也认为无法修复，因此四色猜想憾未得证。但得到了相对较弱的五色定理命题。

希伍德同时提出猜想：在任意的可定向曲面上，最多只用

种颜色就能为任意的地图染色，其中k是曲面的亏格。当k = 0的时候，这个猜想就变成了四色猜想。在1968年，杰拉德.格尔和J.W.T.杨格斯最终证明了这个猜想在k ≥1时的情况。

直到1976年，数学家凯尼斯.阿佩尔和沃夫冈.哈肯设计了“放电法”程式，经过计算机1200小时的验证，首次得到一个完全的证明，四色猜想也终于成为四色定理。这是首个主要借助计算机证明的定理，一开始并不为许多数学家接受，因为不少人认为这个证明无法直接验证。尽管随着计算机的普及，数学界对计算机辅助证明更能接受，但仍有数学家希望能够找到更简洁的、不借助计算机的证明。

下文尝试论述一种直接的、不需借助计算机验算的四色定理证明过程。

三、证明过程-约减五邻国构形

对五邻国构形着四色，只有一种组合：五邻国构形中处于周围的五个国家，一定有四个邻国处于同一条肯普链（本图示为C-D肯普链）上。

我们通过变换五邻国构形的邻居关系，先把五邻国构形变成四邻国构形，然后采用多种约减规则衍生出多份约减地图。在恢复五邻国构形时，利用多份衍生地图间的相互约束，确保五邻国构形周围的五个国家中，有四个邻国处于同一条肯普链上。

为了任意约减由五邻国构形变成的四邻国构形周围国家数量，我们临时将该四邻国构形的邻接状态改为非正规邻接（假设四个周围邻国仅相邻于一点，允许着同色），并临时借用第六种颜色F（根据五色定理，假设当前地图为A、B、C、D、E五色），对目标四邻国构形进行多路约减：

约减规则1：

对四邻国构形周围上方三个国家，及位于中心的国家着F色，这四个F色国家合并，衍生出一份局部剩余两个国家的地图。根据五色定理，排除本轮约减操作时引入的F色（在约减下一个五邻国构形时，需重复引入F色）；

约减规则2：

对四邻国构形周围右方三个国家，及位于中心的国家着F色，这四个F色国家合并，衍生出一份局部剩余两个国家的地图。根据五色定理，排除本轮约减操作时引入的F色（在约减下一个五邻国构形时，需重复引入F色）；

约减规则3：

对四邻国构形周围左上方二个国家，及位于中心的国家着F色，这三个F色国家合并，衍生出一份局部剩余三个国家的地图。排除引入的F色；

然后再对右下方的两个国家着F色并合并，衍生出一个局部剩余二个国家的地图。排除引入的F色（在约减下一个五邻国构形时，需重复引入F色）；

对同一个四邻国构形按上述三种约减规则操作，衍生出三份仅“局部不同”的地图；

接下来我们对地图中其余的五邻国构形按同样的规则进行约减处理，在约减全部五邻国构形过程中，我们可能会得到数量为五邻国构形数量^3(立方)个地图(在约减过程中，>5邻国的构形周围邻国数量会降低，会产生新的五邻国构形)。

最终约减过程中衍生的所有地图，都将被约减到仅包含三邻国构形的四面体上，我们知道四面体是四色足够的，从而第五种颜色(E)也是不必要的。

四、证明过程-约减过程还原

通过上文的三项约减规则，针对每个五邻国构形，我们都会得到仅“局部不同”的三份衍生地图。假设衍生后的三份地图均是四色足够的，能否推演出约减前的五邻国构形地图也是四色足够的呢？

证明：假设存在“局部不同”的三份衍生地图都是四色足够的（A、B、C、D四种颜色），则这三份衍生地图对应的约减前的五邻国构形地图，也是四色足够的。

下文图示证明如何由三份衍生的四色足够地图，恢复得到四色足够的五邻国构形地图。

我们将三份衍生后的四色足够地图，局部区域临时变为非正规邻接状态，如下：

第一份衍生地图与第二份衍生地图均四色足够，说明1-2之间存在C-D肯普链；

第三份衍生地图与第二份衍生地图均四色足够，说明2-3之间存在C-D肯普链；

三份衍生地图同时四色足够，那么在第二份衍生地图上的1-3之间必然存在C-D肯普链。

在第二份衍生地图上利用1-3间存在的C-D肯普链，对局部区域右上方着A、B色的两个邻国做肯普互换着色，一定可以得到一个可着三色的四色足够正规四邻国构形地图。

然后变更该四邻国构形的邻居关系，恢复得到四色足够的五邻国构形地图。

如此，按照约减规则的逆序，每三份约减衍生的仅局部不同的四色足够地图，均可恢复一份四色足够的五邻国构形，直到地图还原到初始状态时仍然四色足够，从而四色定理得证。

五、参考

https://zh.wikipedia.org/wiki/四色定理

https://baike.baidu.com/item/四色定理