●证明方法: (1)→(2) ●(2)→(3) ●(3)→(4) ●(4)→(1) ●/参考定理10.1,1.2证明M
证明方法： (1)(2) (2)(3) (3)(4) (4)(1) /* 参考定理10.1, 11.2证明 */
(1)→>(2):归纳法证明 设l,是G的任意两点,d(,v是从u到v的距离。 对d1,y)用归纳法 ●当d1u,v)=1时,由于G中没有割点且n>3,因而 G是2连通的,kG≌2。由定理11, k(G)≤(G)sx(G)。所以G>2。于是可知{,y不 是桥,因此G-{,v仍连通,即从u到v有一条含 有其他顶点的路,与{,吵构成一条回路,也即 y在同一回路上
(1)(2)：归纳法证明 设u, v是G的任意两点，d(u, v)是从u到v的距离。 对d(u, v)用归纳法。 当d(u, v)=1时，由于G中没有割点且n3，因而 G是2-连通的，k(G)2。由定理11.1， k(G)(G)(G)。所以(G)2。于是可知{u, v}不 是桥，因此G-{u, v}仍连通，即从u到v有一条含 有其他顶点的路，与{u, v}构成一条回路，也即 u, v在同一回路上
●假设d(,y)=k-1时结论成立。当du,y=k时,令 是u到长度k的路上v的相邻点。因du,w)=k-1 按归纳假设G中有一条包含lw的回路C。又因 G没有割点,所以G-}是连通的,且含有一条 l到的路p。设x是p上与回路C相交的最后一个 顶点,x也可能就是u。不失一般性,假设x∈C, 于是G中有一条含有和v的回路:在C上u到x的 条路,并上p上的x到v的一条路,并上边h 吵,再并上在C上到l的一条路
假设d(u, v)=k-1时结论成立。当d(u, v)=k时，令 w 是 u 到 v长度 k的路上 v的相邻点。因d(u, w)=k-1 ， 按归纳假设 G中有一条包含u, w的回路 C。又因 G没有割点，所以G-{w}是连通的，且含有一条 u 到 v的路p。设 x 是p上与回路 C相交的最后一个 顶点， x也可能就是 u。不失一般性，假设 x C ， 于是 G中有一条含有 u 和 v的回路：在 C 上 u 到 x 的 一条路，并上p上的 x 到 v的一条路，并上边{w, v}，再并上在 C 上 w 到 u的一条路
(2)=(3) ●设u是任意一个顶点,{,W是任一边, 由(2)可知,存在包含u和v的回路C, 若W∈C,则即得证;若WC,由(2) u,Ww在同一回路上,那么v一定不是割点 所以必存在不含顶点V的从W到u的路p。 设X是p与C相交的第一个顶点,则W到x 沿C经u到v,最后回到w的回路即所要求 的回路
(2)(3) 设u是任意一个顶点，{v, w}是任一边， 由（2）可知，存在包含u和v的回路C， 若wC，则即得证；若wC，由（2）， u, w在同一回路上，那么v一定不是割点。 所以必存在不含顶点v的从w到u的路p。 设x是p与C相交的第一个顶点，则w到x 沿C经u到v，最后回到w的回路即所要求 的回路
(3)=(4) ●与(2)→(3)的证明类似
(3)(4) 与(2)(3)的证明类似