一、概述
1852年，伦敦大学毕业的格斯里（Francis Guthrie）在一家科研单位从事地图着色工作时，提出四色猜想：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色”。
1976年，四色定理通过“放电法”程式、基于计算机大量运算首次得证。但图论爱好者对于依赖电脑的证明过程心存不甘，始终相信四色定理存在某种不依赖计算机的证明方法。
本文在前人基础上，论述一种简洁的、无需借助电脑海量运算的四色定理证明过程。
四色定理的论证历史及衍生命题，可参考维基百科或百度百科。
https://zh.wikipedia.org/wiki/四色定理
https://baike.baidu.com/item/四色定理
二、关键概念
1. 正规地图
正规地图是指：没有一个国家包围其他国家，或没有三个以上国家相遇于一点的地图为正规地图(维基百科中称为三度图)。
如上图所示，国家数量相同，在地图上的位置也相同的情况下，正规地图的着色数量一定不少于非正规地图。
本文直接忽略二邻国、三邻国构形的约减及恢复，忽略二邻国、三邻国构形不影响四色定理的证明。
2. 不可避免构形
1878年，著名的律师兼数学家肯普（Alfred Kempe）提交了证明四色猜想的论文。1890年希伍德（Heawood）发现肯普的论证方法中存在隐蔽缺陷而憾未得证。
肯普的证明阐述了两个重要概念，第一个概念是“不可避免构形”。他证明了在每一张正规地图中至少有一国具有三个、四个或五个邻国，不存在每个国家都有六个或更多邻国的正规地图，也就是说，由三个、四个或五个邻国组成的“构形”是不可避免的，每张地图都至少含有这三种构形中的一个。
证明过程引用了欧拉公式(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)指出“肯普链”方法中的缺陷，存在无法使用肯普链变换做着四色的五邻国构形。
Heawood构造的16国反例图中，五邻国的五个相邻国家，A-C与A-D肯普链交叉存在，使用肯普链变换，四种颜色在这五个周边邻国中恰好能循环自洽，无法消减为三种颜色，从而无法证明五邻国构形（共六个国家）是四色足够的。
对于该缺陷，肯普自己也认为无法修正。但相对较弱的五色定理命题得证。
三、证明思路
五邻国构形若能四色足够，只有一种组合：五邻国构形中处于周围的五个国家，一定有四个邻国处于同一条肯普链（本图示为C-D肯普链）上。
要证明Heawood反例中的五邻国构形是四色足够的，我们需要在“五色定理”基础上，临时借用第六种颜色，迫使五邻国构形中的六个国家四着色。在对五邻国构形约减时，分析需要采用多种约减规则生成多份约减后地图，这样在恢复五邻国构形时，利用多份约减地图间彼此盈亏互补，以佐证约减前的地图四色足够。
我们对地图中的五邻国构形同时执行如下三种约减规则：
1. 约减规则一：
(1). 临时将五邻国构形中周围五个相邻国家的邻接状态改为非正规邻接（假设这五个邻国仅相邻于一点，允许着同色）；
(2). 引入第六种颜色F（根据五色定理，假设当前地图为A、B、C、D、E五着色），通过肯普变换，五邻国构形周围的五个相邻国家得到三个同色为F的邻国；
(3). 对三个F同色邻国及中心E色国家合并，将原来六个国家，约减为三个国家；
(4). 对约减后的地图恢复为正规地图，并根据五色定理，通过系列肯普变换消减本轮中新引入的F色（在约减下一个五邻国构形时，重复引入F色）；
2. 约减规则二：
同色(B)的两个国家及中心E色国家合并，将原来六个国家，约减为四个国家；
3. 约减规则三：
引入第六种颜色F（根据五色定理，假设当前地图为A、B、C、D、E五着色），将A、C转着F色，并同中心E色国家合并，得到另一份约减为四个国家的地图；
对同一个五邻国构形按上述三种约减规则操作，得到三份仅“局部不同”的地图；
接下来我们对地图中其余的五邻国构形按同样的操作进行约减处理，在约减全部五邻国构形过程中，我们可能会得到数量为五邻国构形数量^3(立方)个地图；
最终，约减过程中衍生的所有地图，都将被约减到仅包含最小构形(三邻、四邻、五邻)的有限个国家，都可以被四着色，从而我们发现第五种颜色(F)也是不必要的，因此四色定理得证。
四、逆向验证
通过上文的三项约减规则，针对每个五邻国构形，我们都会得到仅“局部不同”的三份约减后的地图，假设约减后的三份地图均可被四着色，能否推演出约减前的五邻国构形地图也可被四着色呢？
证明：假设存在“局部不同”的三份约减后的地图都可以被四着色，则这三份地图对应的约减前的五邻国构形地图，也可以被四着色。
首先，按约减措施一得到的四色地图，变化成一个局部非正规的四色地图(包含三个A色国家)，然后顶端的A色国家经过一系列肯普变换着为C色，再把五邻国中心的国家着B色，得到恢复后的正规五邻国构形，且地图仍为四着色；
如果五邻国构形周围顶端的A色国家不能经过肯普链变换为C色，此时需暂时引入第五种颜色E，同时将原C色国家转着E色，此方式恢复得到的正规五邻国构形中的六个国家是四着色的；但是此时地图中共包含了A、B、C、D、E五种颜色；
这种情况下仅依赖约减规则一得到的四色地图，在复原正规五邻国构形时已无法证明四色足够，此时需要利用约减规则二、三得到的四色地图，佐证复原过程中的地图四色足够。
如下图所示，如果约减规则一得到的地图，在复原五邻国构形时，必须引入第五种颜色，则约减规则二、三得到的、与之“局部不同”的地图必然也不能四色足够。
但是根据上文推演，按三种约减规则得到的仅“局部不同”的地图均四色足够，约减规则二、三得到的地图也是四色足够的，这与通过约减规则一地图复原五邻国构形时必须引入第五种颜色矛盾，因此通过约减规则一地图恢复五邻国构形时，一定存在某种无需引入第五种颜色的着色方式。
我们按照约减规则的逆序，每三份约减后的地图，均可证明一个约减前的五邻国构形地图是四色足够的，直到地图还原到初始状态时仍然四色足够，从而四色定理得证。
五、参考
https://zh.wikipedia.org/wiki/四色定理
https://baike.baidu.com/item/四色定理
网友评论