定理2：设图T是一个具有n个顶点的树，则其边数e=-1, 证明：对n作数学归纳：当n=1时，T=K,从而e=0,结论成立！ 假设当n=k时结论成立，下面考虑具有k+1个顶点的树T。 因为T不含有圈，并且连通，所以T的最小度恰好为1（为什 么？)。于是设T中有一条边uv,其中u的度数为1。 现将u从图T中删去，得到图T-u.容易看出，T-u必定无圈， 并且是连通的（为什么？)。也就是说，T-u是一个具有k+1-1=k个 顶点的树，从而由归纳假设，T-u有k-1条边。 因此，T有k-1+1=k条边！定理 2：设图 T 是一个具有 n 个顶点的树，则其边数 e=n-1. 证明：对 n 作数学归纳：当 n=1 时，T=K1，从而 e=0，结论成立！ 假设当 n=k 时结论成立，下面考虑具有 k+1 个顶点的树 T。 因为 T 不含有圈，并且连通，所以 T 的最小度恰好为 1（为什 么?）。于是设 T 中有一条边 uv，其中 u 的度数为 1。 现将 u 从图 T 中删去，得到图 T-u.容易看出，T-u 必定无圈， 并且是连通的（为什么？）。也就是说，T-u 是一个具有 k+1-1=k 个 顶点的树，从而由归纳假设，T-u 有 k-1 条边。 因此，T 有 k-1+1=k 条边！