正在加载图片...
路与边xy形成一个圈,它含有u及边 设ygC。由 Whitney定理,x不是割点。故存在不含x的(u,y)路P,令w是P上从y 出发第一个与C公共的顶点,则C上x段+P上(,y)段+xy构成一个含u和e=x 的圈 (3)→(4):与(2)→(3)类似可证。 (4)→(5):设G中任二边共圈。对V,v∈V(G)及ve∈E(G),如果e=u,结论显 然成立;如果或v之一是e的端点,比如u是e的端点而v的一个邻点是w,则e与边 wv共圈,故显然有(u,v)路含有边e 下面假定u和v都不是e的端点。 因任二边共圈显然任二点共圈,故由(2)→(3)知u与e共圈,v也与e共圈。设这 圈分别是C1和C2。若l∈C2或v∈C1,则结论成立;若u∈C2且v∈C1,则如下构作 含e的(u,v)路:从u出发沿C1到达C1与C2的第一个公共顶点w,再从w出发沿C2含e 的部分到达v,即可 (5)→(6):对Vu,v,w∈I(G),设与w相关联的一条边为e。由(5),存在(l,v)路含 有边e,于是含有w8 路与边 x y 形成一个圈,它含有 u 及边 e; 设 y ∉C 。由 Whitney 定理, x 不是割点。故存在不含 x 的(u, y) 路 P,令 w 是 P 上从 y 出发第一个与 C 公共的顶点,则 C 上 x-u-w 段+P 上(w, y) 段+xy 构成一个含 u 和 e = xy 的圈。 (3)⇒(4):与(2)⇒(3)类似可证。 (4)⇒(5):设 G 中任二边共圈。对∀u, v ∈V(G) 及∀e∈ E(G) ,如果e = uv ,结论显 然成立;如果 u 或 v 之一是 e 的端点,比如 u 是 e 的端点而 v 的一个邻点是 w,则 e 与边 wv 共圈,故显然有(u, v)路含有边 e。 下面假定 u 和 v 都不是 e 的端点。 因任二边共圈显然任二点共圈,故由(2)⇒(3)知 u 与 e 共圈,v 也与 e 共圈。设这 二圈分别是C1和C2 。若 C2 u ∈ 或 C1 v ∈ ,则结论成立;若 C2 u ∉ 且 C1 v ∉ ,则如下构作 含 e 的(u, v)路:从 u 出发沿C1到达C1与C2的第一个公共顶点 w,再从 w 出发沿C2含 e 的部分到达 v,即可。 (5)⇒(6):对∀u, v,w∈V(G) ,设与 w 相关联的一条边为 e。由(5),存在(u, v)路含 有边 e,于是含有 w。 x u y u w v e w C1 e v u C2 w x u y
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有