首先考虑对一个给定的图 G,对他的点进行染色,使得任意一条边的两个顶点不同色。我们把满足条件的最小的所需颜色数目叫做 chromatic number,记为
。
同时我们把图 G 中包含的最大完全图子图的点的数目叫做 clique number,记为
。很容易发现,一个 n 个点的完全图由于点两两相邻,至少需要 n 种不同的颜色。于是我们有如下结论:
Simple Observation:
由于我们更关心染色数的上界,到这里我们就会问,有没有
?很遗憾。。
Naive Conjecture:
Answer: False !
我认为百分之 80 的民科的证明就错在这里了:如果一个图不包含
即五个点的完全图为子图,不能得出这个图可以用四种颜色染色。
这里给一个例子:如下图考虑
,该图不包含
,因此
,但是
。
![](https://picx.zhimg.com/v2-581b7df49a92b2b69ff319304bdfa83e_720w.png?source=8673f162)
那么 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 指的是“商”去给定的边:将这条边的两个点粘合成一个并且保持所有和其他点的相邻关系(如下图)
![](https://picx.zhimg.com/v2-aa9a5f1d44743f1f9caac1043d356b22_720w.png?source=8673f162)
如果图 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 再连上对径点。
![](https://pic1.zhimg.com/v2-49a7ebea641afc26762a85e17c3c2d90_720w.png?source=8673f162)
严格的说上图是 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 绝对是巨大的推进,发个四大不是问题。