设T是一个（n,m）无向图,若T无圈且m=n-1,证明T为树

设T是一个（n,m）无向图,若T无圈且m=n-1,证明T为树
设T是一个（n,m）无向图,若T无圈且m=n-1,证明T为树

设T是一个（n,m）无向图,若T无圈且m=n-1,证明T为树
设该图为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