(｡･∀･)ﾉﾞ大家好，这里是芋头猴，最近我在《The Fascinating World of Graph Theory》一书里读到了四色定理的这个证明思路，觉得很厉害，所以就拿上来和大家分享一下，那么下面开始√
〇、目录
0 目录——你在这里
1 莱昂哈德·欧拉——介绍了图论的基本概念
- 图和平面图
- 欧拉公式
2 阿尔弗雷德·肯普——证明了四色定理
- 定理的内容、解决它的难处在哪
- 4个以下邻国的情况
- 4个邻国的情况、肯普链
- 引理：最多的情况是5个邻国
- 5个邻国的情况、证毕
3 计算机时代——自那之后发生的故事
- 希伍德的反例
- 闵可夫斯基的故事
- 关于计算机证明
4 说点别的——最后的思考
一、莱昂哈德·欧拉
在开始证明之前，我会先花一些篇幅介绍一下有关图论的内容，为后面的证明做做准备。所以如果你对图论有足够了解或者不愿意读大段的介绍的话，就放心地跳到下一部分吧。
图的三个例子。软件：GeoGebra网页版
首先，图指的是把一些点用线连起来所组成的图形，这里的点我们叫做顶点，而线段叫做边。上面就是图的三个例子。当我们在研究图的性质的时候，主要关注的往往不是顶点和边的绝对位置或方向，而更多是它们之间的连接状况，比如两个顶点间至少要用多少条边让彼此相连，一个图中所连边数最多的顶点有多少个等等。
平面图指的是边与边之间没有任何交叉的一种图，例如上面三个例子中的前两个。在平面图中，被几条边包围起来的一小块区域叫做面，打个比方就是如果把一整块地用用来表示边的篱笆划分开，这样分出的每一小块地就都是这个图的一个面；特别地，注意处在整个图之外的“背景”部分（即没被我们的篱笆圈起来的那一大片空地），通常这一部分也算作一个面。
值得一提的是，我们拿立体几何中的相应名称来命名顶点、边和面，这是因为平面图与立体几何体之间有着很自然的对应关系：在一个（没有洞的）几何体空壳的一个面上戳个洞，然后把这个洞使劲向外抻开（类似于橡皮泥或者橡胶），直至原先的表面被抻平，这样一来原先的各个顶点、边和面就构成了所对应的平面图中的各个元素；反之，把一个平面图从纸上剪下来，啪叽，整个糊在一个圆球上，照着样子拿去雕，只要平面图自身的连接不至于太过松散，这样做也是可以得到一个几何体的。
五种正多面体和它们对应的平面图。图源：MathWorld
言归正传，让我们先来证明一个基本的结论。在平面图中，欧拉公式的叙述是这样的：
V-E+F=2
其中V表示顶点数，E表示边数，F表示面数。
欧拉公式的证明
它的证明来得也很直观。从一个平面图出发，我们首先可以一步步地拿掉所有分隔开两个不同的面的边，每一步拿掉一条边时也会使面数减一，所以(V-E+F)的值还是不变的；此外我们不必担心减掉一条边的时候我们的图会突然分裂成两个图（或者说，从连通图变成了非连通图），因为如果是这样的话，去掉的那条边的两侧其实就只是同一个面了。减到不能再减少的时候，我们的图将只剩下最外面的一个大面，以及一大堆的边和顶点（即一棵树）。接着，我们再一步步地拿掉所有剩下的边，并同时每一步都把它原先连着的两个顶点拽到一起，融合成一个新的顶点。由于每一步都只让边数和顶点数各减一，所以(V-E+F)的值仍没有变化。最终，我们将只剩下一个单独的顶点和一个大面，它们正好就满足V-E+F=1-0+1=2，证毕。
另外，3Blue1Brown曾展示过一种基于对偶图和生成树的证明过程（AV3372382的第6P，暂无翻译），感兴趣的话就去看看吧。
那么，到此为止图论中的基本概念差不多就都介绍完了，下面我们来看一看四色定理还有它的证明吧。
二、阿尔弗雷德·肯普
四色定理诞生于1852年，当时弗朗西斯·格思里（Francis Guthrie）注意到，在给一幅英国地图上色时，只需要4种不同的颜色就可以将所有相邻的县与县相互区分开。于是他就猜测，是不是任意样子的地图在按照这种规则上色时也都只需要4种颜色，可惜他最终也没能证明这一点。几经辗转，到了1879年，这个猜想已经变为了一道著名的数学难题。
所以这个猜想究竟说了怎么一回事呢？首先来说，为什么一定是4种颜色呢？显然，如果4种颜色够用的话我们就不需要第5种；如果再节约一点，只使用3种颜色的话，那么请看这个反例：
它的名字是完全图K4。
这个结构里的4个区域两两相邻，因此想把它们互相区分开，3种颜色是不够的，于是所有包含这种结构的地图也都至少需要4种颜色。但如果我们想再用这种思路说明4种颜色也不够时，就遇到了麻烦，这个的原因我将在后面解释。
其次，为什么这个看似简单的命题证起来就这么难呢？通常来说，解决这样的有太多变数的问题就需要用到归纳法，即一步步地把问题的每一种情况都化为更简单的、更好解决的情况来解开整个问题，就像我们在刚刚欧拉公式的证明中所做的那样。但在四色问题的情况里，如果你已经知道一张地图拿掉某一个区域之后可以满足四色问题，想返回来证明添上了这个区域的地图也满足四色问题仍然是很难的，比如可以去参考Matrix67的这篇文章：http://www.matrix67.com/blog/archives/6655
那么，为了更多地发挥出归纳法的力量，就还需要把它和反证法结合一下，得到我们的第二选择——最小反例。这是在说，通过研究所有假想的“可能反例”中最简单的情况并导出矛盾，也就是说其实最简单的反例就不可能存在，于是任意样子的反例就都不可能存在了。我们需要研究的是所有至少需要5种颜色来染的地图中，区域的数量最少的一个，然后想办法说明它只需要4种颜色就够了，从而完成证明。事实上，正是这个方法，让1879年的阿尔弗雷德·肯普（Alfred Kempe）给出了他的证明。
我们从最简单的情况开始分析。这个情况就是，我们的最小反例G包含了某一区域A，而这个A恰与其周围少于四个的区域相邻（见下图）。如果我们把这个A挖走，然后把它原来的土地都瓜分给周围的区域，那么如此得到的新地图G'的区域数是小于G的。换句话说，任何4种颜色满足不了的地图都必须比G'包含更多区域，所以G'只需要4种颜色就够了。不过这样的话G也只需要4种颜色就够了，因为当我们把A安回G'里去的时候，它自动就被染上了它周围的区域中还没用到的那种颜色。
A与3个区域相邻的情况。软件：Windows画图
下一种情况，假设存在某个A有正好4个邻居。乍一看，如果我们给G'上色时把4种颜色都用满了，那么我们把A放回来之后就彻底死棋了。别着急，来看看肯普是怎么做的。由于具体颜色的选取并不重要，所以假设A周围一圈的颜色依次是红(R)、蓝(B)、绿(G)、黄(Y)（见下图），那么从红色出发，找到所有和它相邻的绿色区域，再找和这些绿色区域相邻的红色，再之后是和这些红色相邻的绿色，以此类推。这就有两种结果：一，沿着其中某条红绿相间的路径一直走到底，可以走回到和A相邻的那个绿色区域，这样的一整条路径叫做一条肯普链；二，我们找不到这样的肯普链。如果确实有这么一条肯普链（见下图），那么我们就重新考虑蓝黄这对颜色，如果它们还能形成肯普链，那这条蓝黄链就一定得能跨过红绿链，而这是不可能的。因此在A周围，无论如何都至少有一对颜色，使得从任意一方出发都走不到另一方去。
一条肯普链（Kempe chain）
这正是我们想要的结果——为什么呢？选择这对颜色（比如说是蓝黄）中的任意一方（比如说黄色），从它向外走出所有能走的蓝黄路径，再把这些路径中的蓝色和黄色对调。一方面，得到的新图仍满足四色问题的要求（可以试试自行思考）；另一方面，与A相邻的颜色就只有红、绿、蓝三种了，于是A就可以涂成黄色了。
按着这个分类的思路走，如果我们不想浪费太多功夫的话，理论上如果再有这么一条结论，能告诉我们例如“好了好了，每个地图势必都会包含一个邻国数小于等于4的区域的，所以这个分类讨论就可以在此结束了”这样的话，那就再好不过了。我们要如何构造出这样的一点呢？重新想一想，不难意识到在画初始的地图的时候，自然法则还是更偏好那些邻国数较少的区域的：比如说，你能轻易就画出某个地图，其中每一个国家的邻国数都任意地多，这样的可能性实在是太小了。因此我们可以试试从所有地图都必定遵从的几何性质出发，把这条事实量化出来。
登登登登，屠龙的勇者欧拉公式登场了。它可以定量地阐明平面图的顶点数、边数和面数之间的权衡关系，这使得它能出现在很多形形色色的证明当中；然而在使用它之前，我们还是需要绕一点远道，先把地图转化为正正当当的平面图。
最简单暴力的方式就是把地图的每个区域视做一个面，再夹带上一开始提到的地图最外侧的那个大面，而顶点就可以放在所有三条及以上边界线交汇的位置上了。为了确保如此转化出来的图一定是个一个单个的平面图，那么如果它不是，唯一可能的理由就是它是多个平面图并列或者嵌套的结果。也简单，拆出来各个小平面图，挨个上色（因为区域数都变少了所以做得到），必要的话通过全盘对调某两种颜色来保证小图之间原先共有的那单独一块区域颜色相同，最后拼起来，结束。另外，为了之后广泛讨论起来方便，我们再单独分离出两种平凡的情况，即只有0个和1个区域的两种地图（对应着只有1个和2个面的平面图），一样是直接染就可以了。
现在给图的每个面 f 的边数起个名叫 Nf，考虑和式 Σ(6-Nf)，其中 f 遍历所有的面。它等于 6F-Σ(Nf)，F表示面数。在求 Σ(Nf) 这个和的时候，注意每一条边因为都和两个面相邻所以都被计数了两次，因此这个和还等于 2E，E表示边数。之后，我们再把每个顶点 v 连出的边数记做 Dv，同理 Σ(Dv)=2E，但是由刚刚的定义，每个顶点至少连着3条边，所以又有 Σ(Dv)≥Σ(3)=3V，V表示顶点数，所以得到 2E≥3V，0≥-4E+6V。合起来：
Σ(6-Nf) = 6F-2E ≥ 6F-2E+(-4E+6V) = 6(F-E+V) =12
如果G真的不含边数小于等于4的面，那么 (6-Nf) 只有在 Nf=5 的时候是正数1，其他时候都是零或负；而这些或正或负的数加起来至少等于12，那么我们不仅能知道一定存在 Nf=5 的面，还能知道这样的面的数量至少是12。
更棒的是，我们还能解开一开始留下的疑虑，即为什么不能有5个国家两两相邻，从而需要至少5种颜色的情况。这是因为如果可以，那么至少有一个国家会和地图之外的那个的无限大的面相邻，把这个面也分给这个国家，我们就可以得到一个一共有5个面，每个面至少有4条边的平面图，但是 5*(6-4)=10<12，矛盾。
总之，我们只需要再解决“G的其中一区域A有5个邻国”的情况就大功告成了。让我们继续用肯普链，也就是假设A周围一圈在染色时4种颜色都用上了，分两种情况，其代表分别是RRBGY和RBRGY。RRBGY的情况很好解决，它和有四个邻国的情况是类似的。而RBRGY的情况就稍微复杂一些了。
RBRGY的情况
如图所示，首先从蓝色出发找出蓝绿和蓝黄两条肯普链；如果找不到的话，就直接可以对调颜色了。接着，从蓝黄链一侧的红色出发来寻找红绿路径，也从蓝绿链一侧的红色出发寻找红黄路径，由于这两条路径都会被阻断，因此分别对调这两条路径内的两对颜色，A的各邻国就只剩下蓝、绿、黄三色了，腾出来的红色正好能让给A，从而四色定理证毕。
……但事情并没有这么简单。
三、计算机时代
在1879年肯普发表他的证明之后又过了足足11年，1890年的珀西·希伍德（Percy Heawood）在肯普的证明中发现了一处致命的错误，也就让“四色定理”又变回了“四色猜想”。下图就是希伍德给出的一个反例。
如图所示，如果我们还想要对调红黄、红绿路径上的颜色，那么上方的绿、黄两个区域都会变成红色，于是对调颜色的方法这就行不通了。
遗憾的是，希伍德发现的这个漏洞是如此之大，使得肯普再也没能完善他原本的证明，只好以失败告终。而在再之后的数十年里，谁也没能替肯普补上这个漏洞。但总之，希伍德为了安慰肯普，还是对其表扬了一番，因为把他的方法拿来证明地图中的“五色定理”还是绰绰有余的。而后，希伍德还将四色猜想推广到了任意曲面上，例如任何画在圆环面上的地图最多只需要7种颜色来染（http://www.matrix67.com/blog/archives/890）（Matrix67二杀），而在莫比乌斯带和克莱因瓶上则都只需要6种。
莫比乌斯带（左）和克莱因瓶（右）的6染色，箭头代表粘贴方向。
在1905年，闵可夫斯基曾挑战四色定理，留下了一段有趣的故事。这里我直接把它从知乎上复制过来：
一次拓扑课，Minkowski（闵可夫斯基）向学生们自负的宣称：“这个定理没有证明的最主要的原因是至今只有一些三流的数学家在这上面花过时间。下面我就来证明它……”于是Minkowski开始拿起粉笔。这节课结束的时候，没有证完，到下一次课的时候，Minkowski继续证明，一直几个星期过去了……一个阴霾的早上，Minkowski跨入教室，那时候，恰好一道闪电划过长空，雷声震耳，Minkowski很严肃的说：“上天被我的骄傲激怒了，我的证明是不完全的……” （原问题：https://www.zhihu.com/question/22212241/answer/79303297）
二十世纪六七十年代，计算机运算速度飞速提升，这使许多人都开始试着用编程的方法来解决一些当时悬而未决的数学难题，其中就包括阿佩尔（K. Appel）和哈肯（W. Haken）两人。前人的一次次失败意味着，似乎五邻国国家的情况根本就无法被解决，所以他们对肯普证明的第一步改造就是不再考虑单一国家的情况，而是考虑由相邻的一些国家共同组成的构型。这就需要例如放电法这种可以同时顾及到连续数个区域的邻国数的更高深的技巧来对原先的分类进行进一步细化，也使完成这个证明的难度大大提升，但最后他们还是成功列出了任何地图都必定包含一二的一共1936种构型，并于1976年在计算机的海量计算帮助之下完成了四色定理的证明。
阿佩尔和哈肯的证明一面世马上就遭到了质疑。这是数学史上首个依赖计算机完成的证明，而其证明过程几乎完全无法靠人力检验，同时，当时也有太多的人拿着错误的论据纷纷宣称自己“证明”了四色定理，可想而知这两人的证明也并没有受到很大重视。不过随后在1996年，另一些人用633种构型和更简练的算法再次通过计算机证明了四色定理，而于2005年又有人编写了专门的计算机程序来校验这些计算机证明，结果均表明四色定理真实无误。到目前为止，虽然尚有一部分人还在期待着一份人力证明的出现，不过大众已经广泛承认四色定理获证的事实了。
633种构型中的前几种。这里用到了对偶图和三角剖分的手段，其中黑点、无标志、圆圈、方块分别代表邻国数为5到8的区域。
四、说点别的
既然你已经读到了这里，那么不妨最后再来看一道思考题吧(°∀°)ﾉ：
考虑所有三维中的地图，其每个区域都是一块三维的形状。试说明，对于任意的有限多种颜色来说，总是存在某张还需要更多颜色来染的地图。（附加题，可以试试看最多能想出来多少种不同的构造方法√）
感谢阅读，同时欢迎关注靛蓝字幕组、圆桌字幕组、3Blue1Brown、Solara570和我。
