Something about 四色猜想

许进老师《现代图论》课中所讲授的四色猜想的相关内容.

基础知识

这里只讨论有限平面图,且无自环、重边.

一些相关概念介绍如下(图的定义、Euler公式、Kuratowski定理等不再赘述):

图的染色(着色) 给图的顶点赋权(一般为整数,当然,不是整数也可以强行调整为整数...),相邻顶点不同权.

四色猜想 任意平面图都是可以 \(4\)-染色的.

导出子图 设有图 \(G=(V,E)\),及其顶点集的子集 \(V'\subset V\),记 \(E'=\{(u,v)\in E:u,v\in W\}\),则称 \(G'(V')=(V',E')\)\(V'\) 的导出子图.

  • 随便举个例子吧:\(K_n\) 的任意 \(m\) 元子集的导出子图都是 \(K_m\). (当然,\(m\leqslant n\) ...)

极大平面图 顾名思义,就是边已经多到极限的平面图,以至于再加一条边,它就不是平面图了.

  • 极大平面图又称三角剖分图,其每个面都是三角(二维单形就是三角,课上许老师没有提单形的故事,但其实单形剖分是在任何维度存在的);
  • 任何一个图都可以通过不断加边而变成一个极大平面图。

符号说明

  • \(n\):点数;
  • \(m\):边数;
  • \(\delta\):图中顶点的最小度数.

关键术语:

  • Kempe 链:只含两种颜色的链.
  • Kempe 变换:一种通过换色来减少颜色的技巧.

Kempe 的证明思路

用数学归纳法:

  • 容易验证 \(n\leqslant 5\) 时,所有的极大平面图都可以被 \(4\)-染色.
  • \(n\leqslant p\) 时,所有 \(n\) 个顶点的极大平面图都可以被 \(4\)-染色,考虑 \(p+1\) 的情. 由 Euler 公式可知,对于极大平面图,有 \(3\leqslant \delta\leqslant 5\),故分三种情况讨论:
    • \(\delta=3\)delta=3情形 由于 \(\delta=3\),故必定会存在一个 \(3\) 度顶点,即有图中所示的结构. 记 \(G'=G-D\),则 \(|G'|=p\),因而可以被 \(4\)-染色. 而 \(D\) 相邻的 \(A,B,C\) 点也至多占掉三种颜色,故此时的图 \(G\) 是可以被 \(4\)-染色的.
    • \(\delta=4\)delta=4情形 同上,会存在一个图示的结构,记 \(G'=G-E\),则 \(G'\) 有一个 \(4\)-染色. 若 \(A,B,C,D\) 只用了至多 \(3\) 种颜色,则可以完全沿用上述方法. 因此只讨论 \(A,B,C,D\) 分别用了颜色 \(1,2,3,4\) 的情形. 此时采用的办法被称为 Kempe 变换
      考虑 \(G'\) 中,颜色 \(1\)\(3\) 的导出子图 \(G'[1,3]\)
      • \(A\)\(C\) 不在 \(G'[1,3]\) 的同一个连通分支内,则可以将其中一者(不妨设是 \(A\))所在的连通分支上的 \(1\)\(3\) 全部交换,该种转换不会产生颜色的冲突. 转换完毕后,\(A\)\(C\) 将变为同色,即 \(A,B,C,D\) 只占三种颜色;
      • \(A\)\(C\)\(G'[1,3]\) 的同一连通分支内,则必定存在一条连接 \(A\)\(C\)\(1-3-1-3-\cdots\) 路径(这样的路径称为 Kempe 链). 此时考虑 \(G'[2,4]\),则 \(B\)\(D\) 一定不在 \(G'[2,4]\) 的同一连通分支内(有点像 Jordan 闭曲线定理的那种感觉,\(B\)\(D\) 一个在内一个在外),即可以对 \(G'[2,4]\) 做变换,此时也可转换为 \(A,B,C,D\) 只占三种颜色的情形.
    • \(\delta=5\)delta=5情形 同样会存在一个图示的结构,记 \(G'=G-F\),则 \(G'\) 存在一个 \(4\)-染色. 若 \(A,B,C,D,E\) 只用了至多 \(3\) 种颜色,则很容易给出该种情形的一个 \(4\)-染色. 当 \(A,B,C,D,E\) 恰好用了 \(4\) 种颜色时,必定有且仅有两个顶点同色,不失一般性,设 \(f(A)=1,f(B)=f(E)=2,f(C)=3,f(D)=4\). 此时考虑 \(G'[1,3]\)\(G'[1,4]\)
      • \(A,C\)\(A,D\) 至少有一对在相应的导出子图上不连通,则可以直接采取换色的方式消灭掉颜色 \(1\),此时在 \(G\) 中给 \(F\) 染颜色 \(1\) 即可.
      • \(A,C\)\(A,D\) 在相应的导出子图上都连通,则在 \(G'\) 中存在一条连接 \(A,C\)\(1-3-1-3\cdots\) 链和一条连接 \(A,D\)\(2-4-2-4\cdots\) 链,分别将 \(B\)\(E\) 包围. 故类似 \(\delta=4\) 的情况,不难发现此时不存在 \(E\to C\)\(B\to C\) 的 Kempe 链,因而进行两次换色,即可将颜色 \(2\) 消除. 进一步给 \(F\) 染颜色 \(4\) 即可得到 \(G\)\(4\)-染色.

听起来很简单,不是吗?但很遗憾这个证法是错误的. 错误的关键就在于:虽然图中有一条 \(A\to C\) 和一条 \(A\to D\) 的 Kempe 链,但这两条链可能在处 \(A\) 点之外的其他地方也有交点,这可能会导致我们在后面消除颜色 \(2\) 的换色过程中失败.

听起来好绕啊!那就详细说说...

\(\delta=5\),且 \(|f\{A,B,C,D,E\}|=4\),且 \(A,C\)\(G'[1,3]\) 中连通,\(A,D\)\(G'[1,4]\) 中连通时,我们需要进行两次换色:

  1. \(G'[2,3]\) 中,将 \(E\) 所在的连通分支中的所有 \(2\)\(3\) 对换,即可将 \(E\) 换为颜色 \(3\).
  2. \(G'[2,4]\) 中,将 \(B\) 所在的连通分支中的所有 \(2\)\(4\) 对换,即可将 \(B\) 换为颜色 \(4\).

两次换色后,\(A,B,C,D,E\) 的颜色分别为 \(1,4,3,4,3\),成功减少了一种颜色!

那么,问题出在哪里呢?

就是上述过程中,第一次换色完全可能影响到第二次换色.

试想,如果第一次换色使得 \(B\)\(D\)\(G'[2,4]\) 中连通了怎么办?第二次换色就无法进行了!!那我们构造 \(G\)\(4\)-染色的计划就失败了(

那么,什么情况会导致第二次换色失败呢?

我们要让第一次和第二次换色产生关系. 因此我们努力让它们换色的前提产生关系. 那就是说,我们要让 \(A\to C\) 的 Kempe 链与 \(A\to D\) 的 Kempe 链在 \(A\) 以外的一点相交,这样两次换色就可以互相干扰了.

事实上,Heawood 给出的反例正是应用了这个思路. 其具体的反例如下图所示:

Heawood 的反例


虽然 Kempe 没有成功证明四色定理,但 Kempe 的工作仍然是非常有意义的,在其做法的基础上稍加改动,即可证明比四色定理稍弱的五色定理. 后来 Appel–Haken 对 Kempe 变换失效的不可约情形进行了研究,并利用计算机给出了证明.

对 Kempe 工作的进一步思考

既然两条 Kempe 链相交会导致 Kempe 变换失效,那么我们就需要寻找不相交的 Kempe 链.

Mr. Xu 的猜想! 对于 \(\delta=5\) 的情形,对任意一个 \(5\) 度顶点 \(v_0\)\(N(v_0)=\{v_1,v_2,v_3,v_4,v_5\}\)),都存在 \(G'\) 的一种染色方案 \(f\),s.t. 存在 \(v_1\to v_3\)\(v_1\to v_4\) 两条 Kempe 链,且这两条链仅在 \(v_1\) 相交.

若能证明这个猜想,那当然能修复 Kempe 的证明.(不过我8太看好...

  • 貌似 Heawood 的图中,中心的 \(5\) 度顶点就根本不行...
  • 我始终觉得这个猜想只需要存在性就行了(存在一个 \(5\) 度顶点...),但 Mr. Xu 课上说的的确是任意... 迷惑...