[问题求助] 各位高手，有8道基础菜鸟级图论题亟待解决！！！

[复制链接]

字体大小: 正常放大

东京流浪猫

3 主题	6 听众	14 积分

升级 9.47%

TA的每日心情

	慵懒 2013-4-20 18:12

签到天数: 3 天

[LV.2]偶尔看看I

自我介绍: 哈哈哈~~~

电梯直达

1^#

发表于 2013-1-19 12:25 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

1、拥有p个顶点，q条边，r个区域，kge连结成分的平面图G，满足等式p-q+r-k=1。证明之。
2、 K是奇数，请证明k正则图的顶点数为偶数。
3、 G是连通图。请证明G的任意两条最长路径都通过某个共同顶点。
4、 G是顶点数4个以上的2连通图。请证明以下两个命题等价:
(1) 从G删除相邻连接的顶点后将是非连通图；
(2) 两顶点之间相连的边收缩后的图不是2连通图。
5、请画一个不拥有1因子的3正则图。
6、请证明图K2，n的全域树的个数是n2n-1
7、 G是平面图。请证明G的任意平面图不持有相互邻接的5个面（包括外面）。
8、请画出拥有8条边且不包含三角形的最小顶点数的图。并证明这个图是最小顶点数的图，且有2个存在。

zan