题目
证明:若n阶简单无向图G的任意两个结点的度数之和大于等于n-1,则G是连通的.
我也搜到“假设G有两个连通分支G1和G2,那么取v1是G1中度数最小的顶点,v2是G2中度数最小的顶点,则d(v1)+d(v2)≤n-2(等号在G1和G2都是完全图时取到),这与条件矛盾.” 我希望有一个正规的步骤……我确实不懂这个……
我也搜到“假设G有两个连通分支G1和G2,那么取v1是G1中度数最小的顶点,v2是G2中度数最小的顶点,则d(v1)+d(v2)≤n-2(等号在G1和G2都是完全图时取到),这与条件矛盾.” 我希望有一个正规的步骤……我确实不懂这个……
提问时间:2021-01-02
答案
假设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,与条件矛盾
则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,人们染上烟瘾,最终因吸烟使自己丧命.
最新试题
热门考点
- 1英国历史上有哪几位出名的首相 附人物事迹
- 2a fun idea is to have a balloon release with special notes inside the balloons.4226 什么 is 后面接to have
- 3是:它那么生气勃勃,天真可爱,我怎么会不喜欢它呢?改成陈述句.
- 4有一个农夫带着一袋米、一只鸡和一只狼,要过河,河上有一条船,可是一次农夫只能拿一样东西过去,到底要
- 5甲数的3/4和乙数的2/7相等,那么甲比乙少几分之几
- 62011-2012第一学期期末六年级数学测试试卷(附答案及解析) 人教版的 高坪区的
- 7用matlab解M*DY/DT=mg-kv微分方程
- 81.(6√10)^2=360?(6倍的根号10的平方等于360?) 2.2√5-2怎么算?(2倍的根号5减去2怎么算?) 求详
- 9在长80m,宽50m的矩形草坪的周边上修一条宽为2m的环形人行道,则余下的草坪的面积为?
- 10当A为何值时,关于x的方程3x-a=2的解为整数、负数或0