回路v1v6v3v4v1构成一个Jorand曲线，设其为C，如图7-19（b），顶点v2或在ext（C）中，不妨假定v2∈int（C），于是边v2v4，v2v6 将int（C）分成两个区域。设C1=v1v4v2v6v1，G2=v4v2v6v3v4,v5必然位于ext（C），int（C1），int（C2）三个区域之一。 (1) 若v5∈int（C），则v2v5与C相交，与K3..3是平面图矛盾。 (2) 若v5∈int（C1），则v3v5与C1相交，也矛盾。 (3) 若v5∈int（C2），则v1v5与C2相交，同样产生矛盾。 同理可证，当v2∈ext（C）时，也产生矛盾。 故假设不成立，即K3..3不是平面图。
V1
V2
V1
V6
Int(C1)
Ext(C)
V4
V5
V6 V4
（a） (b)
图7-19
24 设G是连通平面图，最短回路长度是k（k≥3），边数为u，顶点数为v，证明 u≤k(v-2)/(k-2) 证 因为最短回路长度是，而平面图的每一个面是由一个回路所围起来的，因此对于任一个面都有，于是有
∑f∈F(G)dG(f)≥k＆ 其中＆是图G的面数。
再由∑f∈F(G)dG(f)=2u
可知2u≥k＆，即2u/k≥＆，根据欧拉公式可得 v-u+2u/k≥2
由此可以推出u≤k(v-2)/(k-2).
25 利用上题结果说明下面各图不是平面图。
V3
11
（a） （b） 图7-20
解 图7-20（）中：边数u=9，顶点数v=6，最短路长k=4，因为
u=9≦k（v-2）/（k-2）=8 于是，由上题结果可知7-20（a）不是平面图。
图7-20（）中：边数u=15，顶点数v=10，最短路长k=5，因为 u =15≦k（v-2）/（k-2）=40/3 因此7-20（b）不是平面图。
26 若是平面图，并且的所有面全由长度为3的回路围成，证明：u=3v-6。
证 因为中所有面由长度为3的回路围成，因此对任意f∈F(G)，都有dG(f)=3，从而∑f∈其中﹠为F(G)dG(f)=3﹠。代入欧拉公式，得
v-u+2u/3=2
即 u=3v-6 证毕。
G的面数。再由∑f∈F(G)dG(f)=2u，其中u为G的边数，可得3﹠=2u，
12
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库tulun(3)在线全文阅读。
相关推荐：