欧拉图的性质:例子 例:设G是非平凡的且非环的欧拉图,证明 (1)(G)≥2 (2)yu,v∈V(G),u≠v,则G中都存在包含u和v的简单回路 证明: (1)由G是欧拉图,可知Ve∈E(G,存在圈C:e在C中。因此,p(Ge) p(G),所以,e不是桥。由e的任意性可知:(G)≥2,即G是2边-连通图 (2)u,veV(G),u≠V,由G的连通性可知:u和v之间必存在路径r1 设G’=G一E(I,则在G’中u与V还必连通,否则,u与v必处于G的不 同的连通分支中,这说明r1中存在G中的桥,这与(1)矛盾。 于是,在G中存在U到v的路径r2,显然1与I2边不重,这说明:u和v处 于由r1Ur2形成的简单回路上。 1010 欧拉图的性质: 例子 (1) 由G是欧拉图, 可知 ∀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形成的简单回路上。 例: 设G是非平凡的且非环的欧拉图, 证明: (1) λ(G) ≥ 2 (2) ∀u, v ∈ V(G), u ≠v, 则G中都存在包含u和v的简单回路 证明: