库拉托夫斯基定理

$K_5$ 和 $K_{3,3}$（以及它们的细分）非平面可由欧拉公式 $V - E + F = 2$ 推出：$V \ge 3$ 个顶点的平面图满足 $E \le 3V - 6$（这就排除了 $V=5, E=10$ 的 $K_5$），若不含三角形则满足 $E \le 2V - 4$（这就排除了作为二分图且 $V=6, E=9$ 的 $K_{3,3}$）。反过来，取极小非平面反例 $G$，证明它是 3-连通的，收缩或删去一条边 $e = \{u,v\}$，分析 $G - e$ 的平面嵌入中围绕各面的路径如何阻碍无交叉地放入 $e$，即可迫使图中出现 $K_5$ 或 $K_{3,3}$ 的细分。