Kuratowski定理
概述
Kuratowski 定理（Kuratowski’s Theorem）：一个图是平面图当且仅当它不包含 或 的细分（subdivision）作为子图。这是平面图判定中最深刻、最根本的刻画。
定理陈述
形式化陈述
定理（Kuratowski, 1930）： 设 是一个有限简单图，则 是平面图（planar）当且仅当 不包含 （完全五点图）或 （完全二部图）的细分作为子图。
定义（细分 / subdivision）：对图 中的一条边 进行细分，是指删除 ，添加一个新顶点 和两条新边 、。图 是 的细分，如果 可以通过对 的若干条边反复进行细分操作得到。
等价表述： 是平面图当且仅当 不包含与 或 同胚（homeomorphic）的子图。
证明概要
证明思路
Kuratowski 定理的证明分为必要性（）和充分性（）两个方向，难度差异很大。
必要性（）：平面图不含 / 细分
这一方向较为直接。
证明：
- 若 是平面图，则 的任何子图也是平面图（子图的平面嵌入可由 的平面嵌入限制得到）。
- 和 已被证明是非平面图（利用 欧拉公式 的推论）。
- 若 是非平面图 的细分，则 也是非平面图。因为若 有平面嵌入，则将细分点”合并”（即删除度为 的顶点，用一条边连接其两个邻居）可得到 的平面嵌入，矛盾。
- 因此，平面图 不能包含 或 的细分作为子图。
充分性（）：不含 / 细分则为平面图
这一方向是 Kuratowski 定理的核心难点，证明较为复杂。
证明概要：
-
简化到 -连通图：利用一个关键引理——若图 的每个块（block，极大 -连通子图）都是平面图，则 本身是平面图。进一步，可以只考虑 -连通图的情形。
-
Wagner 定理的等价形式：Wagner（1937）给出了一个等价刻画——图是平面图当且仅当它不包含 或 作为小图（minor）。充分性的证明通常通过 Wagner 的框架进行。
-
归纳法：对顶点数 进行归纳。
- 基础： 时，所有图都是平面图。
- 归纳步：对于 -连通图 ，若 不含 / 细分，可以找到一个边 使得 仍是 -连通的，或者找到一种方式将 分解为更小的图，利用归纳假设。
-
Jordan 曲线定理：充分性的严格证明最终依赖于 Jordan 曲线定理（平面上的简单闭曲线将平面分为内部和外部两个区域），这是拓扑学的基本结果。
由于充分性证明的完整展开需要大量拓扑学工具和篇幅，这里仅给出证明框架。完整的严格证明可参见下方参考链接。
关键推论
- 推论1（Wagner 定理）：图 是平面图当且仅当 和 都不是 的小图（minor）。小图关系比细分关系更一般。
- 推论2（非平面图的识别）：要判断一个图是否为平面图，只需检查它是否包含 或 的细分。这提供了一个有限的可检查条件。
- 推论3（平面图算法）：基于 Kuratowski 定理，存在判断平面性的线性时间算法（Hopcroft-Tarjan 算法，1974），尽管算法本身并不直接搜索 / 的细分。
应用场景
- 平面性判定：Kuratowski 定理是判断一个图能否在平面上无交叉绘制的根本准则。例如，判断印刷电路板的布线是否可行。
- 图论算法设计：许多图论问题在平面图上有更高效的算法。Kuratowski 定理帮助我们识别哪些图可以享受这些高效算法。
- 图的着色：四色定理仅对平面图成立，Kuratowski 定理帮助确定四色定理的适用范围。
- 网络可视化：在信息可视化中，判断一个关系网络是否可以无交叉地绘制在二维平面上。
数值示例
（完全五点图）： 个顶点，每个顶点与所有其他顶点相连，共 条边。由欧拉公式推论，，故 是非平面图。
（完全二部图）：两组各 个顶点，组间完全连接，共 条边。由欧拉公式推论（无三角形），，故 是非平面图。
Petersen 图：包含 的细分，因此是非平面图。