15,1 例15.1设G是非平凡的且非环的欧拉图,证明 (1)入G)≥2 (2)对于G中任意两个不同顶点u,,都存在简单回路C含u和v 证明(1)由定理155可知,ve∈E(G,存在圈C,e在C中 因而p(G-e)=p(G,故e不是桥。 由e的任意性λ(G≥2,即G是2边-连通图。 (2)u,v∈V(G,u≠v,由G的连通性可知,,v之间必存在路径 「1,设G′=GE(「1,则在G中n与还必连通, 否则,u与w必处于G'的不同的连通分支中, 这说明在「1上存在G中的桥,这与(1)矛盾。 于是在G中存在u到v的路径「2,显然「与「2边不重, 这说明u,v处于「1U「2形成的简单回路上。例15.1 例15.1 设G是非平凡的且非环的欧拉图，证明： (1)λ(G)≥2。 (2)对于G中任意两个不同顶点u,v，都存在简单回路C含u和v。 证明 (1)由定理15.5可知，e∈E(G)，存在圈C，e在C中， 因而p(G-e)＝p(G)，故e不是桥。 由e的任意性λ(G)≥2，即G是2边-连通图。 (2)u,v∈V(G)，u≠v，由G的连通性可知，u,v之间必存在路径 Г1，设G ＝G-E(Г1 )，则在G 中u与v还必连通， 否则，u与v必处于G 的不同的连通分支中， 这说明在Г1上存在G中的桥，这与(1)矛盾。 于是在G 中存在u到v的路径Г2，显然Г1与Г2边不重， 这说明u,v处于Г1∪Г2形成的简单回路上