Kuratowski 定理

在导线上加一个中转点，不会改变导线能否无交叉布置。同样，把一条边拉长为若干段只是改变表示，不会消除平面性障碍。定理要求寻找的是这类“被拉长的禁图”，而不只是直接相邻的五点或六点结构。

容易的一向与困难的一向 ​

如果图已含禁图细分，就不可能平面。否则从平面画法中删去无关顶点和边，再沿各细分路径压去中间顶点，就会得到 $K_5$ 或 $K_{3,3}$ 的平面画法，与它们的非平面性矛盾。

反向才是定理的主要内容：每张非平面图都能找出这种证书。仅证明两个禁图不可平面并没有完成这一向。标准证明先取边极小的非平面子图，再分析圈上不同附着部分能否分别画在圈内、圈外；无法安排的交错结构最终产生两类细分之一。这里只概述证明路线；完整证明还需分类处理这些附着部分。Shor 讲义给出最大度三情形及一般情形的扩展。

两个基本障碍的数值检验 ​

由平面图 Euler 公式理路平面图欧拉公式Euler's formula for planar graphs连通平面图的顶点数、边数与面数满足 V−E+F=2。，简单平面图在 $v\ge 3$ 时满足 $e\le 3v-6$。$K_5$ 有五点十边，而 $3\cdot 5-6=9$，所以不可能平面。

对顶点数 $v\ge 3$ 的简单二分平面图，面边界计数给出更强的 $e\le 2v-4$。$K_{3,3}$ 有六点九边，而 $2\cdot 6-4=8$，同样矛盾。这就分别验证了两种基本障碍的非平面性。

为什么不能只查普通子图或边数 ​

在 $K_{3,3}$ 的九条边上各插一个新顶点，所得图有 $15$ 个顶点、$18$ 条边。六个原顶点度数仍为三，九个新顶点度数为二。原顶点之间没有直接边，因而不存在普通的 $K_{3,3}$ 子图；最大度也排除了 $K_5$ 子图。

但它本身正是 $K_{3,3}$ 的细分，所以非平面。它同时满足 $18\le 3\cdot 15-6$ 和 $18\le 2\cdot 15-4$，说明这两个边数不等式都是必要条件，绝非充分条件。

图 minor理路图 minorGraph minor · Minor of a graph通过删顶点、删边和收缩边从原图获得的粗粒度图结构。还允许收缩任意边，把一整块连通分支压为一点；细分子图只允许把目标的边表示成内部不交路径。Wagner 定理用禁含 $K_5,K_{3,3}$ minor 得到同样的平面图类，minor 证书由连通分支集组成，细分证书则由内部不交路径组成。Kuratowski 证书中的内部点只需在选出的子图内度二，在原图中可以有额外关联边。

非平面性可以给出有限、可核验的证据：列出分支顶点与替代路径，检查路径端点、内部互不相交以及母图中确实存在这些边即可。平面性测试算法因此可在拒绝输入时输出 Kuratowski 子图，让结果可以独立复核。

寻找证书时，平面性测试算法使用图分解和嵌入维护，逐步定位导致冲突的分支与路径；输出后则按上述局部条件独立核验。

对含自环或平行边的无向图，判定可平面性可先看底层简单图：自环可放在顶点附近，平行边可沿原边邻近布置，它们不增加新的禁图类型。若顶点位置固定、边必须按给定直线绘制，或者画在其他曲面上，问题已改变，不能直接照搬这个平面嵌入定理。