证明:(1)→(2):T是无回路的连通图要证明T是无回路 图,且e=n-1,即证明e=n-1 对顶点数n采用归纳法,n=2时,因为T是无回路的连通图, 显然只能是下图所示: 故结论成立。 假设n=k时结论成立现考察n=k+1时,由于连通无回路以 及定理54 (若图G中每个顶点度数至少为2,则G包含一条回路), 可以知道至少有一个顶点度数为的点u它的关联边为 uv}。证明：(1)→(2): T是无回路的连通图要证明T是无回路 图,且e=n-1，即证明e=n-1 对顶点数n采用归纳法,n=2时,因为T是无回路的连通图， 显然只能是下图所示： 故结论成立。 假设n=k时结论成立,现考察n=k+1时,由于连通无回路以 及定理 5.4 (若图G中每个顶点度数至少为2,则G包含一条回路), 可以知道至少有一个顶点度数为1的点u,它的关联边为 {u,v}