定理:设G=VE是无向图,||=n,|E|=m,则下列 各命题是等价的: ①G是树。 ②G中每一对结点之间存在惟一的路。 ③G中无回路且m=n-1。 ④G是连通的且m=n-1。 ⑤G是连通的且G中任何边均为桥 ⑥G中无回路,但在任何两个不同的结点之间增加 个新边,得到一个惟一的含新边的回路。 证明:④→② G是树,所以G是连通的,Ⅴu∈V,Vv∈V,u和v之 间存在一条路。着路不惟一,设L1和L都是u和V之间的 路,则L和L2组成了G中的一个回路,与G是树矛盾。定理：设G=V,E是无向图，|V|=n，|E|=m，则下列 各命题是等价的： ① G是树。 ② G中每一对结点之间存在惟一的路。 ③ G中无回路且m=n–1。 ④ G是连通的且m=n–1。 ⑤ G是连通的且G中任何边均为桥。 ⑥ G中无回路，但在任何两个不同的结点之间增加一 个新边，得到一个惟一的含新边的回路。 证明：①② G是树，所以G是连通的，uV，vV，u和v之 间存在一条路。若路不惟一，设L1和L2都是u和v之间的 路，则L1和L2组成了G中的一个回路，与G是树矛盾