反证法.假设G中不存在度数为1的结点,G是连通图,所以G的结点的度数至少是2.
G有3度节点,所以G的所有结点的度数之和大于等于2(n-1)+3=2n+1.
而G有n条边,度数之和是2n.
矛盾.
所以G中至少存在有一个度数为1的结点.
设G是有n个结点,n条边的简单连通图,且G中存在度数为3的结点.证明：G中至少存在有一个度数为1的结点.
1个回答
相关问题
-
1、设G=,|V|=n,|E|=m,v是G中度数为k的结点,e是中一条边,则G\v（删去结点v）中有( )个结点,( )
-
设图G有6个结点,10条边,则6个结点的度数之和为多少
-
一棵树有两个结点度数为2,一个结点的度数为3,三个结点的度数为4,其余结点的度数为1,求出度数为1的结点个数
-
3.一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,问它有几个度数为1的结点?
-
设无向连通图G有n个顶点,证明G至少有（n-1）条边.
-
设哈夫曼树中共有n个结点,则该哈夫曼树中有几个度数为1的结点
-
离散数学关于图论的证明,求大神证明：图G连通，每个结点的度数均为偶数，则对G的任意结点v，w(G-v)
-
设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少有一个顶点的度数大于或等于3.
-
设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少有一个顶点的度数大于或等于3.
-
G是n阶简单无向图,如果图G中任意两点的度数之和大于等于n-1,证明图G是连通图