无向树的性质 定理1 (6)G中没有回路,但在任何两个不同的顶点之间加一条新边,在 所得图中得到唯一一个含新边的圈 (1)G是树 证明:(6)→(1).只要证明G是连通的。 vu,veV且u≠v,则(U,)UG产生唯一的圈,显然,有C-({u,v)为G中 u到v的通路,故,U~V。由u和v的任意性,所以G是连通的。 1010 无向树的性质 定理1. (6) G中没有回路, 但在任何两个不同的顶点之间加一条新边, 在 所得图中得到唯一一个含新边的圈 (1) G是树 证明: (6) ⇒ (1). 只要证明G是连通的。 ∀u, v∈V且u ≠ v, 则(u,v)∪G产生唯一的圈, 显然, 有C - (u,v)为G中 u到v的通路, 故, u ~ v。由u和v的任意性, 所以G是连通的