平面图

两道古怪谜题开场：三座狗屋与三户人家，每座狗屋到每户人家修一条路，路不能交叉——能吗？五只 quadrapus（形似章鱼，章鱼八臂、它只有四臂）要两两握手，手臂还不许交叉——能吗？翻译成图论：前者的图是 K₃,₃（完全二部图），后者是 K₅（5 顶点完全图）。答案都是"不能——但差一点！"：从任一图中删掉一条边，立刻就能无交叉地画在平面上。

精确的定义用"递归数据类型"完成（定义 13.2.2：平面嵌入 = 一组闭合 walk 作为离散面，基例单顶点，构造 = "分裂一个面"与"加一条桥"）——第 7 章的结构归纳在这里全面接管几何直觉。收获是三个大定理：

"边不交叉"的直觉定义（13.2.1）靠光滑曲线和拓扑——要证定理得先修一学期点集拓扑。原书的解法：把平面图重定义成递归数据类型。平面画法把平面切成连续面；每个连续面的边界是图里的一个闭合 walk，叫离散面。原书 Figure 13.6 的 K₄ 嵌入有 4 个离散面（式 13.1）：

只有两种并发症：桥（bridge）= 割边，它在同一个离散面的边界里出现两次（如 Figure 13.7 的外侧面 abcefgecda）；dangle = 桥组成的树，每条边"一来一回"出现。Definition 13.2.2 的递归定义只有三条：基例单顶点（一个长 0 的闭合 walk）；分裂一个面（γ = α⁓β 中两个不相邻点 a、b 之间加边，γ 替换为 α⁓⟨b—a⟩ 与 ⟨a—b⟩⁓β）；加一座桥（两个嵌入各选一个起于端点的面，缝合新面 γ⁓⟨a—b⟩⁓δ⁓⟨b—a⟩）。第 7 章的结构归纳从此全面接管——13.2.4 还解释了"外面"根本不存在：把图画在球面上，任何面都能被戳成外面。

平面嵌入把平面切成若干面（faces）。数一数顶点 v、边 e、面 f——三者被一条恒等式焊死。三个平面图，请亲手数：

由欧拉公式 + "每边恰出现在两个面的边界" + "每个面边界长 ≥ 3"（二部图则 ≥ 4），立刻得到平面图的边数天花板：

于是水壶问题（K₃,₃）与 quadrapu 握手（K₅）被"数学处决"：K₅ 有 5 顶点 10 边，但 10 > 3·5 − 6 = 9，违反上界 ⇒ 非平面（推论 13.5.1）；K₃,₃ 是二部图，9 边 > 2·6 − 4 = 8，同样违反 ⇒ 非平面（推论 13.5.4）。而 Kuratowski 定理（13.8.1）更进一步：任何非平面图都包含 K₅ 或 K₃,₃ 作为 minor——这两个"最小障碍"是全部非平面性的种子。

第一章预告的四色定理太重（需要计算机验证构形），但 5 色足够有初等证明。三个台阶：① 平面图必有度 ≤ 5 的顶点（引理 13.6.3：否则 e ≥ 3v 违反上界）；② 删点/合并相邻点保持平面性（引理 13.6.1/13.6.2）；③ 强归纳 + 一个绝妙的 merge 技巧（度恰为 5 时，五个邻居中必有两个不相邻——合并它们、五染色、展开归位）。逐步看：

13.7正多面体只有五种

把多面体放进球面投影成平面图，握手引理给出 mv = 2e 与 nf = 2e（m = 每个顶点的棱数，n = 每个面的边数），代入欧拉公式得到著名的约束：

穷举可行解——正多面体只有五种：

本章选 K₅ 与 K₃,₃ 当主角，不是因为狗屋，而是因为 Kuratowski 定理（13.8.1）：图非平面 ⟺ 它包含 K₅ 或 K₃,₃ 作为 minor。minor（Definition 13.8.2）= 反复使用三种操作化简得到的图：删点、删边、合并相邻顶点。原书给了个热身例（Figure 13.16）：C₃ 是左图的 minor——注意 C₃ 是连通图 G 的 minor ⟺ G 不是树。亲手走一遍这六步：

两道原书 Practice Problem 做成解题器。

八题，覆盖 13.1–13.8。