如何在理论上解释「四色定理」？ 第1页

首先考虑对一个给定的图G，对他的点进行染色，使得任意一条边的两个顶点不同色。我们把满足条件的最小的所需颜色数目叫做chromatic number，记为 。

同时我们把图G中包含的最大完全图子图的点的数目叫做clique number，记为 。很容易发现，一个n个点的完全图由于点两两相邻，至少需要n种不同的颜色。于是我们有如下结论：

Simple Observation:

由于我们更关心染色数的上界，到这里我们就会问，有没有 ？很遗憾。。

Naive Conjecture:
Answer: False !

我认为百分之80的民科的证明就错在这里了：如果一个图不包含 即五个点的完全图为子图，不能得出这个图可以用四种颜色染色。

这里给一个例子：如下图考虑 ，该图不包含 ，因此 ，但是 。

那么chromatic number能不能被clique number控制住呢？

Advanced Conjecture:
Answer (by Erdos, 1959): False !

实际上Erdos构造了clique number固定，但chromatic number任意大的图(Erdos-Renyi Graph)。也就是说在四色定理的证明中，试图从图中包含的完全子图的大小来讨论，是行不通的。更一般的，我们把满足 的图（并且所有induced子图也满足）叫做perfect graph。对于这种图我们有更精细的结构：定义如果一个图G不包含长度大于5的odd cycle和它的complement，我们称这个图Berge。

Strong Perfect Graph Theorem (Chudnovsky, Robertson, Seymour, Thomas):

现在我们从structure graph theory的角度去看四色定理。delete an edge指对G删去给定的边，contract an edge指的是“商”去给定的边：将这条边的两个点粘合成一个并且保持所有和其他点的相邻关系（如下图）

如果图H可以通过对G deleting和contracting一些边得到，我们就说H是G的minor。可以发现minor关系是包含子图这个关系的推广：H是G的子图，那么H也是G的minor。

Graph Minor Theorem(Robertson, Seymour):

上面深刻的定理同时告诉我们，当图G对于给定的图H minor-free时，具有清晰的结构。具体定理的叙述太长这里就不说了，目前这个图结构引理的最新证明由Kawarabayashi, Thomas, Wollen在2016年简化到了100页以内。图的结构问题是图论中最困难的问题之一，有了图的结构，我们就可以考虑图上的染色问题了。比如对于一个没有 minor 的图，我们有Wagner's Theorem，即G是由planar graphs和 经过clique sum of order at most 3得到的（如图），其中 指的是8个点的cycle再连上对径点。

严格的说上图是H minor-free的图，里面的漩涡是vortices。不过如果忽略漩涡，把洞当作 ，还是可以看作是 minor-free的图示的。

上面讲的structure内容看似和四色定理没什么关系。再让我们回到最开始举的 反例上：我们给它的5个点编号1到5，如果我们contract边12和边34，我们得到了 ，也就是说 是 的minor。这看起来也解释了 不能被 控制这个看似矛盾的现象：对于一个图G，如果 是它的minor，说明图G中有t个不相交的子集，分别contract掉它们我们可以得到 。那么对于那些子集，如果对所有子集我们首尾的点染色相同，那我们相当于在对 染色；否则我们就要求子集的首尾染色不同，相当于多了限制条件。换句话说，就算图G连 都不包含，但是如果它有 minor，那么有可能这个图需要至少t种不同的颜色。

很自然的，我们可以提出下面图论中最深刻的猜想：

Hadwiger's Conjecture:

配合planar graph的经典定理：

Kuratowski's Theorem:

我们可以发现，四色定理实际上是Hadwiger's Conjecture的t=4时的特殊情况。目前对这个猜想的进展如下：

Trivial

Hadwiger, 1943

By computer, 1976 （即 四色定理）

Robertson, Seymour, Thomas, 1993

Open

注意到Robertson, Seymour and Thomas对t=5情形的证明没有用电脑，但是用到了四色定理的结论。如果有一天有人可以证明 Hadwiger's Conjecture，绝对是组合数学里面最大的新闻了。目前这个猜想大家都认为是对的，但是我们目前的工具不够深刻。

做为结束，还是回到四色定理。四色定理有没有不依赖计算机的证明？答案是没有，不过目前已经可以通过计算机在10秒内证完了。如果得到了四色定理不依赖计算机的证明，对Hadwiger's Conjecture绝对是巨大的推进，发个四大不是问题。