第9章树 证明①由树的定义可得(1) 施归纳于顶点数n。当n=1时,m=0,则m=n-1成立 假设当n=k时,m=n-1成立。则当n=H+1时,因为树 是连通的且无回路,所以至少有一个度数为1的顶点v, 从树中删去ν和与它关联的边,则得到k个顶点的树T 根据假设它有k-1条边,现将ν和与它关联的边加到T上 还原成树T,则7有k+1个顶点,k条边,边数比顶点数 少1,故m=n-1成立。第9章 树 证明 ①由树的定义可得（1）。 施归纳于顶点数n。当n=1时，m=0，则m=n-1成立。 假设当n=k时，m=n-1成立。则当n=k+1时，因为树 是连通的且无回路，所以至少有一个度数为1的顶点v， 从树中删去v和与它关联的边，则得到k个顶点的树T′ 。 根据假设它有k-1条边，现将v和与它关联的边加到T′上 还原成树T，则T有k+1个顶点，k条边，边数比顶点数 少1，故m=n-1成立