证明:若n阶简单无向图G的任意两个结点的度数之和大于等于n-1,则G是连通的.

证明:若n阶简单无向图G的任意两个结点的度数之和大于等于n-1,则G是连通的.

题目
证明:若n阶简单无向图G的任意两个结点的度数之和大于等于n-1,则G是连通的.
我也搜到“假设G有两个连通分支G1和G2,那么取v1是G1中度数最小的顶点,v2是G2中度数最小的顶点,则d(v1)+d(v2)≤n-2(等号在G1和G2都是完全图时取到),这与条件矛盾.” 我希望有一个正规的步骤……我确实不懂这个……
答案
假设G不是连通的
则G至少有两个连通分支G1和G2,有 |G1|+|G2| ≤ |G| = n
任取G1中一点v1,G2中一点v2
则d(v1)≤|G1|-1,d(v2)≤|G2|-1
d(v1)+d(v2) ≤ |G1|+|G2|-2 ≤ n-2,与条件矛盾
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
1,人们染上烟瘾,最终因吸烟使自己丧命.
最新试题
热门考点

超级试练试题库

© 2017-2019 超级试练试题库,All Rights Reserved.