五色定理

归纳基础。若 $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$ 对每个平面图都成立。