四色定理：伪证与推广
这篇专栏，主要是我在看了一篇四色定理科普后写出来的。因为我从评论区发现有些人证明了一些更弱的定理（比如“平面上不存在五个两两相邻的国家”）便以为已经解决，还有的人对其他情况的“n色定理”不是很熟悉。而现在的大部分科普却往往忽视了这些点。因此我决定写这一篇专栏，总结一下目前常见的一种伪证以及它问题，还有对其他方向的一些推广。
我敢打包票，这篇专栏是目前B站对四色定理阐述最为详细的一篇了。
问题介绍
“四色猜想”描述如下：
将一块有限平面分成一些相邻的区域（这里相邻定义为至少有一条曲边由两个区块共有，而非一个点），每个联通区域称为一个国家（也就是说，没有现实地图中“飞地”的问题），这样的划分结果称为一个地图。要求给地图中每个国家上色，一个国家整体是一种颜色，相邻的国家不能有相同颜色。做到这样只需要4种颜色。
四色猜想最初于1852年提出，最初是英国的古德里在绘制英国地图时抽象出来的问题，在和兄弟一起研究无果后，他向他的老师德摩根提了这个问题，但老师和他的数学家朋友也没法解决这个小孩子都能听懂的问题。1878年凯利向伦敦数学学会提出了这个问题，从而使得该问题变得知名。
在几乎同一年，在美国的律师肯普就给出了一个证明。他的思路是先证明所有地图中都存在一小部分特殊的部分，只要这些特殊的部分都可以用四色填色，那么整张图就可以用四色填色。然后他再证明这些特殊的部分都可以用四色填色。然而十一年后有人发现他给出的几种特殊部分中，有一种并不能完全用肯普提供的方法填色。肯普最后只是证明了五色定理。
如此快对五色定理的解决让人们相信四色定理十分简单，纷纷开始尝试。人们把肯普发现的特殊部分称为“不可避免组”，开始继续研究。然而随着研究深入，人们发现不可避免组的数量越来越多，到最后无法通过人力去检验和寻找。一百年以后，美国数学家阿佩尔和哈肯借助计算机，找到了全部的1963种不可避免组，并证明它们都是可以四色填色的。至此，四色猜想作为近代数学三大猜想（另外两个是费马猜想和哥德巴赫猜想）中最早被证明的猜想，被称为四色定理。
最为常见的伪证：平面上五个国家不可能两两相邻
上图的左边就是在科普四色猜想时最为常用的地图。如果我们把每个国家看成一个顶点，每个国家之间的相邻关系用边相连来表示，则我们可以把左边的图变成右边的图。可以看到，在右边图中，没有一条线是交叉的。我们把这种由顶点和边构成，每条边两端都有顶点且顶点不同，边与边之间不会交叉的图暂且称为平面图（注：这是一个不严谨的定义）。很容易发现，所有的平面上的地图都可以变成平面图。四色猜想也就等价地变成了
给一个平面图的顶点上色，要求每条边的两端的结点颜色不能相同，最多需要四种颜色。
右图还有一种好处，就是它可以消去重复的边，例如下图。
如果在左边的图底下研究的话，红色和蓝色有两条接壤边界，而右图中则只有一条边就表达了相邻关系。右图更加抽象简洁，因此我们之后会常用用右边这种图示。
扯远了，我们回头看那张四个国家的图。这张地图非常典型，它是国家最少的需要四种颜色的地图。在这张图中，四个顶点两两相邻（由一条边相连）。我们将所有结点两两之间都有且仅有一条边的图称为完全图。n个结点的完全图记作Kn。
然而，正因为它太过典型，很多人在开始研究这个问题时都会不由自主地被它限制住思路。由于这张图中四个国家两两相邻，于是很多人便认为，只要证明平面上不存在五个顶点两两相邻的情况，即证明K5不是平面图，就能证明四色猜想。
K5不是平面图这个证明非常简单。但在此之前，我们先要证明一个引理：欧拉公式。不是那个指数虚数的，是多面体中顶点数加上面数减去棱数等于二那种公式。我们首先证明在平面图中
V+F-E=2，其中V为顶点数，F为面数，E为边数
这里的面是指由边分割而成的联通区域。我们可以在上面的平面图中进行验证：上图有4个顶点，6条边，4个面（注意，最外面的无限大区域也是一个面：显然它是联通的），符合上述公式。
那我们怎么证明呢？我们可以对任何平面图重复做如下操作：
如果平面图中有一个顶点只与一条边相连，那么我们可以删去这条边和这个顶点，这样操作后。V减少1，F不变，E减少1，V+F-E不变。重复直至不存在这样的顶点。
如果平面图中有一条边连接两个顶点（注意由于我们是先做第一步的，这一步中的两个顶点一定有其他边相连），我们可以删去这条边，由这条边分割的两个面会变成一个面。这样操作后，V不变，F减少1，E减少1，V+F-E不变。返回第一条判断。
最终我们只会剩下一个顶点和一个以全平面为其内容的面，V为1，F为1，E为0，V+F-E=2。而在上述操作中，等式左侧的值永远不变。因此对任意平面图，V+F-E=2。
欧拉公式证完了，接下来我们回到我们要证的东西：K5不可能是平面图。
反证法，我们先假设K5是平面图。那么，在K5中，V=5，E=5*4/2=10，因此F=2+E-V=2+10-5=7。平均每个面有2*10/7<3条边，由平均数的意义，一定存在一个面的边数小于等于两条。而按照完全图的定义，任意两个顶点之间最多有一条边，因此不可能存在只有两条边的面，而只有一条边的面只可能出现在K2完全图中，推出矛盾。假设错误，因此K5不是平面图。
很容易的，我们就把K5不是平面图给证了出来。既然K5不是平面图，那么也就没有地图能对应K5，平面上也就不存在五个国家两两相邻的情况。既然不存在五个国家两两相邻，那么我们就不需要五种颜色。而既然已经有必须要四种颜色地图的例子，那四色猜想证完了呀！有什么问题？
问题就在于“如果一个地图中不存在五个国家两两相邻”并不能那么显然地推出“那么地图不需要五种颜色”。我们可以考虑这个推论的等价命题
如果一个平面图任意五个顶点都不能构成K5，那么这个平面图不需要五种颜色去染色
单看这里，可能没啥问题。但我们可以考虑一个更强的命题
如果一个图需要五种颜色，那么这个图存在5个顶点可以构成K5
注意到在上述表述中，我把“平面”这个词删去了，也就是说，边与边之间可以交叉。基于此，我们可以给出如下图。
可以看到，这张图中边有交叉。如果算一下欧拉公式你也会发现这不是平面图。仔细观察上图的结构，你会发现这张图中有两套共面的K4，这两套K4又通过中间的红色共顶点连接。因此，如果只能用四种颜色，为了满足两侧的K4，中间的点和两套K4最上方的点颜色必须一样。而这两套K4最上方的点又用一条边相连，边两端顶点颜色相同，不符合上色要求。因此我们不得不引入第五种颜色。然而如果你仔细看的话，上图并没有哪五个点能构成K5。上图中没有五个两两相邻的点，但仍然需要五种颜色。
上面的反例是想说明什么呢？的确，我们的反例举的是非平面图的例子，对于证明或证伪四色猜想没有任何帮助。然而，你能保证，一个没有K5的平面图，这个平面图就一定不需要五种颜色去染色吗？凭什么非平面图会出现的反例，在平面图上就不会出现？如果你能证明这样的反例不可能出现在平面图中，那这确实是证明了四色猜想。但问题是，你证明了吗？
我们再看两个例子加深印象
显然，这两张图都是平面图。左边的平面图没有K3，但是它需要三种颜色；右边的平面图没有K4，但是它需要四种颜色。那么，你怎么能保证，一个没有K5的平面图，不需要五种颜色？
可能还有人不是很理解这段的反证法究竟是什么问题。我再详细写一下“反证法”的证明过程：
我们先假设存在一张平面图都需要5种颜色染色，那么这张平面图中一定存在一个由5个点构成的完全图K5。而K5不可能在平面图中出现，因此假设错误，平面图不需要5种颜色去染色。
我们把上述证明中所有的5都换成n
我们先假设存在一张平面图都需要n种颜色染色，那么这张平面图中一定存在一个由n个点构成的完全图Kn。而Kn不可能在平面图中出现，因此假设错误，平面图不需要n种颜色去染色。
我们会发现，证明的第一步在n=3、4的时候是不成立的，那为何在n=5的时候成立了呢？这需要给出详细证明，而不是一个“显然”就能过去的。如果不考虑证明过程的正确性而滥用反证法，就会闹出如下笑话
如果1+1=2，那么太阳将从西边升起。但太阳不可能从西边升起，所以假设错误，1+1≠2。
希望各位读者好好理解这一节所讲的内容。根据我讨论的经验我发现很多人就是绕不过去这个坎，想不通这两个命题实际上是不等价的。“图没有Kn”只是“图不需要n种颜色”的必要条件，而非充要条件。由逆否命题等价性，“图需要n种颜色”也只是“图有Kn”的必要条件，而非充分条件。
此外还有一些其他的伪证思路，比如看上面4色无K4的反例图，有人会发现它每个点都至少发出3条边，因此可能认为只要证明地图中一定存在相邻国家数小于4的国家，就能证明四色定理。这种证法在环面中是可以的，但是在平面中不成立。比如说我们可以对正十二面体球极投影，这样得出来的一个12个顶点的平面图，每个顶点都发出五条边。这也是平面比环面难的一个原因。
还有的人可能看上面4色无K4和5色无K5，发现它们之中存在与K4和K5相似的结构，因此给出猜想：只要一张图能用四色染色，那么它一定不能通过删边、删点和并点的变换变成K5及以上的。与前面两个伪证不同，这个猜想是等价的，被称为哈德威格猜想，
当一张图需要n种颜色才能染色时，Kn一定是该图的图子式
这里图子式就是可以通过对原图删边、删顶点、融合一条边相邻的顶点获得的图。哈德威格本人证明了n=4的情况，可以用上面那张反例图验证，K4尽管不是它的一个子图，但确实是它的一个图子式。1937年，Klaus Wagner证明了上述猜想在n=5时和四色定理是等价的。然而现在对n=5的证明都是从四色定理出发的，如果能绕过四色定理，那确实是一个完美的证明。
看点别的：四色问题推广
那既然这不是证明，我们能怎么证明四色问题呢？很遗憾，由于四色问题现在依然处在计算机的统治之下，我并不能给出四色定理的详细证明。不过对于一些简单的问题，我们还是能证的。接下来，我们先看看四色问题朝其他方向的推广，然后再证明四色定理的弱化版：六色定理和五色定理。
把一个问题推广，一个方向就是改变问题的维数。一维曲线段很简单，我们只需要2种颜色交替排布就能给所有国家上色。现在，一维2种颜色，二维4种颜色（我们假定四色定理成立），那三维要几种颜色呢？6种？8种？7种？都不是，答案是不存在这样的最小值。
我们可以从下面这个简单的模型中证明这一点。看完之后，读者可以尝试构建一下自己的模型，留作习题。
我们将一些国家交替排布，于是我们可以得到上图。
你也许要说，这样交替排布只要两种颜色就够了！确实，但这里用不同颜色是为了下一步更为清楚。我们在第一个国家（白色）的第一个方块上向上延伸一格，然后向右覆盖所有的其他国家。
这样，第一个国家便与其他所有的国家相邻。接下来，我们再取第二个国家（橙色）的第二个方块向上延伸一格，然后向左右延伸覆盖。
这个国家依然可以和所有国家相邻！我们还可以对第三个、第四个……所有的国家都做一遍这个操作……
最终的结果就是所有的国家都会和所有其他国家相邻！这就意味着所有国家都必须有一个不同的颜色！（还记得“没有Kn”是“不用n种颜色”的必要条件吗？否命题“有Kn”就是“要用n种及以上颜色”的充分条件了。）而尽管我们在上面展示的时候只使用了六个国家，但很显然以上构造过程中并没有限制必须要六个国家。因此，对任意正整数n，我们都可以构造出不能用n种颜色涂色的三维“地图”！
升维不行，那我们只能研究二维问题了，二维问题也不光是平面，还有球面、甜甜圈面、莫比乌斯面等等。在这些面上，四色问题会有怎样的结果呢？
（其实三维也不只有我们上面研究的那种样子，还有比如说向二维球面一样的三维空间：你往任意方向走都会在一定距离后回到最开始的位置。有人说其他种类的三维也不存在最少的颜色，但这方面我不太懂，不拓展了。）
先研究最简单的球面。有人会认为球面需要五色，比平面多一色。因为曲线段需要两种颜色，而圆需要三种，多一种。那球面也应当比平面多一种，要五种。然而，这个答案是错误的，因为可以很容易地证明，球面和平面实际上是完全一样的。
要做到这点，我们可以用一个叫做“球极投影”的变换。做法是将球放在平面上，将球最上方的点与球上其他点连线，连线与平面的交点即为投影点。这样，除了北极点自身，其他所有点都和平面上的点一一对应。
接下来我们旋转球，让最上方的点落在一个国家的内部，这样，我们就可以获得一张平面图，这张图的外围是一个无限大的国家。
然而如果你把它转成平面图，你会发现这依然是一个有限的图！无限大小的国家并没有对应成无限多的顶点。或者，你也可以理解成，上面那张无限地图和下面这张有限地图其实是完全等价的。
也就是说，只要平面四色能画完，球面四色一定能画完；平面画不完，球面也一定画不完。这也说明，随随便便把其他维度的结果抄过来并不总能给出正确的结果。
球面是四个，其他面呢？我们先考虑甜甜圈。甜甜圈面（环面）和球面一样，是一个可定向闭曲面。也就是说，它有“里面”和“外面”，而且没有边界。我们之前证了平面上的欧拉公式，球面上的我们可以用球极投影证明球面上的公式是完全一样的，也就是常用的多面体的欧拉公式。但环面中间有个洞，这就导致我们之前用到的欧拉公式并不能直接用在环面上。我们需要把公式改造一下，变成V+F-E=0。如果曲面再多一个洞，那右边再减2。
接下来怎么证？我们仿照平面地图的方法，将它转成一个图。如果转成的图中有面只有两条以下边，这个面只能是整个环面，这些情况显然可以用七色填色。如果有只有一条边连接的顶点，那只要剩下的图可以七色填色，加上这个顶点依然可以七色填色，因此我们可以把所有这样的顶点删去。对于剩下的情况，面的边数至少为3，每条边的两侧都是不同的面，因此3F≤2E，由欧拉公式推知，3V≥E，2*E/V≤6。也就是说平均每个顶点发出的边数小于等于6，因此必然存在发出边数小于等于6的顶点。
对于n个顶点的图，我们找到一个边数小于等于6的顶点，删去该顶点及与其相邻的边，如果剩下的n-1个顶点的图可以用七色填色，原来的图也可以。而这个新的n个顶点的图也有一个边数小于等于6的点，我们重复这样的操作，最后只剩下小于等于7个顶点时一定可以用七色涂色。因此任意环上的地图都可以用7色涂色。
接下来只要我们能找到一张必须要7种颜色涂色的地图，就能证明环面七色定理。幸运的是，人们找到了它。
其他曲面也有类似定理，例如在莫比乌斯带上需要6种颜色。
在“推广”这章的最后，我们来看一下现实世界中的地图，考虑一下飞地问题。飞地就是地图上尽管没有相邻，但是需要是有相同颜色的区域。按这个定义来讲，飞地其实远比想象的要多。比如现实世界中，所有的湖泊都可以看作海洋的“飞地”。
我们接下来给出一种构造，以证明当地图具有飞地时，颜色就没有上限了。比如我们考虑一个已经需要n种颜色的地图，我们往这张图上添加一个新国家，这个国家在其他每个国家中都有一块飞地。这样这个国家就必须要一种新的颜色，不能用原来的n种颜色。因此需要的颜色无上限。
因此当有飞地存在时，四色定理是不成立的，这也是为什么现实世界的地图绘图时通常不会特别去应用四色定理。
四色定理弱化版：六色定理和五色定理
推广推完了，我们接下来尝试一下接近四色定理，证明六色定理和五色定理。
还记得我们之前的环面七色定理吗？我们可以把这个证明过程照搬到平面上，从欧拉公式得到6>2E/V，这样一定存在一个顶点只发出小于等于5条边。因此类比在环面上的证明可知6种颜色一定能绘图。六色定理就这样证明了。
五色定理需要一点技巧，我们这里介绍肯普的证明。首先，对于顶点数小于等于5的平面图，一定可以用五种颜色绘图。接下来，考虑顶点数大于6个的情况，找到发出边数最少的顶点，
如果这个点发出的边数小于等于4，那么很显然这个顶点可以不考虑，其他点如何用五种颜色涂色并不影响这个点，因为这个点只要取与它相邻颜色不同的颜色即可。
如果有发出了5条边，我们先删去这个顶点，然后对剩下的图用5种颜色涂色，涂完以后再把这个点加回来看它应该涂什么颜色。如果相邻的五个顶点有相同的颜色，那么该顶点不能选择的颜色数就小于4，我们依然可以找到一种颜色给它填上。
真正的难点在于处理相邻5个顶点颜色都不相同的情况。这时你就没法用旧颜色去填充了。但我们接下来要证明，我们可以通过修改原本的填色方式，使得这5个相邻顶点中出现颜色相同的顶点。
这里我们需要引入一个肯普在他的证明中的概念：肯普链。肯普链就是只有两种给定颜色顶点构成的极大联通子图。就像下图中，圈出来的黄绿色可以组成一条肯普链，红蓝也可以组成一条2个顶点的肯普链，红绿则有一条3个顶点的和一条1个顶点的（最上方的那个绿色顶点）。
由于肯普链是把所有联通的两种颜色的顶点给包括了进去，因此与肯普链相邻的点不会有肯普链上的颜色。因此我们可以做出反色操作：设肯普链上有颜色A和颜色B，我们把链上所有颜色为A颜色的顶点换成B颜色，B颜色的顶点换成A颜色。这样的图依然不会产生矛盾。就像下图所示的那样。
基于此，我们就可以给出证明，我们考虑下图的模型
我们任意选择两个间隔一格的颜色，比如这里我们选择蓝色和橙色，找到连接这两个顶点所属的蓝橙肯普链。如果像下图一样，这是两条不同的，那我们就可以把其中一条肯普链反色，这样这两个顶点的颜色就完全相同了。
但如果这两个顶点属于同一条肯普链，那么它就会把红色和黄色、绿色分割开来，我们可以在红色结点上寻找红黄肯普链或红绿肯普链，将其反色，这样又造出了两个相同颜色的结点。
这样我们就证完了五色定理。
四色定理的遗憾：计算机证明
上面这套证法是肯普的四色定理伪证被发现错误的附带产物。肯普本人也是用肯普链去证明四色定理，然而人们检查他的证明过程后发现，对于有4个邻国的证明，肯普的证明完全正确，但有5个的证明并不严密。由此开启了数学家们百年打补丁的奋斗历程。
很明显，只要一张地图有一小块区域不能用四色填色，整张地图就不能用四色填色。因此，人们就开始寻找这个最小的区域以证伪四色猜想，或者证明平面图上不可能存在这样的区域。
但是，平面有无限种可能的划分，我们应当怎么去研究这无限多种呢？人们开始想尽一切办法去归类可能的地图。比如像本文最开始把地图变成平面图，就把一大堆实质相同，但看起来不同的地图归为一类。再比如，因为有4个邻国的证明是正确的，因此可能举出的反例中最小的图必然不存在发出边数小于4条以下的顶点，因此研究的平面图必须保证图中所有顶点都至少发出五条边，否则那个顶点便会被删去。再比如，平面图中所有的面都应该只有三条边，因为如果有一个面有四条边，我们就能把它割成两个三条边的面，后者多了一个相邻关系，约束关系比前者更强。但即使做了这么多剪枝，要研究的图形还是无限多的。于是人们便开始找这些图中有没有一些特定的关系。
肯普的证明表明，一张平面图中，一定存在一个边数小于等于5的顶点，这再任何平面图中都不可避免，肯普也根据这个不可避免的顶点将所有的平面图分了类。后来人们将这种不可避免的部分称为“不可避免组”。如果能找到所有的不可避免组，就能按照各组的方式去约化图形。这样就能化无限为有限。
1970年，德国数学家Heesch在证明过程中引入了放电法。核心就是把平面图看成电路图，然后根据欧拉公式计算出的发出不同数量的边的顶点的比例，在每个顶点上放上相应的正电荷，让电荷开始流动。如果推出矛盾，比如流动前后电荷不守恒，那么这张图就不成立。在大西洋对岸，1972年，数学家Appel了解到这种解决方法后决定使用计算机进行处理。1976年，在对Heesch的程序和证明方法进行大量改进后，Appel等人发现不可避免组总共只有1936个（我理解的其实已经约化很多了，毕竟Heesch列了8900多种）。然后他们便对这所有的1936个组分类讨论，用计算机程序程序进行检查，在1200个小时的运算后，1936种情况全部检验成功，四色定理终于得证。
尽管证明了，但大家依然抱着非常谨慎的态度。因为前车之鉴实在过多，让大家难以相信这个定理就这么被证明了。不断有人指出程序中的漏洞，证明团队也不断地打补丁。在经历漫长的修正和验证后，程序和证明最终被发现无可挑剔，人们也接受了四色猜想作为一个定理存在。
但1963种依然过多，原本的证明团队后来把不可避免组的数量约化到了1482种。1996年，Robertson等人在Appel的基础上将不可避免组的数量约化到了633种，并且还优化了算法，大大降低了时间复杂度。
四色定理最终被证明了，但数学家们一开始却高兴不起来。因为这种证明充其量就是大力出奇迹，一点没有数学的简洁之美。更重要的是，这套证明并没有给其他的问题提供太多帮助。安德鲁怀尔斯在证明近代数学三大猜想的另一个猜想，费马大定理的时候做了许多创新的工作，并运用了朗兰兹纲领中的思想，架设起了数学不同领域之间的桥梁。而四色定理就没有如此多的成果。数学家的解决问题的最终目的不是解决问题，而是在解决问题中创造新的工具以解决其他问题。所以在最开始，这一证明不受很多数学家待见。直到现在，依然有部分数学家抱着“我可以接受这个证明是正确的，但我绝对不接受这个证明”的心理，尝试给出一些更“数学”的证明。
然而，作为第一个使用计算机的数学证明，四色定理的证明成功打破了数学家们对计算机的抗拒心理，现在，越来越多的数学定理的证明过程开始基于计算机。这也可以算是四色定理的一项成果吧。
