证明：若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都是完全图时取到），这与条件矛盾。” 我希望有一个正规的步骤……我确实不懂这个……
展开
1个回答
展开全部
假设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，与条件矛盾
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
