问一道图论题：设简单连通图G的结点数是15,其中8个点的度是4,6个点的度是6,一个点的度是8,证明G是非平面图.

Question

问一道图论题：
设简单连通图G的结点数是15,其中8个点的度是4,6个点的度是6,一个点的度是8,证明G是非平面图.

Answer 1

我对图论也不是很熟悉,我试一下吧．提供给你参考．
证明：
首先,根据条件得到：
边数为：（4＊8＋6＊6＋8）／2＝38
假设G是平面图
根据欧拉定理知道,面数等于：
38＋2－15＝25
根据假设,面的总长度是：38＊2＝76
所以,G的面有24个长度为3,1个长度为4
不可能有别的可能．
设度为8的结点为P
分两种情况：
1．P不在长度为4的面上．
设和P相连的八个点为：A1,A2,．．．,A8
根据假设．由A1,A2．．．,A8,P组成的子图为
如下：
A1,A2．．．,A8组成一个八边形．
P在八边型内部,P和A1,．．．,A8都有一条连
线．
和A1相连的有A2,A8,P
和A2相连的有A3,A1,P
．．．
和A8相连的有A1,A7,P．
剩下的六个点记为：B1,B2．．,B6
首先,A1．．．A8里面必然有度为6的点．
否则,由B1,．．,B6组成的子图是非平面图．
（这个通过欧拉公式可推出,此处从略）
不妨设A1为度为6的点．
设A1与B1,B2,B3相连．
必有点与A3连,且该点不可能是B1,B2,B3
否则,（比如是B1）,P－A1－B1－A3为长度为四的面．矛盾
所以设与A3连的是B4
同理,设与A5连的是B5
设A7连的是B6
现在看B4这点．
根据上面分析,B4不可能与P,A1,A5,A6,A7,A8,中任意点连．
同时,B4不能和B1,B2,B3,B5,B6中任意点连,否则．（比如B6）
则,P－A3－B4－B6－A7－P
组成长度为5的面．矛盾．
所以B4的度为3,根据题意,矛盾．
所以排除这种情况．
2．P在长度为4的面上．
分析方法类似于1,己于人这里不再重复写．如果问题你补充．