设该图为G.只需要证明G是连通的.用反证法.
设G是不连通的,G含s个连通分图G1,G2,……Gs,(s>=2）.因每个Gi（i=1,2,……s)是连通的,并且不含圈,故每个Gi是树.设Gi有pi个点,则Gi有pi-1条边,于是
q(G)=q(G1)+q(G2)+……+q(Gs)=(p1-1)+(p2-1)+……+ps-1)=p(G)-s
设T是一个（n,m）无向图,若T无圈且m=n-1,证明T为树
1个回答
相关问题
-
设G是n阶m条的无向连通图,证明m>=n-1
-
m,n均为三维单位列向量且(m^T)n=0,令A=m（n^T）+n（m^T）证明A与对角阵【1,-1,0】相似
-
集合M={1,t},N={t2-t+1},若M U N=M,那么t的值是什么?
-
已知m={1,t},n={t∧2－t+1},若m并n=m,求t的取值集合.
-
一道数学命题证明若a^m=b^n,且a,b,m,n都为正整数,m,n互质,求证命题“必存在正整数t,使a=t^n,b=t
-
对于集合M,N,定义M–N={x|x∈M,且x不包含于N},M*N=(M–N)∪(N–M),设A={t∣t=x2-3x
-
如果a＞b＞0，t＞0，设 M= a b ， N= a+t b+t ，那么（ ） A．M＞N B．M＜N C．M=N
-
判断题,设T为n维线性空间V的线性变换,V中向量组α1,α2,...,αm线性无关,则Tα1,Tα2,...Tαm线性无
-
若(m-n/2)^2=(m^2+n^2/2)+t,则t=( )
-
数列 {an }为等差数列m,n,s,t∈N*且m+n=s+t 求证am+an=as+at