库拉托夫斯基定理

为何 $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-连通非平面图都已经包含两种禁止细分之一。这种通过连通性进行的结构归约正是该定理真正困难之所在。

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