G是n阶简单无向图，如果图G中任意两点的度数之和大于等于n-1，证明图G是连通图

Question

如题所述

Answer 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只能是连通图。

在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。

如果此图是有向图，则称为强连通图。而无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。

扩展资料：

连通图性质

一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。

如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。

没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。

参考资料：百度百科-连通图

Answer 2

G是n阶简单无向图，如果图G中任意两点的度数之和大于等于n-1，证明图G是连通图

假设G有两个连通分支G1和G2，那么取v1是G1中度数最小的顶点，v2是G2中度数最小的顶点，则d(v1)+d(v2)≤n-2（等号在G1和G2都是完全图时取到），这与条件矛盾。

Answer 3

假设G有两个连通分支G1和G2，那么取v1是G1中度数最小的顶点，v2是G2中度数最小的顶点，则d(v1)+d(v2)≤n-2（等号在G1和G2都是完全图时取到），这与条件矛盾。