planar · Euler · Kuratowski · dual

平面图：Euler 公式、Kuratowski 与对偶

一张图若能画在平面上、使任意两条边除端点外都不相交，就叫 planar graph（平面图）。一个具体的无交叉画法称为 平面嵌入 (planar embedding)；它把平面切成若干块连通区域，每块叫一个 face（面）——其中总有一块向四周无限延展的 外部面 (outer / unbounded face)。本页先用可换样本的图核验 $V - E + F = 2$ 并画出它的对偶图，再看 $K_5$ 与 $K_{3,3}$ 为何无论怎么画都躲不开交叉。这套结论由子图谱系里的细分 / 子式关系收口。

平面嵌入把平面分成 F 个面（含 1 个无界外部面）。每条边恰好是两个面的公共边界，每个面的边界是一条闭合的边走廊。下面三个样本都已手工标注好每个面的顶点环，切换样本即可逐一核对。

Euler 公式——对任何连通平面图的平面嵌入， $V - E + F = 2$ 。其中 F 计入唯一的外部面。（若图有 k 个连通分支，则推广为 $V - E + F = 1 + k$ 。）

从 Euler 公式挤出边数上界： 设 $V \ge 3$ 的简单平面图。每个面的边界至少由 3 条边围成，而每条边最多被 2 个面共享，于是 ${3F \le 2E}$ ，即 $F \le 2E/3$ 。代入 $F = 2 - V + E$ 得 ${2 - V + E \le 2E/3}$ ，整理即 $E \le 3V - 6$ 。

若图还是二部的（不含三角形，最短面边界 ≥ 4），则 ${4F \le 2E}$ ，同法得到更紧的 $E \le 2V - 4$ 。这两条不等式是判「不可平面」最快的一刀：边太多就一定画不平。

两块绕不开的「障碍」： 完全图 $K_5$ 与完全二部图 $K_{3,3}$ 。把上面的不等式当尺子量一下，它们当场出局——下面两幅图把违规算式写在标题里。

Kuratowski 定理 (1930)——一张图可平面当且仅当它不含 $K_5$ 或 $K_{3,3}$ 的细分 (subdivision) 作为子图。换言之，把 $K_5$ 或 $K_{3,3}$ 的边拉长成路（插入若干 2 度顶点）后能嵌进图里，图就一定画不平。

Wagner 定理——等价的子式版本：一张图可平面当且仅当它不含 $K_5$ 或 $K_{3,3}$ 作为子式 (minor)。细分（拓扑子式）与收缩（子式）的区别见子图谱系；在「可平面」这件事上两套语言恰好给出同一对禁用块。

平面对偶图 (planar dual) G*： 在每个面里放一个对偶顶点；原图中两个面若共享一条边，就在这两个对偶顶点间连一条对偶边——这条对偶边恰好横穿那条原边。于是 G* 的边与 G 的边一一对应，E(G*) = E(G)，而 V(G*) = F(G)、F(G*) = V(G)。上面的对偶画布按这个规则生成（centroid 取面内顶点的平均位置；外部面的对偶顶点摆在图外）。注意：对偶可能出现重边——当两个面共享不止一条边时（如「正方形 + 对角线」样本），这是对偶的正常现象，不是错误。