图着色与四色定理

这是四色定理之前容易得多的热身:它只用到初等归纳法和一个巧妙的局部换色技巧(肯普链),不需要计算机辅助,读者可以逐步手工验证。

归纳基础。若 $G$ 至多有5个顶点,给每个顶点分配不同颜色;这样至多用5种颜色,结论成立。

归纳步骤,准备工作。假设每个顶点数少于 $n$ 的平面图都可5着色,设 $G$ 是有 $n$ 个顶点的平面图。每个简单平面图都满足 $E \le 3V - 6$(该边数上界由欧拉公式证明),故所有顶点度数之和至多为 $2(3n-6) = 6n-12$,小于 $6n$。因此平均度数小于6,于是存在某个顶点 $v$ 度数至多为5。

去掉 $v$ 得到一个更小的、有 $n-1$ 个顶点的平面图;由归纳假设它有一个合法的5着色。若 $v$ 至多有4个邻居,这些邻居至多用了4种颜色,于是给 $v$ 留下一种自由颜色,证毕。

剩下的情形是 deg$(v) = 5$ 且5种颜色在 $v$ 的5个邻居中各恰好出现一次。按平面图中围绕 $v$ 出现的循环顺序,把这些邻居依次称为第一、第二、第三、第四、第五个,分别染色1、2、3、4、5。考虑由所有染色1或3的顶点构成的子图 $H_{1,3}$。若第一个邻居与第三个邻居位于 $H_{1,3}$ 的不同连通分量中,则在含第一个邻居的分量内交换颜色1和3;由于只涉及染色1或3的顶点,这仍是合法着色,此时第一个邻居变为颜色3,于是颜色1可用于 $v$。

否则第一个邻居与第三个邻居位于 $H_{1,3}$ 的同一连通分量中,由一条颜色1、3交替的路径相连。这条路径连同 $v$ 及通向第一、第三个邻居的两条边,在平面上围成一个闭合圈,(由约当曲线定理,并因围绕 $v$ 的循环顺序为第一、第二、第三、第四、第五)将第二个邻居与第四个邻居分隔开。因此不存在颜色2、4交替的路径连接第二个邻居与第四个邻居,因为这样的路径必须穿过颜色1-3的闭合圈。于是在含第二个邻居的 $H_{2,4}$ 分量内交换颜色2和4;这就为 $v$ 腾出了颜色2。

无论哪种情形,$v$ 都能获得5种颜色之一且不与任何邻居冲突,从而把 $G$-v 的着色扩展到整个 $G$。由归纳法,$\chi(G) \le 5$ 对每个平面图都成立。

这解答了弗朗西斯·格思里1852年提出的原始地图着色问题:任何平面地图始终只需四种颜色就够了,且这个界是紧的,因为某些平面图(例如四个区域两两相邻的地图)确实需要用满全部四种颜色。

归约为最小反例。若定理不成立,取一个需要5种或更多颜色、顶点数尽可能少的平面图。在保持平面性的前提下增加边只会使所需颜色数增多不会减少,因此这个最小反例可以假设是一个极大平面图(三角剖分),其中每个面(包括外部面)恰好由3条边围成。

放电法准备。给每个顶点 $v$ 分配初始电荷 $6 - \deg(v)$。结合 $V - E + F = 2$ 以及 $2E = \sum_v \deg(v)$ 和 $3F \le 2E$(每个面至少有3条边),所有顶点上的电荷总和恰好等于 $12$,因而严格为正。放电法随后按照一套固定规则在相邻顶点间局部转移电荷,而不改变这个总和;分析放电后正电荷必然残留在何处,可以证明图中某处必定出现某个低度顶点及其特定邻域模式。这有限多种模式称为不可避配置,因为每个平面三角剖分中至少会出现其中一种。

可约性。称一个配置是可约的,是指每当它出现在假设的最小反例中时,通过删去或收缩该配置所得较小图的任何4着色,总能重新扩展为整个图的4着色,这与最小性矛盾。Appel和Haken于1976年用计算机验证了他们列出的1936个不可避配置(后于1997年被Robertson、Sanders、Seymour和Thomas精简为633个)全部都是可约的,共耗费一千多个小时的计算机时间。这使四色定理成为第一个证明本质上依赖机器计算的重大定理,此后又被独立重新验证,并于2005年由Gonthier在Coq证明助手中逐行进行了形式化核验。

结论。由于每个不可避配置都是可约的,最小反例不可能存在:没有平面图需要5种或更多颜色,因此对任意平面图 $G$ 都有 $\chi(G) \le 4$。