证明(3)G中无回路且m=n-1.(4) G 是连通的且 m=n-1.(3)二(4).只需证明G连通.用反证法.否则G有s(s≥2)个连通分支，它们都是树.于是，有m=n一1,m=mi=ni- s= n- s (s ≥ 2)i=1i=1这与m=n-1矛盾.6
6 (3)(4). 只需证明G连通. 用反证法. 否则G有s(s2)个连通 分支, 它们都是树. 于是, 有mi=ni−1, 这与m=n−1矛盾. 证明 𝑚 = 𝑖=1 𝑠 𝑚𝑖 = 𝑖=1 𝑠 𝑛𝑖 − 𝑠 = 𝑛 − 𝑠 (𝑠 ≥ 2) (3) G 中无回路且 m=n−1. (4) G 是连通的且 m=n−1
证明(4)G是连通的且m=n-1.(5)G是连通的且G中任何边均为桥(4)二(5).只需证明G中每条边都是桥.下述命题显然成立：G是n阶m条边的无向连通图，则mzn-1VeEE,G-e只有n-2条边，由命题可知G-e不连通，故e为桥7
7 (4)(5). 只需证明G 中每条边都是桥. 下述命题显然成立: G 是 n 阶 m 条边的无向连通图，则 mn−1. eE, G−e只有n−2条边，由命题可知G−e不连通，故e为桥. 证明 (4) G 是连通的且 m=n−1. (5) G 是连通的且 G 中任何边均为桥