一个图论问题的简单证明

《一个图论问题的简单证明》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一个图论问题的简单证明摘要：通过引入拓扑中的一个不变量__欧拉示性数来证明图论中的一个重要定理。关键词：库拉图斯基定理;可平面图;定理中国分类号：029文献标识码：A从库拉图斯基定理的证明以来，很多书本都引入这个定理，它也是证明一个图是否是可平面图的基本定理，同时也是一个平面图着色的基础。本文就是通过一种容易理解和简短的证明这个有用的定理.一、知识简介库拉图斯基定理图G是可平面图当且仅当G中既不含与K5同胚的子图，也不含与K3，3同胚的子IsI.定义1（点连通）设X是一个拓扑空间，X，yex,如果X中有一个连通子集同时包含x和y

2、，我们称点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—共有C25=10条边，这就意味着S2/f(K5)至多有［2X4+3］=6个连通分支，这里［

3、x］表示取整函数.同时S2/f(K5)的每个连通分支应该是一个盘，于是我们就得到了一种用圆盘沿着边粘出S2的方法，粘出来有5个顶点，10条边，至多6个面.因此我们有欧拉数2=x(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条边相邻，

4、同时K3,3的每条边至多只与2个连通分支相邻.考虑到K3,3—共有3C13=9条边，这就意味着S2/f(K3,3)至多有[9X2+4]=4个连通分支.类似于K5的情形，此时我们粘出来有6个顶点，9条边，至多4个面.因此欧拉数2=x(S2)6+4-9=1,这是一个矛盾，也就是二部图K3，3也不可能嵌入到S2.参考文献：[1]Kuratowski，Kazimierz.Surleproblemedescourbesgauchesentopologie.Fund.MathinFrench，1930：271-283.[2]徐俊明.图论及其

5、应用[M].中国科技大学出版社，2010(03).[3]张先迪，李正良.图论及其应用[M].高等教育出版社，2005-02-01.[4]迪斯特尔.图论[M].4版.于青林，等译.北京：高等教育出版社，2013-01-01.[5]阿姆斯特朗.基础拓扑学[M].孙以丰，译.人民邮电出版社，2010-04-01.作者简介：邢振宇，硕士研究生，研究方向：计算机代数与代数几何。