Kuratowski 定理

平面性障碍不要求图中直接出现 $K_5$ 或 $K_{3,3}$ 作为普通子图；长路径可以充当一条边，因此应允许对边做细分。定理说所有非平面复杂性最终都能收缩到这两种核心：一种来自五点两两连接，另一种来自三对三的交叉连接。删边删点只是暴露障碍，压缩度二路径才识别其拓扑骨架。

$K_5$ 和 $K_{3,3}$ 本身非平面；在它们边上插入任意多个顶点仍非平面。仅含一个 $K_5$ minor 不必显式含 $K_5$ 子图。定理是存在性刻画，实际线性时间平面性测试还需更具体算法。

把 $K_{3,3}$ 的每条边中插入一个新顶点，所得图没有度数为三的六顶点完全二分子图作为普通子图，却仍非平面，因为它本身就是 $K_{3,3}$ 的细分。反之，含有一个非平面子图当然使整个图非平面。多重边与自环不构成新的简单图平面性障碍，通常先化到简单图讨论。

平面图公理库平面图Planar graph · Plane graph可把顶点与边嵌入平面且除公共端点外没有交叉的抽象图。可由禁含两种细分刻画，子图公理库子图Subgraph从母图删除顶点或边、同时保留剩余边端点关系所得的图。与边细分共同表达这一拓扑子结构，并与禁 minor 的 Wagner 刻画相呼应。五阶完全图公理库完全图Complete graph每一对不同顶点都恰有一条边相连的有限简单无向图。和完全二分图 $K_{3,3}$ 也可先由Euler 公式公理库平面图欧拉公式Euler's formula for planar graphs连通平面图的顶点数、边数与面数满足 V−E+F=2。证明非平面；算法上，平面性测试不仅返回真假，还常输出一个 Kuratowski 证书。