对于G的任何一个分支,从中任选一个点,然后把和它相连的点(δ(G)>=|p/2| => 至少|p/2|个和它相连的点)算在一块就有|P/2|+1个点了,所以这个分支里至少有|P/2|+1个顶点.
所以G的每个分支至少有|P/2|+1个顶点.
设G(p,q)是简单图.δ(G)>=|p/2|,则G必连通.怎么证明?
1个回答
相关问题
-
图论题,设G是有p顶点的图,δ(G)>=((p+k)-1)/2,试证：G是k-连通的.
-
设G是n(n>=2)阶欧拉图,证明G是2-边连通图
-
设命题公式G=┐（P→Q）∨（Q∧（┐P→R））,求G的主析取范式
-
有关平面图的问题设G为任意的连通平面图,则有n-m+r=( )；若G是简单连通平面图n>=3,则m<=(
-
设G是n>=3的连通图,证明若m>=0.5（n-1）（n-2）+2,则G存在哈密顿回路
-
1.证明：若无向图G不连通,则G的补图是连通的
-
G是n阶简单无向图,如果图G中任意两点的度数之和大于等于n-1,证明图G是连通图
-
设无向连通图G有n个顶点,证明G至少有（n-1）条边.
-
设G是n阶m条的无向连通图,证明m>=n-1
-
抽象代数证明：设(G,*)是一个群,如果 对所有的a属于G总有a^2=e,则G必是交换群