③→④只须证明G是连通的。若不然,设G 有2)个连通分支G1,G2,…,G,G中均无 回路,都是树。由①→②→③可知,m=n1 i=1,…。于是mm+m2+…+m1=m1-1+m2-1 +…+nr1=n1+n2+…+nr′=nt,由于仑2,这 与m=n-1矛盾。所以G是连通图。 ④→⑤只须证明G的每一条边均为桥。设e是 的任意边,删除e得子图G1,G中的边数m1=m 1,G1中的结点数n1=n,m1=m-1=n-1-1=n-2=n12 <n1-1,所以G不是连通图,所以e是桥。③④只须证明G是连通的。若不然，设G 有t(t≥2)个连通分支G1，G2，…，Gt，Gi中均无 回路，都是树。由①②③可知，mi =ni –1， i=1,…,t。于是m=m1＋m2＋…＋mt =n1 -1＋n2 -1 ＋…＋nt -1=n1＋n2＋…＋nt -t=n–t，由于t≥2，这 与m=n–1矛盾。所以G是连通图。 ④⑤只须证明G的每一条边均为桥。设e是 G的任意边，删除e得子图G1，G1中的边数m1 =m- 1，G1中的结点数n1 =n，m1 =m–1=n-1-1=n-2=n1 -2 ＜n1 -1，所以G1不是连通图，所以e是桥