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

我也搜到“假设G有两个连通分支G1和G2，那么取v1是G1中度数最小的顶点，v2是G2中度数最小的顶点，则d(v1)+d(v2)≤n-2（等号在G1和G2都是完全图时取到），这与条件矛盾。” 我希望有一个正规的步骤……我确实不懂这个……

举报该问题

推荐答案 2012-01-05

假设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，与条件矛盾

温馨提示：答案为网友推荐，仅供参考

当前网址：http://22.wendadaohang.com/zd/0XfIC2T0C.html

相似回答

...图,如果图G中任意两点的度数之和大于等于n-1,证明图G是连通图_百度...答：任取G1中一点v1,G2中一点v2，则d(v1)≤|G1|-1,d(v2)≤|G2|-1；d(v1)+d(v2) ≤ |G1|+|G2|-2 ≤ n-2，与条件矛盾，故G只能是连通图。在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。

着急!《离散数学》两个选择题!答：定理1 若图G=<V,E>具有汉密尔顿回路，则对于结点集V的每个非空子集S均有 W(G-S)≤|S|成立。其中W(G-S)是G-S中连通分支数。定理2 设G具有n个结点的简单图，如果G中每一对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路。定理3 设G是具有n个结点的简单图。如果G中每一对结点度...

大家正在搜

n阶k正则图G的变数是设G为有m条边的n阶无向图证明群G的中心是一个不变子群已知n阶无向图G中有m条边证明G与E和泊松比的关系怎么证明HN是G的不变子群证明H是G的子群设G是n阶完全图对下列各题分别证明G是否为F

无论有向图还是无向图，顶点数n，边数e和度数之间有什么关系

设9阶无向图的每个顶点的度数为5或6，至少有几个5度顶点，求...

设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少...

怎样证明在N个顶点的简单无向图中至少有两个顶点的度数相同