Lecture 10: Graphs II（图论进阶）

目录 · ← l10 · l12 →

Lecture 10: Graphs II（图论进阶）

概述

上一讲把「图」抽象成了对象与关系的数学模型，并用度数论证解决了柯尼斯堡七桥问题（Eulerian tour）。本讲要回答一个更”几何”的问题：一个图画在纸上，最少需要多少”交点”？ 这就是平面性（planarity）问题。核心工具是欧拉公式 $V - E + F = 2$，由它推出的两条边数上界 $E \le 3V-6$ 与 $E \le 2V-4$ 将一举证明 $K_5$ 与 $K_{3,3}$ 不能无交叉地画在平面上。

本讲的第二个主题是「图上的归纳法（Graph Induction）」——这是 Fall 2026 日程中与 Stable Matching 并列的独立主题（Quiz 5 会考）。它的困难之处在于：删掉一个顶点后图可能不再连通，于是归纳假设没法直接用在整体上，必须改用强归纳（strong induction）或在每个连通分量上分别归纳。这一节我们把「树的边数是 $V-1$」这个命题完整证穿，作为图归纳的范式。

第三个主题是三类重要图：完全图（complete graph）$K_n$、树（tree）、超立方体（hypercube）$Q_n$。它们分别代表”极大连通 / 极小连通 / 兼顾鲁棒与稀疏”三种设计哲学，也是后续计数、概率、算法课程里反复出现的对象。

核心概念的直观解释

平面图（Planar Graph）

• 定义：若图 $G=(V,E)$ 能够画在平面上，使得任意两条边只在公共端点处相交（除了端点之外没有任何交叉点），则称 $G$ 是平面图。这样的画法称为 $G$ 的一个平面嵌入（planar embedding）。
• 直观解释（”它是什么意思？”）：把顶点想成图钉，边想成绷紧的橡皮筋。平面图就是”你能把图钉钉在木板上，用橡皮筋按边连接，且橡皮筋彼此不相碰”的图。关键在于：平面性是图自身的性质，不是某一张画法的性质。 一张画得有交叉的图完全可能是平面图——只要存在某种画法没有交叉就行。类比：一件衣服”能不能熨平”取决于布料本身，而不取决于你随手揉成一团的样子。
• 具体示例：$K_4$（4 个顶点的完全图）如果画成”正方形 + 两条对角线”，交叉 1 次；但把第 4 个顶点放到三角形内部，从它连三条边到三个顶点，就完全没有交叉。所以 $K_4$ 是平面图（而且 $E=6=3\cdot 4-6$，恰好取到上界）。反之，$K_5$ 无论怎么画都必然有交叉——这是本讲要证的第一个硬结论。

【K4 的两种画法：同一个图，平面性相同，画法不同】

  画法一：正方形 + 两条对角线       画法二：顶点 4 放进三角形内部
  （有 1 个交叉点，不好）            （零交叉，好！这就是平面嵌入）

      1 ----------- 2                    1 ----------- 2
      | \         / |                     | \         / |
      |   \     /   |                     |   \  4  /   |
      |     X     |   <- 交叉           |     \ /     |
      |   /     \   |                     |      X      |   <- 4 在内部
      | /         \ |                     |     / \     |
      4 ----------- 3                     |   /     \   |
                                          4 ----------- 3
  V=4  E=6  F=4                        V=4  E=6  F=4
  （4 个面：3 个三角形 + 外部面）      V-E+F = 4-6+4 = 2  OK

面（Face）与外部面（Outer Face）

• 定义：给定平面图的一个无交叉画法，平面被这些边分割成的连通区域称为面；其中唯一无界的那个面称为外部面（outer face），其余为内部面。面数记作 $F$。一个面的边数（sides）$s_i$ 是沿该面边界顺时针走一圈经过的边数；若一条边两侧是同一个面（这样的边称为桥 (bridge)），它会被重复计数。
• 直观解释：面就是”地图上的国家”。外部面是”包围整个地图的海洋”。一个国家如果只有一座桥与外面相连，那么这座桥在这个国家的边境上要走两次（进去再出来），所以 $s_i$ 是”走一圈的步数”而不是”不同边的条数”。
• 具体示例：三角形 $K_3$ 的平面画法把平面分成 2 块：三角形内部（1 个面，3 条边）和外部（1 个面，3 条边），所以 $F=2$，两个面的 $s_i$ 都是 3，总和 $6 = 2E = 2\cdot 3$。而一棵 4 个顶点的星形树（一个中心连 3 个叶子）完全不分割平面，只有 1 个外部面，它走一圈要经过每条边两次：$s_1 = 2E = 6$，$F=1$。

欧拉公式（Euler’s Formula）

• 定义：对任意连通平面图，设顶点数 $V$、边数 $E$、面数 $F$（含外部面），则

• 直观解释（”它是什么意思？”）：这是一个”会计恒等式”。每加一条边，要么多消耗一个顶点（$V$ 与 $E$ 同增，差不变），要么把某个面一分为二（$F$ 与 $E$ 同增，差不变）。所以 $V-E+F$ 在”建图”过程中始终不变，而空图（$V=1,E=0,F=1$）时为 $2$。历史上古希腊人知道它对多面体成立却证不出来——因为他们试图对多面体做归纳，但”多面体减去一个顶点”不再是多面体。欧拉的洞察是：必须把定理推广到平面图这个更大的类，归纳法才能施展。
• 具体示例：立方体（$Q_3$）的平面画法：$V=8$，$E=12$，$F=6$（6 个正方形面），$8-12+6=2$ ✓。正八面体：$V=6,E=12,F=8$，$6-12+8=2$ ✓（八面体与立方体互为对偶，$V$ 与 $F$ 恰好互换）。

细分（Subdivision）与库拉托夫斯基定理（Kuratowski’s Theorem）

• 定义：把图 $G$ 的某条边 $e=\{u,v\}$ 替换成一条经过新顶点 $w$ 的长度为 2 的路径 $\{u,w\},\{w,v\}$，称为对 $e$ 做一次细分。反复细分得到的图叫 $G$ 的一个细分图。
• 直观解释：细分就是”在橡皮筋中间多钉一颗图钉、把橡皮筋折一下”。它不改变图能否被画平的结论（多一个拐弯不会制造或消除本质的交叉），因此”是否含有 $K_5$ 或 $K_{3,3}$ 的细分”就成了非平面性的判据。
• 具体示例：把 $K_5$ 的一条边细分一次，得到 $V=6,E=11$ 的图。它满足 $E\le 3V-6$（$11\le 12$），看起来”通过了平面性检测”，但它依然是非平面的——因为它含有 $K_5$ 的细分。

树（Tree）

• 定义：连通且无环（acyclic，不含任何 cycle）的无向图称为树。
• 直观解释（”它是什么意思？”）：树是”最小连通”的图——刚好够把所有顶点串起来，一条多余的边都没有。它是通信网络里最省线的拓扑：路由表最简单（任意两点间只有唯一一条路径，不会绕圈），代价是毫无冗余——断一条边就断成两半。类比：树像一棵没有环的分叉家族树，也像”只能用最少的桥把若干岛屿全部连通”的方案。
• 具体示例：$V=4$ 的树必有 $E=3$ 条边。星形树 $K_{1,3}$（中心连 3 个叶子）、路径 $P_4$（一条链）、以及”Y 形”都是树；而 $K_4$ 不是树（有环），$C_4$（4 环）不是树（有环），”两个不相连的点”不是树（不连通）。

超立方体（Hypercube）$Q_n$

• 定义：$n$ 维超立方体 $Q_n$ 的顶点集为 $V=\{0,1\}^n$（所有 $n$ 位二进制串）；两个顶点 $x,y$ 相邻当且仅当它们恰好有一个坐标不同（即汉明距离 (Hamming distance) 为 1）。
• 直观解释（”它是什么意思？”）：把每个 $n$ 位串看成一个网络节点的”地址”，只有一位不同（比如 $00110$ 与 $00111$）的节点之间才有直连线路。这样每个节点只需 $n$ 条线路（度数低、布线成本小），但任意两个节点之间的距离最多 $n$（走 $n$ 步逐位翻转即可到达），所以又很”扁”又很”通”。这正是 1980 年代 Thinking Machines 公司 Connection Machine 采用 20 维超立方体连接百万处理器的原因：完全图要 $10^{12}$ 根线，超立方体只要约 $2^{20}\cdot 20/2 \approx 10^7$ 根。
• 具体示例：$Q_1$ 就是一条边（$0-1$）；$Q_2$ 是一个正方形（$00,01,11,10$）；$Q_3$ 是普通立方体的骨架图，$V=8$，每个顶点度数 3，$E=12$。

图上的归纳法（Graph Induction）

• 定义/范式：对图的某个参数（通常是顶点数 $n$ 或边数 $m$）做归纳：先证基础情形，再取 $n+1$ 个顶点的图 $G$，删掉一个顶点 $v$ 得到 $G^{\prime}$，对 $G^{\prime}$ 用归纳假设，最后把 $v$ 加回去、分析它带来多少边/面。
• 直观解释：图归纳的危险在于删点会破坏连通性。$G^{\prime}$ 可能裂成 $t$ 个连通分量 $G^{\prime}_1,\dots,G^{\prime}_t$，这时归纳假设对 $G^{\prime}$ 整体无效（它不连通），必须分别对每个分量用——而且分量顶点数都严格小于 $n$，所以要用强归纳（假设对所有 $1 \le n \le k$ 成立），而不是弱归纳。
• 具体示例：$G$ 是一条路径 $1-2-3-4$。删掉中间的顶点 $2$，$G^{\prime}$ 裂成 $\{1\}$ 和 $\{3,4\}$ 两个分量；删掉端点 $4$，$G^{\prime}$ 仍是连通的路径 $1-2-3$。前者必须强归纳，后者弱归纳即可。这个例子说明”删点位置”决定了证明难度——归纳证明里必须把两种情形都覆盖。

完整证明与推导（核心）

定理 10.1（欧拉公式，Euler’s Formula）：对任何连通平面图 $G=(V,E)$，在其任意无交叉画法下都有

其中 $F$ 为面数（含外部面）。

证明策略：对边数 $e$ 做（强）归纳。选边数而不是顶点数，是因为”加一条边”对 $(V,E,F)$ 的影响有两种清晰形态：要么新增一个顶点（$V$ 和 $E$ 同时 $+1$），要么把某个面劈成两个（$F$ 和 $E$ 同时 $+1$）。两种情况下 $V-E+F$ 都保持不变。这就是官方 Note 采用的路径：先处理树的情形（$F=1, E=V-1$），再对非树图删掉圈上的一条边，用归纳假设回推。

逐步推导：

1. 基础情形 $E=0$：此时图只有一个孤立顶点 $V=1$；平面没有被分割，只有 1 个面 $F=1$。于是 $V-E+F = 1-0+1 = 2$ ✓。（注：$E=0$ 的连通图只能是单点，否则不连通。这个问题还能更宽松地处理：$E=1$ 时 $V=2,F=1$，$2-1+1=2$ ✓，也直接可验。）

2. 归纳假设：设对所有满足 $E^{\prime} \le m$ 的连通平面图，$V^{\prime} - E^{\prime} + F^{\prime} = 2$ 成立。

3. 归纳步骤：取连通平面图 $G$ 有 $E = m+1$ 条边。分两种情形。

   情形 A：$G$ 是树。 树的定义就是连通无环。

   • 先证”树不分割平面，故 $F=1$”：设树有一个环，则平面被分成至少 2 个面；反之，若 $F\ge 2$，则平面被边分割出至少一个闭合的”围墙”，围墙本身就是环。更直接地看：树中每条边都是桥 (bridge)，桥两侧是同一个面，所以整棵树只贡献 1 个面。（用 10.2 的引理也可以严格推出：树叶幕 $\sum s_i = 2E = 2(V-1)$，若 $F \ge 2$ 则 $\sum s_i \ge 3F$……这一步绕远了，我们用”树无环 ⟺ $F=1$”这个更朴素的事实即可。）
   • 再证”树有 $E = V-1$”：这是定理 10.9，将在本小节后面用强归纳完整证明。
   • 代入：$V - E + F = V - (V-1) + 1 = 2$ ✓。

   情形 B：$G$ 不是树。 那么 $G$ 含有一个环 $C$。

   • 取环 $C$ 上的任意一条边 $e$，从 $G$ 中删除它，得到 $G^- = G - e$。
   • $G^-$ 仍连通：因为 $e$ 属于环 $C$，删掉后 $e$ 的两个端点仍可通过环 $C$ 的其余部分连通，其余顶点之间的路径最多绕一下环，依然存在。
   • $G^-$ 的边数为 $m$，故归纳假设适用于它：$V(G^-) - E(G^-) + F(G^-) = 2$，即 $V - (E-1) + F(G^-) = 2$。
   • $F(G^-) = F - 1$：这是关键的一步。边 $e$ 是环 $C$ 的一部分，$e$ 的两侧是两个不同的面（沿 $e$ 一侧走环 $C$ 的一部分、另一侧走 $C$ 的其余部分，两条都不含 $e$，故它们在 $G^-$ 中都是通路，把两侧分开）。删除 $e$ 后，这两个面合并成一个面，面数恰好减 1。（与之对比：若 $e$ 是桥，两侧是同一个面，删掉它面数不变——这正是情形 A 的机制。）
   • 代入：$V - (E-1) + (F-1) = V - E + F = 2$。由归纳假设左边等于 $2$，故 $V - E + F = 2$ ✓。

4. 结论：两种情形都成立，由强归纳，定理对一切连通平面图成立。$\blacksquare$

【证明机制解说】：整个证明的”灵魂”是找到不变量并证明它在两种局部操作下不变。$V-E+F$ 是拓扑学中欧拉示性数的雏形：删掉环上的一条边，”一条边 + 一个面”同时消失，$E$ 与 $F$ 各减 1，和不变；删掉桥，”一条边”消失而面不变，这正是树的特征。更深刻的一层是为什么必须推广到平面图：多面体的面是”多边形”，删掉一条边后可能不再是多面体，归纳法无以为继；而平面图对删除封闭，可以自由地做”删边”操作。这就是笔记里说的”定理太弱导致归纳失败”的经典案例。

反例（条件不可省）：欧拉公式只对连通图成立。看两个孤立的顶点：$V=2,E=0,F=1$，则 $V-E+F=3 \ne 2$。一般地，若连通分量数为 $C$，则正确的公式是

（验证：两个孤立点 $C=2$：$2-0+1 = 3 = 1+2$ ✓；一个三角形加上一个孤立点 $V=4,E=3,F=2,C=2$：$4-3+2=3=1+2$ ✓。）这正是官方 Note 末尾追问的”What happens when the graph is not connected?”的答案。

引理 10.2（面的边数双计数）：对任何平面图（不必连通），设各面的边数为 $s_1,\dots,s_F$，则

证明策略：双计数 (double counting)。分别从”面”和”边”两个方向数同一个量：所有面包围边的”出现次数”总和。

逐步推导：

1. 从面这边数：面 $i$ 沿边界走一圈经过 $s_i$ 条边，所以总和为 $\sum_{i=1}^F s_i$。
2. 从边这边数：任取一条边 $e$，它把平面分成左右两侧（这两侧各自属于某个面）。如果 $e$ 不是桥，两侧是两个不同的面，$e$ 在左边那个面的绕行中被数一次、在右边那个面的绕行中再被数一次，共贡献 2；如果 $e$ 是桥，两侧是同一个面，绕行这个面时 $e$ 会被走两次（进去、出来），同样贡献 2。
3. 所以每条边在总和里恰好贡献 2，总计 $2E$。两个计数结果相等，即 $\sum_{i=1}^F s_i = 2E$。$\blacksquare$

【证明机制解说】：双计数是 CS70 最简单也最万能的技巧之一（讲次 16 会用它对组合恒等式做组合证明）。这里的关键观察是”桥也被数两次”——如果把桥误当成只数一次，就会错误地得到 $\sum s_i = 2E - (\text{桥数})$，后面的所有不等式都会崩掉。

定理 10.3（平面图的边数上界 I）：设 $G$ 是简单（无平行边、无自环）连通平面图，且 $V \ge 3$。则

证明策略：利用”每个面至少由 3 条边围成”，把 $\sum s_i = 2E$ 变成关于 $F$ 的下界，再代入欧拉公式消去 $F$，得到只含 $E$ 与 $V$ 的不等式。

逐步推导：

1. 每个面至少 3 条边。因为 $G$ 是简单图，不存在”两条边围成一个面”的情形（那需要两个顶点之间有多条平行边，或者自环）；也不存在”一条边围成一个面”（自环）。在连通且 $E\ge 2$（从而 $V\ge 3$）的情况下，每个面的边界至少需要一个长度 $\ge 3$ 的闭环，故 \(s_i \ge 3 \quad \text{对一切 } i = 1,\dots,F.\)
2. 由引理 10.2 与上式： \(2E = \sum_{i=1}^F s_i \ge \sum_{i=1}^F 3 = 3F \quad\Longrightarrow\quad F \le \frac{2E}{3}.\)
3. 由欧拉公式 $F = 2 - V + E$。代入上一步： \(2 - V + E \le \frac{2E}{3} \quad\Longrightarrow\quad E - \frac{2E}{3} \le V - 2 \quad\Longrightarrow\quad \frac{E}{3} \le V-2 \quad\Longrightarrow\quad E \le 3V - 6. \qquad \blacksquare\)

【证明机制解说】：这个证明的”灵光一现”是不等式方向的匹配：我们要 $E$ 的上界，所以需要 $F$ 的上界；而 $2E = \sum s_i \ge 3F$ 给出的正是 $F \le 2E/3$。链条是：简单图 ⟹ 面足够”厚”（$s_i\ge 3$）⟹ 面数被边数压住 ⟹ 边数被顶点数压住。这也解释了为什么平面图是稀疏的：$1000$ 个顶点的连通图最多可以有约 $5\times 10^5$ 条边，但平面图被限制在 $999 \sim 2994$ 条之间（$V-1 \le E \le 3V-6$）。

定理 10.4（$K_5$ 非平面）：5 个顶点的完全图 $K_5$ 不是平面图。

证明策略：反证法 + 定理 10.3 的定量上界。假设 $K_5$ 是平面图，则在它身上必须满足 $E \le 3V-6$；但把具体数字代进去会得到一个假的不等式。

逐步推导：

1. $K_5$ 有 $V=5$ 个顶点；每对顶点之间都有边，故 $E = \binom{5}{2} = 10$。
2. 假设 $K_5$ 是平面图。$K_5$ 是简单图且 $V = 5 \ge 3$，故定理 10.3 适用，必须有 $E \le 3V - 6 = 3\cdot 5 - 6 = 9$。
3. 但 $E = 10 > 9$，矛盾。
4. 因此 $K_5$ 不是平面图。$\blacksquare$

另一个更”物理”的写法（直接数面）：假设 $K_5$ 画平了，由欧拉公式 $F = E - V + 2 = 10-5+2 = 7$。每个面至少 3 条边，故 $\sum s_i \ge 3\cdot 7 = 21$；但 $\sum s_i = 2E = 20$。$21 > 20$，矛盾。两种叙述本质相同，后者更直观地暴露”面太多、边不够分”。

【反证法的两条路线，用 K5 走一遍】

  K5: V=5, E=C(5,2)=10, 每个顶点度数 = 4

  +---------------------------------------------------------------+
  | 路线甲（边数上界）：                                          |
  |   假设平面 => 必须 E <= 3V-6                                  |
  |   3*5-6 = 9  而 E = 10                                        |
  |   10 <= 9 ?  FALSE                                            |
  |   => 矛盾，K5 非平面                                          |
  +---------------------------------------------------------------+
  | 路线乙（直接数面）：                                          |
  |   假设平面 => F = E-V+2 = 10-5+2 = 7                          |
  |   每个面 >= 3 条边 => sum(s_i) >= 3*7 = 21                    |
  |   但 sum(s_i) = 2E = 20                                       |
  |   21 <= 20 ?  FALSE                                           |
  |   => 矛盾，K5 非平面                                          |
  +---------------------------------------------------------------+
  | 路线丙（"5 个邻居"的几何论证，教材外的等价说法）：            |
  |   任取顶点 v，它在平面上有 4 个邻居 a,b,c,d。                 |
  |   画一个以 v 为心的"星"：这 4 个邻居绕 v 的圆周排列。         |
  |   a 与 c 之间的边、b 与 d 之间的边，必有一条被"逼"到          |
  |   圆环的另一侧，从而与另一条相交 —— 除非 v 在外部面边界上。   |
  |   但 K5 里每个顶点地位相同，不可能所有顶点都在外部面边界上。  |
  +---------------------------------------------------------------+

  K3,3 的对应版本（必须换用 2V-4 型上界）：
    V=6, E=3*3=9, 二分图 => 无三角形 => 每个面 >= 4 条边
    假设平面 => F = 9-6+2 = 5
    sum(s_i) >= 4*5 = 20  但 sum(s_i) = 2E = 18
    20 <= 18 ?  FALSE   => 矛盾，K3,3 非平面
    即 E=9 > 2V-4 = 8

  K3,3 的 ASCII 画法（三座房子 H1,H2,H3 / 三口井 W1,W2,W3）：
      H1        H2        H3
       \  \  /  |  \  /  /
        \  \/   |   \/  /
         \ /\   |   /\ /
          X  \  |  /  X      <- 9 条边全部跨组，画在平面上必有交叉
         / \  \ | /  / \
        /   \  \|/  /   \
      W1        W2        W3
    度数列：H1,H2,H3 各为 3；W1,W2,W3 各为 3。
    sum(deg) = 6*3 = 18 = 2E  => E = 9  OK（握手引理自检通过）

定理 10.5（平面图的边数上界 II：二分图情形）：设 $G$ 是简单连通二分平面图，且 $V\ge 3$，则

证明策略：与定理 10.3 同样的双计数路线，但把”每个面至少 3 条边”加强为”每个面至少 4 条边“。这一步来自二分图的结构性质：二分图不含奇数长度的环。

逐步推导：

1. 二分图无奇环。设 $G$ 的二部划分为 $V = L \cup R$，所有边都在 $L$ 与 $R$ 之间。沿任意一个环走一圈，每经过一条边就从一个部分换到另一个部分，所以走 $k$ 步回到起点要求 $k$ 是偶数。故所有环长度为偶数。
2. 每个面至少 4 条边。面 $i$ 的边界是一个闭环（长度为 $s_i$）。若 $s_i = 3$，就存在一个长度为 3 的环——即三角形，与二分图无奇环矛盾。若 $s_i \le 2$，如前所述需要平行边或自环，简单图不允许。因此 \(s_i \ge 4 \quad \text{对一切 } i.\)
3. 由引理 10.2： \(2E = \sum_{i=1}^F s_i \ge 4F \quad\Longrightarrow\quad F \le \frac{E}{2}.\)
4. 代入欧拉公式 $F = 2 - V + E$： \(2 - V + E \le \frac{E}{2} \quad\Longrightarrow\quad \frac{E}{2} \le V - 2 \quad\Longrightarrow\quad E \le 2V - 4. \qquad \blacksquare\)

【证明机制解说】：与定理 10.3 相比，这里只是把常数 3 换成 4，但效果是上界从斜率 3 降到斜率 2，收紧了整整一个常数倍。这展示了平面图理论的一个方法论：图的结构限制（二分性、无三角性、最小环长 girth）越强，边数上界越紧。一般地，若平面图的最小环长为 $g$，则 $E \le \frac{g}{g-2}(V-2)$。

定理 10.6（$K_{3,3}$ 非平面）：完全二分图 $K_{3,3}$ 不是平面图。

证明策略：$K_{3,3}$ 的 $V=6,E=9$，代入 $-6$ 型上界会发现它通过了检测（$9 \le 3\cdot 6 - 6 = 12$）。所以必须换用二分图的 $2V-4$ 上界。

逐步推导：

1. $K_{3,3}$ 的顶点分为两组各有 3 个（题面里的”三座房子、三口井”），组间所有 $3\times 3=9$ 条边都存在，组内无边。故 $V = 6$，$E = 9$。
2. $K_{3,3}$ 显然是二分图（取两个组作为二部划分即可），且是简单图，$V = 6 \ge 3$。
3. 假设 $K_{3,3}$ 是平面图，则由定理 10.5 必须有 $E \le 2V - 4 = 2\cdot 6 - 4 = 8$。
4. 但 $E = 9 > 8$，矛盾。
5. 因此 $K_{3,3}$ 不是平面图。$\blacksquare$

为什么 $K_{3,3}$ 躲过了第一个检测？ 因为”三座房子三口井”的图里没有三角形——任何三角形都意味着两座房子之间有边，或两口井之间有边，这在 $K_{3,3}$ 中都不存在。没有三角形 ⟹ 每个面至少 4 条边 ⟹ 可以用更强的上界。这就是官方 Note 说的 “we must think a little harder”。

定理 10.7（库拉托夫斯基定理，Kuratowski’s Theorem，1930）：一个图是平面图，当且仅当它不含 $K_5$ 的细分，也不含 $K_{3,3}$ 的细分。

陈述与直觉说明（本讲只要求陈述，不要求完整证明）：

• “含”的精确含义：图 $G$ 中存在 $5$ 个（或 $6$ 个）顶点，它们之间由互不相交（除端点外没有公共顶点）的路径相连，且连接方式与 $K_5$（或 $K_{3,3}$）一致。这些路径可以是单条边，也可以是长链。换句话说，把 $K_5$ 或 $K_{3,3}$ 的每条边”拉长”成一条路径后，得到的图作为子图出现在 $G$ 里。
• 一个方向显然：如果 $G$ 含有 $K_5$ 或 $K_{3,3}$ 的细分，则 $G$ 非平面。因为细分不改变平面性（拉长一条边只是多插几个顶点，既不制造也不能消除本质交叉），而 $K_5$、$K_{3,3}$ 本身非平面（定理 10.4、10.6）。把非平面子图”嵌”进更大的图里，只会更糟。
• 另一个方向才是深水区：若 $G$ 不含这两个细分，则 $G$ 可以画在平面上。这个方向的证明需要处理”极大平面图”“3-连通分解”“桥”等一系列结构，篇幅远超本讲范围（官方 Note 明确说 “The other direction … is difficult”）。可以记住的直觉是：非平面性只有两个”根源”，一切非平面图都只是这两个根源的”膨胀”。
• 应用示例：4 维超立方体 $Q_4$（$V=16,E=32$）是非平面的——它包含 $K_{3,3}$ 的细分。注意 $Q_4$ 通过了 $-6$ 型检测（$32 \le 42$），所以这里也必须用库拉托夫斯基定理或二分图上界（$32 > 2\cdot 16 - 4 = 28$，后者一步就够，见算例 4）。反过来，$Q_3$（立方体）是平面的，恰好是”临界”情形：$E = 12 = 2\cdot 8 - 4$。

定理 10.8（树的四个等价刻画）：对 $n = \vert V\vert \ge 1$ 的图 $G=(V,E)$，以下四条等价：

1. $G$ 连通且无环；
2. $G$ 连通且有 $n-1$ 条边；
3. $G$ 连通，且删去任意一条边都会使 $G$ 不连通（极小连通）；
4. $G$ 无环，且添加任意一条新边（连接两个原不相邻的顶点）都会产生一个环（极大无环）。

【等价刻画的循环证明链：只需证一圈，四条命题就全部等价】

     (1) 连通 + 无环
          |
          |  对顶点数 n 做强归纳（定理 10.9）
          |  删点后可能裂成 t 个分量 => 必须强归纳！
          v
     (2) 连通 + 恰好 n-1 条边
          |
          |  若删边 e 后仍连通，它至少要有 n-1 条边（引理 10.11）
          |  但它只有 n-2 条边 => 矛盾
          v
     (3) 连通 + 删任一边即断（极小连通）
          |
          |  无环：有环则可删环上一边而不失连通，与(3)矛盾
          |  加边成环：u,v 间原有路径 P，加 {u,v} 后 P+{u,v} 是环
          v
     (4) 无环 + 加任一边成环（极大无环）
          |
          |  若不连通，取两个分量中的 u,v 加边 {u,v}
          |  u,v 之间原本无路径 => 加边不生环，与(4)矛盾
          v
     (1) 连通 + 无环        （回路闭合，四条命题两两等价）

  口诀：连通无环  <=>  边数 = V-1  <=>  极小连通  <=>  极大无环

证明链条（(1)⟹(2)⟹(3)⟹(4)⟹(1)）：

• (1)⟹(2)：这是定理 10.9，下面用强归纳完整证明。
• (2)⟹(3)：设 $G$ 连通且有 $n-1$ 条边。任取一条边 $e$，若删去 $e$ 后 $G-e$ 仍连通，则由下面的引理 10.11（连通图至少 $n-1$ 条边），$G-e$ 至少要有 $n-1$ 条边；但 $G-e$ 只有 $n-2$ 条边，矛盾。故删去任意一条边都会不连通。
• (3)⟹(4)：先证 $G$ 无环：若 $G$ 含环，则环上任取一条边 $e$，删去后环上其余顶点仍连通，且环外顶点可通过环上顶点中转，故 $G-e$ 仍连通，与 (3) 矛盾。再证”加边必成环”：设在新加入的边 $\{u,v\}$ 之前，$u,v$ 本来不相邻。由 (3) 的连通性，$G$ 中存在 $u$ 到 $v$ 的路径 $P$；加入 $\{u,v\}$ 后 $P \cup \{u,v\}$ 构成一个环 ✓。
• (4)⟹(1)：已知无环，只需证连通。若 $G$ 不连通，取两个不同分量中的顶点 $u,v$（此时 $\{u,v\}$ 不是已有的边），加入边 $\{u,v\}$ 后 $u,v$ 之间本来没有任何路径，因此不可能产生环，与 (4) 的”加边必成环”矛盾。故 $G$ 连通。$\blacksquare$

定理 10.9（树有 $n-1$ 条边）：若 $G=(V,E)$ 是 $n$ 个顶点的连通无环图，则 $\vert E\vert = n-1$。这是本讲”图上的归纳法”的范式证明。

证明策略：对顶点数 $n$ 做强归纳。为什么必须强归纳？因为删掉一个顶点 $v$ 后，$G^{\prime} = G - v$ 可能裂成 $t \ge 2$ 个连通分量，我们要同时对每个分量用归纳假设，而这些分量的顶点数各不相同、都小于 $n$——只有强归纳（”对所有 $1 \le n \le k$ 成立”）才允许这么做。这正是官方练习里强调的 “Note that this requires strong induction!”

逐步推导：

1. 基础情形 $n=1$：$G$ 只有一个顶点、没有边（自环不允许），故 $\vert E\vert = 0 = n-1$ ✓。
2. 归纳假设：设对一切 $1 \le n \le k$，任何 $n$ 个顶点的连通无环图都有 $n-1$ 条边。
3. 归纳步骤（$n = k+1$）：取 $G$ 为 $k+1$ 个顶点的连通无环图。任取一个顶点 $v$，令 $G^{\prime} = G - v$（删去 $v$ 及其所有关联边）。
   • $G^{\prime}$ 仍然无环：删点删边不可能创造出新的环，这是”无环”的单调性质。
   • 但 $G^{\prime}$ 可能不连通。设 $G^{\prime}$ 的连通分量为 $G^{\prime}_1,\dots,G^{\prime}_t$（注意 $t \ge 0$：若 $k=0$ 则 $G^{\prime}$ 为空图）。
4. 分情形讨论：
   • 情形 A（$t = 1$，即 $G^{\prime}$ 连通）：$G^{\prime}$ 有 $k$ 个顶点、连通无环，由归纳假设 $\vert E(G^{\prime})\vert = k-1$。现在看 $v$ 在 $G$ 中的度数：若 $\deg(v) \ge 2$，取 $v$ 的两个邻居 $a,b$。由于 $G^{\prime}$ 连通，$G^{\prime}$ 中存在 $a$ 到 $b$ 的路径 $P$，于是 $P \cup \{v,a\} \cup \{v,b\}$ 是 $G$ 中的一个环，与无环矛盾。故 $\deg(v) \le 1$。又 $G$ 连通且 $k+1 \ge 2$，故 $\deg(v) \ge 1$。于是 $\deg(v) = 1$，$\vert E\vert = \vert E(G^{\prime})\vert + 1 = (k-1)+1 = k = n-1$ ✓。
   • 情形 B（$t \ge 2$，$G^{\prime}$ 不连通）：设分量为 $G^{\prime}1,\dots,G^{\prime}_t$，顶点数分别为 $n_1,\dots,n_t$，有 $n_1+\cdots+n_t = k$，且每个 $n_i \le k-1 < k+1 = n$。每个 $G^{\prime}_i$ 都是连通无环图，故由强归纳假设（对每个 $i$ 分别使用！） \(\vert E(G^{\prime}_i)\vert = n_i - 1.\) 求和得 $\vert E(G^{\prime})\vert = \sum{i=1}^t (n_i-1) = k - t$。
   • 关键：$v$ 必须与每个分量都有边相连。 否则若某个分量 $G^{\prime}_i$ 中的顶点与 $v$ 没有边相连，则在 $G$ 中该分量与”$v$ 及其余部分”无法连通，与 $G$ 连通矛盾。故 $v$ 至少有 $t$ 条边伸出，即 $\deg(v) \ge t$。
   • 且 $\deg(v) = t$ 精确成立。 若 $\deg(v) > t$，则由抽屉原理，$v$ 与某个分量 $G^{\prime}_i$ 之间存在两条边 $\{v,a\}$ 与 $\{v,b\}$（$a,b$ 在同一个分量中，$a\ne b$）。由于 $G^{\prime}_i$ 连通，其中存在 $a$ 到 $b$ 的路径 $P$；于是 $P \cup \{v,a\} \cup \{v,b\}$ 构成 $G$ 中的一个环，与无环矛盾。故 $\deg(v) = t$。
   • 于是 $\vert E\vert = \vert E(G^{\prime})\vert + t = (k-t) + t = k = n-1$ ✓。
5. 两种情形都得到 $\vert E\vert = n-1$，由强归纳，命题对一切 $n \ge 1$ 成立。$\blacksquare$

【证明机制解说】：这个证明是”图归纳”的教科书级范例，值得记住三个要点。

• 第一，删点之后必须考虑连通性变化。 情形 A 与情形 B 的区别不是技术细节，而是证明的实质：连通的 $G^{\prime}$ 只需一次归纳，不连通的 $G^{\prime}$ 需要对每个分量各用一次归纳。
• 第二，强归纳不是”更保险”，而是”必需的”。 情形 B 中我们同时调用 $t$ 次归纳假设，作用的规模 $n_1,\dots,n_t$ 都小于 $n$ 但彼此不等；弱归纳的假设 $P(n-1)$ 完全用不上。
• 第三，”无环”这一条件在情形 B 中被用了两次。 一次证明 $G^{\prime}$ 无环从而归纳假设可用，一次证明 $\deg(v) = t$（不能多连）。去掉无环条件，命题就假（$K_4$ 连通、$4$ 个顶点、$6 \ne 3$ 条边），所以这些地方一步都不能省。

引理 10.10（叶子引理，Leaf Lemma）：任何 $n \ge 2$ 个顶点的树至少有两个度数为 1 的顶点（称为叶子 (leaf)）。

证明策略：反证法 + 握手引理（handshake lemma，讲次 9：$\sum_{v} \deg(v) = 2E$）+ 定理 10.9 的 $E = V-1$。核心是一个计数下界与上界的冲突。

逐步推导：

1. 设树 $T$ 有 $n = \vert V\vert \ge 2$ 个顶点、$E = n-1$ 条边（定理 10.9）。
2. 由握手引理：$\sum_{v\in V} \deg(v) = 2E = 2n-2$。
3. 适由连通性（$n\ge 2$），每个顶点度数 $\ge 1$（没有孤立点）。
4. 先证至少有一个叶子：反设所有顶点度数 $\ge 2$，则 $\sum_v \deg(v) \ge 2n > 2n-2$，与第 2 步矛盾。故至少存在一个度数为 1 的顶点。
5. 再证至少有两个叶子：反设叶子恰好只有一个，设为 $u$（$\deg(u)=1$），其余 $n-1$ 个顶点度数都 $\ge 2$。则 \(\sum_{v}\deg(v) \;\ge\; 1 + 2(n-1) = 2n - 1 \;>\; 2n-2,\) 与第 2 步矛盾。
6. 故叶子数 $\ge 2$（其实还可以用”路径的两个端点都是叶子”给出一个更构造性的证明：从任意顶点出发沿最长路径走到尽头，两个尽头都必须是叶子）。$\blacksquare$

【证明机制解说】：证明的”灵光”是把”叶子太少”翻译成”度数总和太大”，再与握手引理给出的精确值 $2n-2$ 对撞。注意 $n\ge 2$ 不可省：$n=1$ 的单点树度数为 $0$，不是叶子（也没有两个叶子）。另外，这个引理是归纳法证明树命题时的”抓手”——很多关于树的归纳证明都选择删掉一个叶子的邻居或删掉叶子来做归纳步骤。

引理 10.11（连通图至少有 $n-1$ 条边）：任何 $n$ 个顶点的连通无向图至少有 $n-1$ 条边。

证明策略：对顶点数 $n$ 做归纳（这里可以用较弱的归纳，因为可以精心选择删点位置——但在情形 B 中仍需对分量分别归纳，所以本质上是强归纳）。

逐步推导：

1. 基础情形 $n=1$：$0$ 条边，$0 = n-1$ ✓。
2. 归纳假设：设对所有 $\le k$ 个顶点的连通图，边数 $\ge$ 顶点数 $-1$。
3. 归纳步骤（$n=k+1$）：取连通图 $G$，$n$ 个顶点。任取 $v$，令 $G^{\prime}=G-v$，其连通分量为 $G^{\prime}_1,\dots,G^{\prime}_t$，顶点数 $n_1,\dots,n_t$，$\sum n_i = k$。
   • 由强归纳假设，$\vert E(G^{\prime}_i)\vert \ge n_i - 1$，故 $\vert E(G^{\prime})\vert \ge k - t$。
   • 由 $G$ 连通，$v$ 与每个分量至少有一条边（理由同定理 10.9 情形 B），故 $\deg(v) \ge t$。
   • 于是 $\vert E\vert = \vert E(G^{\prime})\vert + \deg(v) \ge (k-t) + t = k = n-1$ ✓。$\blacksquare$

（这条引理正是定理 10.8 中 (2)⟹(3) 所依赖的事实，也是官方练习第 3 题。）

引理 10.12（超立方体的顶点数与边数）：$n$ 维超立方体 $Q_n$ 有 $2^n$ 个顶点、度数均为 $n$、共 $n2^{n-1}$ 条边。

证明策略：顶点数用”逐位独立选择”的乘法原理（讲次 14 的计数）；边数用两种方法——方法一：握手引理（每个顶点度数为 $n$，每条边被数两次）；方法二：递归定义 + 归纳。

逐步推导：

1. 顶点数：$V = \{0,1\}^n$，每一位有 2 种取法，$n$ 位独立，故 $\vert V\vert = 2^n$。
2. 度数：固定 $x \in \{0,1\}^n$，与 $x$ 相邻的顶点必须”恰好一位不同”，而这一位可以是 $n$ 个位置中的任意一个；选定位置 $i$ 后，邻居唯一确定为”把 $x$ 的第 $i$ 位翻转”。$n$ 个位置给出 $n$ 个不同的邻居，故 $\deg(x) = n$。
3. 边数（方法一，握手引理）：$\sum_{x}\deg(x) = 2^n \cdot n = 2E$，故 $E = n2^{n-1}$。
4. 边数（方法二，递归）：$Q_n$ 由两个 $(n-1)$ 维子立方体（$0$-子立方体与 $1$-子立方体）构成：把 $Q_{n-1}$ 的每个顶点 $x$ 复制成 $0x$ 与 $1x$，再加上 $2^{n-1}$ 条”跨接边”$\{0x,1x\}$。于是 \(E(n) = 2E(n-1) + 2^{n-1}, \qquad E(1) = 1.\) 断言 $E(n) = n2^{n-1}$。验证归纳：基础情形 $n=1$：$1\cdot 2^0 = 1$ ✓。归纳步骤：若 $E(n-1) = (n-1)2^{n-2}$，则 \(E(n) = 2(n-1)2^{n-2} + 2^{n-1} = (n-1)2^{n-1} + 2^{n-1} = n2^{n-1}. \qquad \blacksquare\)

【证明机制解说】：两个证明平分秋色。方法一是”全局计数”（用度数对称性一步到位），方法二是”结构递归”（用自相似性），后者在分析递归算法、分治法复杂度时是标准套路。注意方法二中跨接边数恰好是 $2^{n-1}$（$Q_{n-1}$ 的顶点数），这是”两位子立方体一一对应”的直接结果。

定理 10.13（$Q_n$ 是二分图，且直径恰为 $n$）：对一切 $n \ge 1$，$Q_n$ 是二分图；并且任意两个顶点之间的距离等于它们的汉明距离，故直径（diameter，任意两点间距离的最大值）为 $n$。

证明策略：构造性染色 + 归纳。用汉明距离的奇偶性给顶点染两色——这正是官方 Note 说的”每个环都是偶长度 ⟹ 二分图”。

逐步推导（二分性）：

1. 定义映射 $\chi: \{0,1\}^n \to \{0,1\}$ 为 $\chi(x) = \left(\sum_{i=1}^n x_i\right) \bmod 2$，即”$x$ 中 1 的个数的奇偶性”（也就是 $x$ 到全零串 $0^n$ 的汉明距离的奇偶性）。
2. 设 $x,y$ 相邻，则它们恰好有一位不同，于是 $\chi(x) \ne \chi(y)$（翻转一位必然改变 1 的个数的奇偶性）。
3. 取 $L = \{x : \chi(x) = 0\}$，$R = \{x : \chi(x) = 1\}$，则 $V = L \mathbin{\dot\cup} R$ 且每条边都跨在 $L,R$ 之间——按定义 $Q_n$ 是二分图 ✓。
4. 归纳版的论证（对应官方 Note 的递归定义）：$Q_1$ 是一条边，显然是二分图。设 $Q_{n-1}$ 可二分染色，把它复制成两份，一份染色不变（作为 $0$-子立方体），另一份颜色全部取反（作为 $1$-子立方体）；子立方体内部按假设合法，跨接边 $\{0x,1x\}$ 两端颜色恰好相反（因为取反了），也合法。故 $Q_n$ 可二染色，即二分图 ✓。
5. 顺带得到”环长全为偶”：在二分图中沿边行走必然在两个部分之间交替，回到起点所需的步数必为偶数。

逐步推导（距离与直径）：

1. 上界：设 $x,y$ 的汉明距离为 $d$（有 $d$ 位不同）。逐位翻转这 $d$ 个坐标，得到一条从 $x$ 到 $y$ 的长度为 $d$ 的路径，故 $\operatorname{dist}(x,y) \le d$。
2. 下界：每走一条边只能改变一位，所以走 $k$ 步最多改变 $k$ 位；要改变 $d$ 位至少需要 $d$ 步，故 $\operatorname{dist}(x,y) \ge d$。
3. 合并得 $\operatorname{dist}(x,y) = d = $ 汉明距离。
4. 直径：两个顶点间汉明距离最大为 $n$（例如 $0^n$ 与 $1^n$），故 $\operatorname{diam}(Q_n) = n$。
5. 对照完全图：$K_{2^n}$ 的直径是 1，但度数高达 $2^n-1$、边数高达 $\binom{2^n}{2} \approx 2^{2n-1}$。超立方体用 $n$ 的度数换来了 $\log_2$ 级别的直径 $n$——这是”网络拓扑设计”里最经典的时间/空间权衡。$\blacksquare$

【证明机制解说】：二分性证明的关键是找到一个”势函数”（这里是奇偶性），使得每条边都让势函数变号。这种技巧在后面讲 Markov 链的周期性、随机游走的二部性时会反复出现。归纳版本的关键技巧是“复制 + 一半取反”——用旧结构的染色给新结构染色，跨接边自动合法。

算例总汇（下面 6 个小图逐个数 $V,E,F$，逐个验算欧拉公式；数值全部经脚本核算）：

【算例 1：单点树】          【算例 2：2 点树】
      *                          * ---- *
  V=1  E=0  F=1              V=2  E=1  F=1
  V-E+F = 1-0+1 = 2  OK      V-E+F = 2-1+1 = 2  OK
  （F=1：平面未被分割）（F=1：一条边不围出封闭区域）

【算例 3：4 点星形树】      【算例 4：三角形 K3】
      *                          1
      |                        /   \
  *---*---*                   2-----3
  V=4  E=3  F=1              V=3  E=3  F=2
  V-E+F = 4-3+1 = 2  OK      V-E+F = 3-3+2 = 2  OK
  （树的 E=V-1 ✓）           （2 个面：内部三角形 + 外部面）
                             sum(s_i) = 3+3 = 6 = 2E  OK

【算例 5：正方形 + 一条对角线】   【算例 6：K2,3（二分平面图）】
   1 -------- 2                     a       b
   |        / |                      \     / \
   |      /   |                       \   /   \
   |    /     |                        c       d
   3 -------- 4                         \     /
                                          \   /
   V=4  E=5  F=3                          (e)
   V-E+F = 4-5+3 = 2  OK
   F=3：两个三角形 + 外部面      V=5  E=6  F=3
   3F=9 <= 2E=10  OK             V-E+F = 5-6+3 = 2  OK
   E=5 <= 3V-6=6  OK             E=6 <= 3V-6=9  OK
                                 E=6 <= 2V-4=6  OK（取等号！）

【算例 7：立方体 Q3（V=8,E=12,F=6）】
        000 --------- 001
        /|            /|
     010 --------- 011 |
       | |           | |
       | 100 --------|-101
       |/            |/
     110 --------- 111
   V=8  E=12  F=6  （6 个正方形面）
   V-E+F = 8-12+6 = 2  OK
   sum(s_i) = 6*4 = 24 = 2E  OK
   3F=18 <= 2E=24  OK ；4F=24 <= 2E=24 取等（二分图，每面恰好 4 边）
   E=12 <= 3V-6=18  OK ；E=12 <= 2V-4=12 取等（二分平面图临界情形）

【四个"取等 / 越界"的判据对照表（脚本已核）】

  图       V    E    3V-6   E<=3V-6?   2V-4   E<=2V-4?   平面?
  ------------------------------------------------------------------
  K3       3    3      3      OK       2       NO      YES
  K4       4    6      6      OK(等)    4       NO      YES
  K5       5   10      9      NO        6       NO      NO  <-- 上界击倒
  K2,3     5    6      9      OK        6       OK(等)  YES
  K3,3     6    9     12      OK        8       NO      NO  <-- 换用二分上界击倒
  Q3       8   12     18      OK       12       OK(等)  YES
  Q4      16   32     42      OK       28       NO      NO  <-- 二分上界击倒
  K6       6   15     12      NO        8       NO      NO
  ------------------------------------------------------------------
  结论：E<=3V-6 与 E<=2V-4 都是"必要条件"。
        NO  => 一定非平面（可以据此下结论）
        OK  => 什么也不能说，必须另找论据（库拉托夫斯基定理等）

  注意：2V-4 那一列只对"二分图"有约束力。
        K3、K4、K5、K6 都不是二分图（含三角形），
        它们该列的 "NO" 不构成任何推论——
        定理 10.5 的前提"G 是二分图"不满足，无从谈起。
        K5 只被 3V-6 那一列击倒；K3,3 / Q4 才是被 2V-4 击倒的。

反例与边界情形总汇（这些是本节最容易被忽略的部分）：

• 反例 1（$E\le 3V-6$ 是必要条件，不是充分条件）：把 $K_5$ 的一条边细分一次，得到 $G$：$V=6$，$E=11$，而 $3V-6 = 12$，故 $11 \le 12$ 成立——$G$ 通过了边数检测。但 $G$ 含有 $K_5$ 的细分，由库拉托夫斯基定理，$G$ 非平面。所以 $E \le 3V-6$ 不能用来证明平面性。同理，把 $K_{3,3}$ 的一条边细分一次：$V=7,E=10$，$2V-4 = 10$，恰好取等号，检测”通过”，但它含 $K_{3,3}$ 的细分，仍非平面。上界只能用来否定平面性，不能用来肯定平面性。
• 反例 2（必须 $V\ge 3$ 且为简单图）：单点树 $V=1,E=0$ 时 $3V-6 = -3 < 0 = E$，不等式反向；两点一条边 $V=2,E=1$ 时 $3V-6 = 0 < 1$。此外，柯尼斯堡七桥图有多重边（$A,B$ 之间两座桥），此时”每个面至少 3 条边”不成立（两条平行边可以围出一个 2 边面），$E\le 3V-6$ 的推导整条链就断了。
• 反例 3（”$3F \le 2E$”中的等号条件）：$3F \le 2E$ 对 $K_4$ 取等号（$F=4,E=6$：$12 \le 12$），对 $Q_3$ 也取等号（$F=6,E=12$：$18 \le 24$ 不取等）。取等号意味着每个面恰好是三角形，这样的平面图叫极大平面图 (maximal planar graph)，$K_4$、正四面体都是。极大平面图在顶点数 $V\ge 3$ 时恰好有 $E = 3V-6$ 条边。
• 反例 4（强归纳不可换成弱归纳）：定理 10.9 的情形 B 中，删点后可能裂成多个分量，规模各不相同。若用弱归纳（只假设 $P(k)$），对规模 $n_i < k$ 的分量完全无法调用假设，证明立即断链。

与经典问题的联系

（1）芯片布线与 PCB 单层布线（平面性的工程含义）。在印刷电路板 (PCB) 的单层布线中，导线不能交叉（交叉就短路）。因此”这个连接关系图能不能单层布通”就是平面性判定问题。$K_5$ 非平面意味着：如果 5 个元件要两两直连，单层布线做不到，必须打孔换层（多层板）或引入跳线。库拉托夫斯基定理给出了一个结构性判据：只要找到 $K_5$ 或 $K_{3,3}$ 的细分，就可以断言”必须换层”。工程上的实用算法（如 Hopcroft–Tarjan 的线性时间平面性测试）本质上就是它的算法化版本。

（2）互联网拓扑与”平面图不够用”。路由器网络的物理布线大体平面，但逻辑连接（IP 链路）常常非平面——因为长距离链路会”跨越”中间节点。$E \le 3V-6$ 告诉我们：平面结构最多只能提供约 3 倍顶点数的边，这远不足以支撑互联网的高连通需求。所以真实网络必须”非平面化”，代价是布线复杂度（交叉、跳线、光纤绕行）。这也解释了为什么数据中心网络要用超立方体、胖树 (fat-tree)、Butterfly 这类非平面但对高度数友好的拓扑。

（3）Connection Machine 与超立方体拓扑。1980 年代 Thinking Machines 的 Connection Machine 要把 100 万台处理器连起来。完全图需要 $\binom{10^6}{2} \approx 5\times10^{11}$ 根线（官方 Note 说约 $10^{12}$ 量级），完全不可行；20 维超立方体 $Q_{20}$ 每个处理器只连 20 个邻居，边数约 $20 \cdot 2^{19} \approx 10^7$，而任意两台处理器通信最多中转 20 跳。这就是引理 10.12 与定理 10.13 的直接工程价值：度数为 $n$、直径为 $n$、边数 $n2^{n-1}$ 的精确公式让设计者能精确算成本。

（4）树与最小生成树 / 路由 / 二叉搜索树。树”连通且无环”的等价刻画（定理 10.8）说明它有唯一路径性质，这让路由变得极简（不用防环，不需要复杂的路由协议）。计算机网络中的生成树协议 (Spanning Tree Protocol) 就是在物理网络里选出一棵生成树来转发帧，避免广播风暴。另一方面，树没有冗余，所以需要”鲁棒性”时要在树上加边形成环。二叉搜索树 (BST) 是有根树：根在顶部，深度 $d$ 是最长根到叶路径长度，第 $k$ 层是与根距离为 $k$ 的顶点集合——查找代价正比于深度，而随机 BST 的期望深度分析要用到讲次 20 的期望线性性。

（5）四条颜色定理与频段分配（对偶与着色）。平面图还有一个漂亮的对偶 (duality) 结构：在平面图 $G$ 的每个面上放一个”对偶顶点”，两个面共享一条边就在对偶图中连一条边，得到 $G^$；$(G^)^* = G$。”给政治地图染色使相邻国家异色”因此等价于”给平面图的顶点染色使相邻顶点异色”。四色定理说平面图只需 4 种颜色；官方 Note 证明的是较弱的版本（定理 5.4，五色定理），思路是对顶点数归纳：先证明存在度数 $\le 5$ 的顶点（用 $E\le 3V-6$：若所有顶点度 $\ge 6$ 则 $E \ge 3V > 3V-6$，矛盾），删掉它、递归染色、再把它放回并用”可换色的连通分量”技巧找一个没用过的颜色。频段分配是它的直接应用：把发射台想成顶点，位置太近（会干扰）就连一条边；如果干扰图是平面的，四色定理保证 4 个频段即可无冲突分配。

（6）de Bruijn 序列与 Euler 定理（承上讲）。$2^n$ 位的循环串若每个 $n$ 位子串恰好出现一次，就叫 de Bruijn 序列。构造方法是：在顶点集 $\{0,1\}^{n-1}$ 上造有向图，每个顶点 $a_1\cdots a_{n-1}$ 有两条出边（右移补 0 或补 1）。每个顶点入度 $=$ 出度 $=2$，由讲次 9 的有向版 Euler 定理（把”所有顶点偶度”改成”每个顶点入度 = 出度”）该图必有欧拉环游，沿环游读出的位就是 de Bruijn 序列。这个例子说明：Euler 定理 + 一个巧妙的建模 = 一个组合对象的构造性存在证明。

与其他讲次的关联

• 讲次 9（Graphs，图论基础）：本讲的起点是讲次 9 的语言——顶点、边、度、路径、环、连通分量、二部图。握手引理 $\sum_v \deg(v) = 2E$ 在引理 10.10（叶子引理）与引理 10.12（超立方体边数）中被用了两次；有向版 Euler 定理在 de Bruijn 序列的应用中直接复用（只把条件从”所有顶点偶度”改成”每个顶点入度 = 出度”）；二部图概念在本讲升级成了”无奇环”的等价刻画，并由此得到更紧的 $E\le 2V-4$。
• 讲次 3（Induction，归纳法与强归纳）：本讲是讲次 3 的技巧在图论上的主战场。欧拉公式定理 10.1 是对边数归纳；树有 $n-1$ 条边（定理 10.9）与连通图至少 $n-1$ 条边（引理 10.11）是对顶点数的强归纳，且”删点后裂成多个分量”正是讲次 3 中”弱归纳不够用、必须强归纳”的最典型场景。超立方体的边数递推 $E(n) = 2E(n-1) + 2^{n-1}$ 也是标准归纳。
• 讲次 2（Proof Techniques II，逆否/反证/分情形）：$K_5$ 与 $K_{3,3}$ 非平面都是反证法（假设平面 ⟹ 必须满足边数上界 ⟹ 具体数字矛盾）；$E\le 3V-6$ 的”必要非充分”是逆命题不成立的经典素材；树的等价刻画用循环式证明（(1)⟹(2)⟹(3)⟹(4)⟹(1)）展示”多条命题等价”的标准证法。
• 讲次 14（Counting，计数）：$K_n$ 的边数 $\binom{n}{2} = n(n-1)/2$ 是组合数最直接的应用；$Q_n$ 的顶点数 $2^n = \vert \{0,1\}^n\vert $ 用的是乘法原理；引理 10.2 的 $\sum s_i = 2E$ 与握手引理都是双计数，与讲次 16（Combinatorial Proofs）的双计数/双射思想同源。
• 讲次 12（Countability，可数性）：$\{0,1\}^n$ 与 $2^n$ 的联系将在讲次 12 扩展到 $\{0,1\}^{\infty}$；对角化论证的核心正是”所有 $n$ 位串可以编号”这一事实。此外”平面图稀疏 ⟹ 可数”这类论证在讲次 12/13 会以更抽象的形式出现。
• 讲次 11（Stable Matching，稳定匹配）：稳定匹配的实例天然是完全二分图 $K_{n,n}$ 加上两侧的偏好序；本讲建立的二分图语言（$E\le 2V-4$ 那一套）为讲次 11 提供词汇，而讲次 11 的 Gale–Shapley 算法则给出”二分图上的完美匹配（perfect matching）”这一概念的具体算法化实例。
• 讲次 20（Expectations & Linearity，期望与线性性）：超立方体上的随机游走、$Q_n$ 中随机两点距离的期望，都会用到本讲的”距离 = 汉明距离”结论与期望线性性；图论中的平均度数 $\bar d = 2E/V$ 也是线性性推导的常客。
• 讲次 26（Markov Chains，马尔可夫链）：$Q_n$ 的二分性（定理 10.13）会导致其上的随机游走具有周期性（周期 2），这正是 Markov 链周期性理论中最标准的例子。

关键要点

1. 欧拉公式是平面图理论的”能量守恒”：连通平面图满足 $V - E + F = 2$（含外部面）；不连通时是 $V - E + F = 1 + C$（$C$ 为连通分量数）。证明靠”删圈上的边使 $E$ 与 $F$ 各减 1、删桥使只有 $E$ 减 1”的不变量论证。
2. 两条上界及其适用范围：简单平面图 $V\ge 3$ 时 $E \le 3V-6$；若还是二分图则 $E \le 2V-4$。推导的公共骨架是 $\sum_{i=1}^F s_i = 2E \ge (\text{最小面长})\cdot F$，其中最小面长在一般图是 3、在二分图是 4。
3. 非平面性的两把锤子：$K_5$ 用 $E=10 > 3\cdot 5-6=9$ 击倒；$K_{3,3}$ 用 $E=9 > 2\cdot 6-4=8$ 击倒（注意它通过了 $-6$ 型检测）。库拉托夫斯基定理进一步说：$K_5$ 与 $K_{3,3}$ 的细分是唯一的两个非平面性根源。
4. 树的等价刻画记成一句口诀：”连通无环 $\iff$ 连通且边数 $=V-1$ $\iff$ 极小连通（删任一边即断）$\iff$ 极大无环（加任一边成环）”。树的叶子引理：$V\ge 2$ 的树至少有两个叶子（用 $\sum\deg = 2(V-1)$ 反证）。
5. 图归纳的三条铁律：对顶点数或边数归纳；删点后可能不连通，必须对每个连通分量分别归纳；因此要用强归纳而非弱归纳。此外”删什么”是证明的艺术——删叶子、删环上的边、删度 $\le 5$ 的顶点，各有各的用处。
6. 超立方体 $Q_n$ 的四个公式：$V = 2^n$、$\deg = n$、$E = n2^{n-1}$、直径 $= n$；且它是二分图（按 1 的个数的奇偶性染色 / 归纳地”复制 + 一半取反”）。

常见误区与注意事项

1. 把”这张画法有交叉”当成”这个图非平面”。平面性是存在性性质：只要有某一种无交叉画法就够。$K_4$ 的”正方形 + 两条对角线”有 1 个交叉，但 $K_4$ 明明是平面图。判断非平面必须用证明（边数上界或库拉托夫斯基），不能靠”我画不出来”。
2. 忘记外部面。欧拉公式里的 $F$ 包含无界的那个面。$K_4$ 的面数是 $4$（3 个内部三角形 $+$ 1 个外部面），不是 3；三角形 $K_3$ 是 $2$ 不是 1；单点图是 $1$ 不是 0。漏掉外部面会让 $V-E+F$ 全部算错 1。
3. 把必要条件当充分条件。$E \le 3V-6$ 是平面性的必要条件：$K_5$ 的细分（$V=6,E=11\le 12$）满足不等式却非平面。同理 $K_{3,3}$ 满足 $-6$ 型不等式（$9\le 12$）却非平面——这正是为什么必须发展 $-4$ 型上界。上界只能用来证明”非平面”，不能用来证明”平面”。
4. 忽略定理的前提条件。$E\le 3V-6$ 需要”简单图（无平行边、无自环）、连通、$V\ge 3$”三个条件；$E\le 2V-4$ 还需加上”二分图”。柯尼斯堡七桥图有多重边，就是一个被排除的实例。$V=1,2$ 时不等式本身不成立（$3V-6$ 是负数）。
5. 图归纳中错误地使用弱归纳。删掉一个顶点后 $G^{\prime}$ 可能裂成 $t$ 个连通分量，归纳假设要同时作用于这些大小不一的分量。弱归纳只能说”$P(k) \Rightarrow P(k+1)$”，根本调不动。这是”图上的归纳法”最核心的考点。
6. 混淆超立方体的度数与直径。$Q_n$ 的度数（邻居数）是 $n$，直径（最远距离）也是 $n$，两者数值恰好相同，但含义完全不同：度数决定布线成本，直径决定通信延迟。$Q_3$ 每个顶点连 3 条线，最远也要走 3 跳——数值相等，概念不可混。
7. 把 $3F \le 2E$ 无条件使用。它的推导依赖”每个面至少 3 条边”，而这需要简单图 + 至少 3 条边。树的情形下 $F=1$ 而 $2E$ 可能很小（$V=2$ 时 $3F = 3 > 2 = 2E$），不等式根本不成立。

思考题（带答案）

Q1. 设 $G$ 是连通平面简单图，$V = 9$，每个顶点的度数都是 4。请判断这样的 $G$ 是否存在；若存在，求面数 $F$；并回答”$G$ 可能是二分图吗”。

Q2. 证明：若树 $T$ 有 $n \ge 2$ 个顶点，则 $T$ 中至少有两个叶子；并说明为什么这条结论在 $n=1$ 时失效。

Q3. 判断正误并说明理由：「超立方体 $Q_4$ 是二分图，所以它是平面图。」

Q4（图归纳专练）：请说明”证明任何 $n$ 个顶点的连通图至少有 $n-1$ 条边”时，为什么必须用强归纳，并写出删掉顶点 $v$ 后图裂成 $t$ 个连通分量时归纳步骤的关键式子。