库拉托夫斯基定理

库拉托夫斯基定理（）是一个关于平面图的等价判定定理，它由波兰数学家卡齐米日·库拉托夫斯基提出.。这个定理表明，一个图是平面图当且仅当它不包含K5 或 K3,3的细分。其中，K5是包含5个顶点的完全图，K3,3是包含6个顶点的完全二分图，其中三个顶点和另外三个顶点两两相连，K3,3也被称作。

 进一步阐述 
平面图（planar graph）是可以画在平面上，使得不同的边在除了端点之外互不相交的图。

细分（subdivision）是在一个图的一些边上加入一些点，使得这些边被分割成包含一条或多条边的路径。库拉托夫斯基定理表明，一个图G是平面图，如果它不能通过细分K5或 K3,3的边，然后再加上一些多余的边或点得到。等价地，一个图是平面图当且仅当它不包含同胚（Homeomorphism）于K5 或 K3,3的子图。

库拉托夫斯基子图
G是一个图，如果它包含K5或 K3,3的细分H，那么H被称为G的一个库拉托夫斯基子图。.

K5和 K3,3均不是平面图，这可以分类讨论或利用欧拉公式进行验证。此外，细分一个非平面图不可能得到一个平面图。这是显然的，如果一个图G的细分G′有平面画法，那么把G′中通过细分边e得到的路径的平面曲线段当作原图G边e的平面曲线段，我们也可以得到G的一个平面画法。因此，一个包含库拉托夫斯基子图的图不是平面图。定理的另一边证明则更加困难。

 相关结论 
库拉托夫斯基定理和另一个平面图等价判定定理瓦格纳定理(Wagner's theorem)高度相关。瓦格纳定理表明，一个图是平面图当且仅当 K5 或 K3,3 不是它的次图（minor）。次图又称图子式，如果无向图H可以通过图G删除边和顶点或收缩边得到，则称H为G的子式或次图。

显然，如果图G包含库拉托夫斯基子图，那么K5 或 K3,3一定是它的子式。反之，可以验证任意包含K5 或 K3,3子式的图G也必然包含库拉托夫斯基子图.。因此，两个定理实际上是等价的。

 參考資料 

Category:图论
Category:图染色
Category:图染色