假设G有两个连通分支G1和G2,那么取v1是G1中度数最小的顶点,v2是G2中度数最小的顶点,则d(v1)+d(v2)≤n-2(等号在G1和G2都是完全图时取到),这与条件矛盾.
G是n阶简单无向图,如果图G中任意两点的度数之和大于等于n-1,证明图G是连通图
1个回答
相关问题
-
设G是n阶m条的无向连通图,证明m>=n-1
-
离散数学证明题设G是一个n阶无向简单图,n是大于等于3的奇数.证明图G与它的补图G`中的奇数度顶点个数相等.
-
设G是n(n>=2)阶欧拉图,证明G是2-边连通图
-
设无向连通图G有n个顶点,证明G至少有(n-1)条边.
-
1.证明:若无向图G不连通,则G的补图是连通的
-
设G是有n个结点,n条边的简单连通图,且G中存在度数为3的结点.证明:G中至少存在有一个度数为1的结点.
-
设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少有一个顶点的度数大于或等于3.
-
设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少有一个顶点的度数大于或等于3.
-
1.证明在具有n个顶点的简单无向图G中,至少有两个顶点的度数相同.
-
n是图G的阶数,G是自补图,证明n=4k或4k+1