证明：若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,与条件矛盾
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
- 禹从部落联盟首领转变为奴隶制国家实力是历史的进步还是历史的倒退?
- 英文解释单词
- 甲乙两人从AB两地相向而行,甲的速度为akm/h,乙的速度比甲的速度的2倍少1km,6小时后,两人相距2km,
- 蛋白质变性的概念及本质是什么?有何实际应用?
- 1000kg立方米等于多少克立方厘米
- 说4级铵盐和2级胺盐,铵盐和胺盐有什麽区别啊胺盐的级别是什麽啊,
- 分解因式,要过程(x+y)^2-3(x+y)+2
- 一个茶叶罐,规格如右图所示,要在它侧面贴满一张商标,商标接头处为cm.这张商标纸的面积是多少?
- 一个最大2位数被5和3除都余2.这个数最大是多少?最小是多少?
- 介绍叙利亚闷热干燥
热门考点
- 英国历史上有哪几位出名的首相 附人物事迹
- a fun idea is to have a balloon release with special notes inside the balloons.4226 什么 is 后面接to have
- 是：它那么生气勃勃,天真可爱,我怎么会不喜欢它呢?改成陈述句.
- 有一个农夫带着一袋米、一只鸡和一只狼,要过河,河上有一条船,可是一次农夫只能拿一样东西过去,到底要
- 甲数的3/4和乙数的2/7相等,那么甲比乙少几分之几
- 2011-2012第一学期期末六年级数学测试试卷(附答案及解析) 人教版的 高坪区的
- 用matlab解M*DY/DT=mg-kv微分方程
- 1.(6√10)^2=360?(6倍的根号10的平方等于360?) 2.2√5-2怎么算?(2倍的根号5减去2怎么算?) 求详
- 在长80m,宽50m的矩形草坪的周边上修一条宽为2m的环形人行道,则余下的草坪的面积为?
- 当A为何值时,关于x的方程3x-a=2的解为整数、负数或0