功败垂成的四色定理:被埋没的史话

大家好我是渡鸦,两年前我在B站发表了一篇《图论:如何错误地证明四色定理》,今天来聊一聊当时由于篇幅原因被忽略掉的另一个四色定理的“错误证明”吧。

彼得·泰特(Peter Tait)是一位苏格兰的数学物理学和热动力学家。同上一期所说,在1879年的肯普发表了著名的肯普链证明之后,泰特紧跟着在1880年发表了他自己的证明。

证明的第一步,是意识到给全部平面图染色,等价于给满足每个顶点都连有恰好3条边的全部平面图染色。例如,假如要染色的平面图中的某一个顶点连有4条边,那么以下的局部微扰可以把这样的顶点分裂成两个连有3条边的顶点:

对连更多边的顶点也可以如此操作,这个方法在对偶图意义上就叫做三角剖分。

下一步是先给图的每条边染色。和给图的每个面染色类似,这里的规则是只使用三种颜色,且每个顶点相连的三条边都需要有不同的颜色,例如:

在这样的染色中,考虑删掉被染上某一种特定颜色的所有边。由于图中本来所有顶点都连接三种颜色的边,这样删掉之后得到的新图中每个点都连着恰好2条边,而这样性质的图就只是一个或多个不相交的多边形。例如,从上面的这个图出发就会得到这样的结果:

从这三种结果中任意挑出两种,例如前两种,称被它们包围起来的阴影部分为A和B。现在回到原始的图中,每个面都分别有“在A内外”和“在B内外”的总共2×2=4种状态。将这样的状态全部标出之后看起来就是这样的:

仔细看可以发现,任意两个相邻的区域的状态都不一样。这是因为,两个相邻区域之间相隔的边总是青色、粉色或者黄色。如果两个区域相隔青色边,那么由于青色边总是B多边形的边界,它们的B状态就不一样。如果两个区域相隔粉色边,那么由于这是一条A边界,它们的A状态就不一样。如果两个区域相隔黄色边,那么同理它们的A、B状态就都不一样。由于这样的状态正好是四种,所以把字母替换成颜色,就能自动得到图的4-染色:

有了颜色,这里隐藏的另一个对称性就明显许多了:考虑先从面的4-染色着手,构造边的3-染色。那么可以发现,如果一条边相邻的两个面都不是白色,那么这条边就是这两个面的加色。如果一条边相邻的其中一个面是白色,那么这条边就是另外一个面的补色。用更晦涩的术语描述的话,这样的一对边-面染色过程就等价于克莱因4-群上所有非单位元的乘作用。

确实如此,我们马上就可以证明出面的4-染色和边的3-染色其实是等价的。只需要证明的是这样构造出的边3-染色能使得两个同色的边不会出现在同一个顶点上即可。反过来假设存在这样的同色边u和v,那么由于每个顶点只连接了3条边,这两条u和v一定连在同一个面M上。根据染色规则,由于u和v同色,那么在u和v另外一边的剩下两个面也同色,这是不可能的。

这个四色定理的证明看似完美,但是我们还没说明为什么一定会存在这样的边3-染色。根据我自己的查证,泰特并没有给出染色的逐步过程,也许他是觉得先给出任意的边4-染色或者5-染色、然后再通过肯普交换(见上一期)就可以消掉其中一种或两种颜色吧;由于没有记载下来,他的思路我不得而知。事实上,给任意每个顶点连3条边的平面图构造边的3-染色并不简单,比如我们可以证明出下面的这张图就不存在边3-染色:

图片来源:维基百科

这个图中总共有16个顶点和24条边,因此如果存在3-染色,那么每种颜色都会占满16个顶点,也即每种颜色都包含8条边。但是图中任意画出8条边,总会有其中两条边在某一个顶点处相遇(试试看),因此想要的染色也不存在。

这个图不能构成泰特证明的反例,因为图中正中心的边并没有分隔开两个不同的区域。但是这也说明了,不花一些功夫用到图的更多性质是构造不出满意的染色方案的。上回说到,肯普的证明从1879到1890的11年才被希伍德提出有效质疑。而泰特于肯普后一年1880提出他的证明之后,也过了11年,在肯普被质疑之后的1891年被朱利叶斯·彼得森(Julius Petersen)提出有效质疑。说起彼得森,就不得不提到著名的彼得森图,它除了不是个平面图以外、满足构成泰特的反例的所有性质:

图片来源:维基百科

彼得森图虽以彼得森命名,但是实际在1886的发现者是我们熟悉的肯普先生。自从这个图的性质被彼得森于1898年发表以来,它至今不断充当着诸多图论和组合学里伪命题的反例。

我们说回到泰特。在他的证明被驳回后,他重新着手考虑起一类叫做哈密顿图的图。假设从一个图的其中一个顶点出发,沿着图里的各个边行走。如果可以造访图里的所有顶点各恰好一次,还能在旅途的最后回到开始的定点上,那么这样的图就叫做哈密顿图,走过的路径就叫做哈密顿回路。例如,最开始的边3-染色里,每个阴影多边形的边界都是图的一条哈密顿回路。

那么假设我们有了一个哈密顿图,接下来首先证明图里一定有偶数个顶点。由于我们假设过每个顶点都连有3条边,而每条边连有2个顶点,那么把所有的边都劈成两半,每半分给其中一个顶点,那么图就被分解成了每个顶点连有3/2条边的许多Y字形,因此边的数量和顶点的数量的比也是3:2。所以由于顶点占了比例的其中两份,总顶点数也一定是个偶数。

下一步是找到任意一条哈密顿回路。由于图中总共有偶数个顶点,回路里也一定有偶数个顶点,因此也一定有偶数条边,因为它是一个多边形。用两种颜色交替地给回路的边染色之后,把图的剩下所有边染上第三种颜色,就能得到边的3-染色。这是因为,每个顶点都在哈密顿回路里,所以总会先被染上回路的两种不同颜色,然后再被染上第三种。这样就得到了,所有哈密顿图都满足四色定理。

由于哈密顿图在图论里足够常用,人们发现了许多判断图是不是哈密顿图的根据,例如:
• 所有正多面体都是哈密顿图;
• 有至少5个顶点的平面图,如果去掉任意3个顶点之后仍然是连通的,那么这是一个哈密顿图(Tutte 1956);
• 有n个顶点的图,如果每条边连接的两个顶点各自所连的边数之和大于等于n,那么这是一个哈密顿图(Ore 1960);
• 如果一个平面图中有且只有一个面的边数不是3k+2型的整数,那么这不是一个哈密顿图(Grinberg 1968);
等等。

泰特写道,凭一己之力无法证明是不是所有每个顶点连有3条边的平面图都是哈密顿图,也即是不是哈密图的情况涵盖了所有情况。威廉·图特(William Tutte)在1946年找到了反例:

图片来源:维基百科

图中用的三个小部分意味着任何哈密顿路径必须经由图正中心的三条边造访图正中心的一个顶点(试试看),而这是不可能的。

由于泰特无法解决非哈密顿图的情况,他对四色定理证明的追寻也无功而返。当然,由于阿佩尔和哈肯在1976年的证明(见上一期),我们现在也知道了任意这样的平面图都存在边的3-染色。而泰特等众人在寻找证明途中贡献的诸多思想,在二十一世纪的今天也推动着数学里许多领域的发展。

 


主要参考文献:

Lena Folwaczny, The Four Color Theorem.

Thomas Saaty, Thirteen Colorful Vairations on Guthrie’s Four-Color Conjecture.

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注