无向树的性质 定理1 (4)G是连通的,且m=n-1;(5)G是连通的,且G中任何边均为桥 证明:(4)→(5) ve∈E,从G中删除e后,均有E(G-e)=n-1-1=n-2,vG-e)=m 由“n阶m条边的无向连通图,则m≥n-1”,可知Ge不是连通图,故e 为桥,也即G中每条边均为桥 可通过对n做数学归纳法证明:“n阶m条边的无向连通图,则m8 无向树的性质 定理1. (4) G是连通的, 且m = n-1; (5) G是连通的, 且G中任何边均为桥 证明: (4) ⇒ (5) ∀e∈E, 从G中删除e后, 均有E(G-e) = n-1-1 = n-2, V(G-e)=m. 由“n阶m条边的无向连通图, 则m ≥ n-1”, 可知 G-e不是连通图, 故e 为桥, 也即G中每条边均为桥. 注: 可通过对n做数学归纳法证明: “n阶m条边的无向连通图, 则m ≥ n-1