第 12 讲 · 平面图

平面图指存在一种画法，使不同边只在共同端点相交。当前画法出现交叉，不等于图不平面；必须证明所有画法都无法消除交叉。

面属于嵌入，不只属于抽象图

把连通平面图无交叉地嵌入平面后，边把平面分成若干面，包括恰好一个无限面。一个面的次数是其周界经过的边数；桥会在同一面边界上被走两次。

每条边为两侧的面各贡献一次，因此：

$$\sum_{f\in F}\deg(f)=2|E|.$$

欧拉公式把顶点、边和面锁在一起

对连通平面图：

$$|V|-|E|+|F|=2.$$

若图是一棵树，只有一个无限面，代入得到 $|E|=|V|-1$。加入一条保持平面的非桥边时，边数和面数各增加一，等式仍保持，这给出了直观证明。

至少三个顶点的简单连通平面图，每个面次数至少为 3，所以：

$$3|F|\leq 2|E|.$$

结合欧拉公式得到：

$$|E|\leq3|V|-6.$$

若图没有三角形，例如简单二分平面图，每个面次数至少为 4，可加强为：

$$|E|\leq2|V|-4.$$

这些都是必要条件，不违反上界仍可能不平面。

$K_5$ 与 $K_{3,3}$ 是两种基本障碍

$K_5$ 有 5 个顶点、10 条边，违反 $3n-6=9$，因此不平面。$K_{3,3}$ 有 6 个顶点、9 条边，不违反一般边数界，却是二分图，应使用加强界 $2n-4=8$，仍得到不平面。

在边上插入或删除度为 2 的顶点不改变可平面性。Kuratowski 定理指出：图平面，当且仅当它不包含与 $K_5$ 或 $K_{3,3}$ 同胚的子图。这给出完整结构刻画，而边数界只提供快速排除。

极大平面图把所有面三角化

简单平面图若再加任意缺失边都会不平面，称为极大平面图。至少三个顶点的极大平面图每个面都是三角形，因此恰有 $3n-6$ 条边。极大描述的是“不能再加边”，不等于顶点或边数量在所有平面图中最大。

对偶图交换面与顶点

给定一个平面嵌入，在每个面中放一个对偶顶点；原图每条边分隔两个面，就连接相应对偶顶点。原图的圈和割在对偶中互相对应，最小割问题因此可以转成对偶图中的路径问题。

对偶依赖具体嵌入，而不是任意画法之外的唯一抽象对象。使用对偶前必须固定平面嵌入。