西安电子科技大学$6.7.1 无向树软件学院（1）连通且无简单回路。证明：采用循环论证方法。2）无简单回路且m=n-1。(1) →(2)对树T中的结点数n进行归纳。当n-1时，必有m=0，因此有m-n-1成立。假设当n-k时命题成立，现证明当n=k+1时命题成立。由于树T是连通的且无简单回路，所以在树T中至少有一个度为1的结点V，从T中删除结点及其关联的一条边e，得到k个结点且无简单回路的连通图T-v。根据归纳假设T-v中有k-1条边.现将结点v及其关联的边e放回以而恢复原图T这样T中必含有k+1个结点和k条边，满足公式m-n-1。所以树是无简单回路且m-n-1的图。+西安电子科技大学 §6.7.1 无向树 软件学院 （1）连通且无简单回路。 （2）无简单回路且m=n-1