无向树的性质 定理1 (3)G中无回路,且m=n-1;(4)G是连通的,且m=n-1 证明:(3)→(4) 假设G不是连通的。不失一般性,设G包含S(S≥2个连通分 支G1G2,…,Gs,其中G(=1.s为n阶m条边且无回路,因此G1 全为树(i=1.s)。 由(1)→(2)→(3)可知,对于每个G有m1=n1-1。于是,m E=1.m=E=1.n4-s=n-s。由于s≥2,这显然与条件“m=n1” 相矛盾。所以,G是连通的7 无向树的性质 证明: (3) ⇒ (4) 假设G不是连通的。不失一般性, 设G包含s(s ≥ 2)个连通分 支G1, G2, …, Gs, 其中Gi(i=1..s)为ni阶mi条边且无回路, 因此, Gi 全为树(i=1..s)。 由(1)⇒(2)⇒(3)可知, 对于每个Gi, 有mi = ni-1。于是, m = Σi=1..smi = Σi=1..sni - s = n - s。由于s ≥ 2, 这显然与条件“m=n-1” 相矛盾。所以, G是连通的。 定理1. (3) G中无回路, 且m = n-1; (4) G是连通的, 且m = n-1