一个图论问题的简单证明

邢振宇

（威海职业学院信息工程系）

从库拉图斯基定理的证明以来，很多书本都引入这个定理，它也是证明一个图是否是可平面图的基本定理，同时也是一个平面图着色的基础。本文就是通过一种容易理解和简短的证明这个有用的定理.

一、知识简介

库拉图斯基定理图G 是可平面图当且仅当G 中既不含与K5同胚的子图，也不含与K3，3同胚的子图.

定义1（点连通）设X 是一个拓扑空间，x，y∈X，如果X 中有一个连通子集同时包含x 和y，我们称点x 和y 是连通的.

定义2（连通分支）设X 是一个拓扑空间，对X 中的点的连通关系而言的每一个等价类成为拓扑空间X 的一个连通分支.

二、定理的证明

定理:完全图K5和二部图K3，3不能嵌入S2.

图1

图2

证明：先证完全图K5不能嵌入到S2.

假设存在嵌入f：K5→S2，由于K5中三条边才能构成一个闭合回路（见上图1ABC 就是一个回路），从而S2/f（K5）的每个连通分支至少要与K5的三条边相邻，同时K5的每条边只与至多2个连通分支相邻.考虑到K5一共有条边，这就意味着S2/（fK5）至多有[2×4÷3]=6个连通分支，这里[x]表示取整函数.

同时S2/f（K5）的每个连通分支应该是一个圆盘，于是我们就得到了一种用圆盘沿着边粘出S2的方法，粘出来有5个顶点，10条边，至多6个面.因此我们有欧拉数2=χ（S2）≤5+6-10=1，这是一个矛盾，也就是完全图K5不可能嵌入到S2.

下面再证二部图K3，3也不可能嵌入到S2.

假设存在这样的嵌入f：K3，3→S2，由于K3，3中四条边才能构成闭合回路（见图2 中的A1B1A2B2A1就是一个回路），这是因为K3，3在同一层的3个顶点没有相互连接，从而S2/f（K3，3）的每个连通分支至少要与K3，3中的4条边相邻，同时K3，3的每条边至多只与2个连通分支相邻.考虑到K3，3一共有条边，这就意味着S2/f（K3，3）至多有[9×2÷4]=4个连通分支.类似于K5的情形，此时我们粘出来有6个顶点，9条边，至多4个面.因此欧拉数2=χ（S2）≤6+4-9=1，这是一个矛盾，也就是二部图K3，3也不可能嵌入到S2.

[1]Kuratowski，Kazimierz.Surleproblèmedescourbesgauchesento pologie.Fund.Math inFrench，1930：271-283.

[2]徐俊明.图论及其应用[M].中国科技大学出版社，2010（03）.

[3]张先迪，李正良.图论及其应用[M].高等教育出版社，2005-02-01.

[4]迪斯特尔.图论[M].4 版.于青林，等译.北京：高等教育出版社，2013-01-01.

[5]阿姆斯特朗.基础拓扑学[M].孙以丰，译.人民邮电出版社，2010-04-01.