无向树的性质 定理1 (2)G中任意两个顶点之间存在唯一的路径;(3)G中无回路,且m=n-1 证明:(2)→(3) 先证明G中无回路。若G中存在关联某顶点V的环,则v到存在长为0 和1的两条路径,这与已知矛盾。若G中存在长度大于或等于2的圈,则圈上 任何两个顶点之间都存在两条不同的路径,这也与已知条件矛盾。 下面用归纳法证明:m=n-1。 当n=1时,G为平凡图,结论显然成立 假设n≤k(k≥1)时,结论成立 当n=k+1时,设e={u,v)为G中的一条边,由于G中无回路,所以,G-e 有两个连通分支G1和G2。设n和m分别为G中的顶点数和边数,则n1≤k(i =1,2)。由归纳假设可知,m=n1,于是m=m1+m2+1=n1+n2+1-2=n-16 无向树的性质 定理1. (2) G中任意两个顶点之间存在唯一的路径;(3) G中无回路, 且m = n-1 证明: (2) ⇒ (3) 先证明 G中无回路。若G中存在关联某顶点v的环, 则v到v存在长为0 和1的两条路径, 这与已知矛盾。若G中存在长度大于或等于2的圈, 则圈上 任何两个顶点之间都存在两条不同的路径, 这也与已知条件矛盾。 下面用归纳法证明: m = n-1。 当 n = 1时, G为平凡图, 结论显然成立。 假设n ≤ k(k ≥ 1)时, 结论成立。 当n = k+1时, 设e = (u, v)为G中的一条边, 由于G中无回路, 所以, G-e 有两个连通分支G1和G2。设ni和mi分别为Gi中的顶点数和边数, 则ni ≤ k (i = 1, 2)。由归纳假设可知, mi = ni-1, 于是 m=m1+m2+1=n1+n2+1-2=n-1