平面图

这一个恒等式几乎是关于平面图的所有其他事实的源头,包括边数上界以及 $K_5$ 与 $K_{3,3}$ 的非平面性,并且它由一个简短且完全初等的归纳法证明。

归纳基础。若 $E$ $= 0$ 且图连通,则它必定只由单个顶点组成($V=1$),且恰好有一个面,即整个无界平面($F=1$)。此时 $1 - 0 + 1 = 2$ 成立。

归纳步骤,情形1:某条边位于一个圈上。假设公式对每个边数少于 $E$ 的连通平面图都成立,设该图有 $E$ $\ge 1$ 条边。若某条边 $e$ 位于一个圈上,则去掉 $e$ 后图仍连通(圈的其余部分仍连接其两个端点)。去掉 $e$ 会把它两侧的两个面合并为一个面,于是较小的图有 $V$ 个顶点、$E - 1$ 条边、$F - 1$ 个面。由归纳假设,$V - (E-1) + (F-1) = 2$,化简得 $V - E + F = 2$。

归纳步骤,情形2:没有边位于任何圈上。此时每条边都是桥,即该图完全没有圈,也就是一棵树。画在平面上的树恰好有一个面($F = 1$,唯一的无界区域,因为没有圈可以围出有界区域),而关于树的一个标准事实是:有 $V$ 个顶点的树恰好有 $E = V - 1$ 条边。代入得 $V - E + F = V - (V - 1) + 1 = 2$。

结论。每种情形要么直接得到公式成立,要么(通过去掉一条边)归约到一个由归纳假设成立的更小的图,因此 $V - E + F = 2$ 对任何连通平面嵌入图都成立。

这给出了仅用两个小型禁止模式就能完全刻画平面性的可检验判据,把一个存在性问题(能否找到某种无交叉画法?)转化为寻找两种特定障碍之一的问题。

为何 $K_5$ 与 $K_{3,3}$ 本身不是平面图。$K_5$ 有 $V=5$ 个顶点、$E=10$ 条边,但边数上界 $E \le 3V - 6$ 要求 $10 \le 3(5)-6=9$,矛盾,所以 $K_5$ 不是平面图。$K_{3,3}$ 是有 $V=6$ 个顶点、$E=9$ 条边的二部图;平面二部图必须满足更紧的界 $E \le 2V - 4$,要求 $9 \le 2(6)-4=8$,同样矛盾,所以 $K_{3,3}$ 也不是平面图。

细分保持非平面性(容易的方向)。若图 $H$ 是图 $G$ 的一个细分(将 $G$ 的每条边替换为内部不相交的路径),且 $G$ 不是平面图,则 $H$ 也不可能是平面图:$H$ 的任何无交叉画法,只需擦去每条路径内部的2度顶点并把它拉直成一条边,就能变成 $G$ 的一个画法,而这不会引入任何新的交叉。因此任何以 $K_5$ 或 $K_{3,3}$ 的细分作为子图的图都自动不是平面图,这就证明了定理的必要性方向。

反方向(困难的方向)概述。每个非平面图都必须包含这样一个细分,这是深刻的部分,由库拉托夫斯基于1930年,以及以等价的子式形式由瓦格纳于1937年独立证明。论证过程是:取一个假设中不含 $K_5$ 或 $K_{3,3}$ 细分的最小非平面图,并导出矛盾:利用门格尔关于连通性的定理,先归约到图是3-连通的情形(带有小顶点割的图可以沿该割分成更小或更简单的平面部分,再重新拼接),然后直接证明任何最小的3-连通非平面图都已经包含两种禁止细分之一。这种通过连通性进行的结构归约正是该定理真正困难之所在。

结论。结合两个方向,一个图是平面图当且仅当它同时避开这两种禁止细分,由此得到完整的刻画。