离散数学 证明 (4)→（⑤）.只需证明G中每条边都是桥.下述命题显然成立：G 是n阶m条边的无向连通图，则m心n-1. Ve∈E,G-e只有n-2条边，由命题可知G-e不连通，故e为桥 (⑤)=→>（⑥.由（⑤）易知G为树.由(1)→(2)知，u,veV(u≠v), u到v有惟一路径，加新边(w,)得惟一的一个圈. (6)→(1).只需证明G连通，这是显然的. 55 (4)(5). 只需证明G 中每条边都是桥. 下述命题显然成立: G 是 n 阶 m 条边的无向连通图，则 mn−1. eE, G−e只有n−2条边，由命题可知G−e不连通，故e为桥. 证明 (5)(6). 由(5)易知G为树. 由(1)(2)知，u,vV（uv）, u到v有惟一路径，加新边(u,v)得惟一的一个圈. (6)(1). 只需证明G连通，这是显然的