必要性:设G是2一连通图,欲证任二顶点L,v都在同一圈上。 对距离d(l,v)作归纳法。 d(l,)=1时,因x≥K≥2,故G中无割边,G-仍连通。因此G-中存在 条(u,v)路P。这表明在G中a,v都在圈P+上。 假定d(l,v)<k时,结论成立。下证d(u,v)=k时结论也成立。 当d(l,v)=k时,设f=l…wv是长为k的一条(u,v)路,则d(l,)=k-1。由归 纳法假设,l,w在同一圈上,故在t,w间有两条无公共内部顶点的路P和Q。因G是2连 通图,故G-仍连通。在G-中存在(,v)路P。令x是P上最后一个与PUQ的公 共顶点(因l∈P∪Q,这样的x存在)。不妨设x∈P,则P上(,x)段+P'上(x,v)段 与Q+w是两条内部无公共点的(,v)路。故,v在同一圈上。归纳法完成。证毕 推论23.1v≥3的图G是2连通图(块)当且仅当G中任二顶点被至少两条内部无公共顶 点的路所连 推论23.,2若v≥3的图G是2连通图(块),则G的任二边都位于同一圈上。 证明:设G是v≥3的2连通图,且e1e2∈E(G),在e1和e2上各添加一个新的顶点v1和 V2,构成一个新图G’。G’仍是2连通的。由 Whitney定理,v1和v2在G中位于同一个圈 上。故e1和e2在G中位于同一个圈上。证毕。 关于块的部分等价命题总结在下一个定理中。 定理23.2设G是v≥3的连通图,则下列命题等价 (1)G是2连通的(块) (2)G的任二顶点共圈 (3)G的任一顶点与任一边共圈 (4)G的任二边共圈; (5)对vu,v∈(G)及ve∈E(G),存在(u,v)路含有边e; (6)对vu,v,w∈F(G),存在(l,v)路含有顶点w (7)对vu,v,w∈F(G),存在(l,v)路不含有顶点v。 证明:(1)→(2)见 Whitney定理 (2)→(3)设G中任二顶点共圈。对veV(G)及ve=xy∈E(G),若x=或y=l, 则结论显然。以下假定x,y≠l。设C是含u与x的圈。若y∈C,则C上含有u的(x,y)7 必要性：设 G 是 2－连通图，欲证任二顶点 u, v 都在同一圈上。 对距离d(u, v) 作归纳法。 d(u, v) = 1时，因κ ′ ≥ κ ≥ 2 ，故 G 中无割边，G − uv 仍连通。因此G − uv 中存在 一条(u, v) 路 P1 。这表明在 G 中 u, v 都在圈 P + uv 1 上。 假定d(u, v) < k 时，结论成立。下证d(u, v) = k 时结论也成立。 当d(u, v) = k 时，设 P = u"wv 0 是长为 k 的一条(u, v) 路，则d(u,w) = k −1。由归 纳法假设，u, w 在同一圈上，故在 u, w 间有两条无公共内部顶点的路 P 和 Q。因 G 是 2 连 通图，故G − w仍连通。在G − w中存在(u, v) 路 P′ 。令 x 是 P′ 上最后一个与 P ∪ Q 的公 共顶点（因u ∈ P ∪ Q ，这样的 x 存在）。不妨设 x ∈ P ，则 P 上(u, x)段＋ P′ 上(x, v) 段 与Q + wv 是两条内部无公共点的(u, v) 路。故 u, v 在同一圈上。归纳法完成。证毕。 推论 2.3.1 ν ≥ 3的图 G 是 2 连通图（块）当且仅当 G 中任二顶点被至少两条内部无公共顶 点的路所连。 推论 2.3.2 若ν ≥ 3的图 G 是 2 连通图（块），则 G 的任二边都位于同一圈上。 证明：设 G 是ν ≥ 3的 2 连通图，且 , ( ) e1 e2 ∈ E G ，在 1 e 和 2 e 上各添加一个新的顶点 1 v 和 2 v ，构成一个新图G′。G′仍是 2 连通的。由 Whitney 定理， 1 v 和 2 v 在G′中位于同一个圈 上。故 1 e 和 2 e 在 G 中位于同一个圈上。证毕。 关于块的部分等价命题总结在下一个定理中。 定理 2.3.2 设 G 是ν ≥ 3的连通图，则下列命题等价： （1） G 是 2 连通的（块）； （2） G 的任二顶点共圈； （3） G 的任一顶点与任一边共圈； （4） G 的任二边共圈； （5） 对∀u, v ∈V(G) 及∀e ∈ E(G) ，存在(u, v)路含有边 e； （6） 对∀u, v,w∈V(G) ，存在(u, v)路含有顶点 w; （7） 对∀u, v,w∈V(G) ，存在(u, v)路不含有顶点 w。 证明：（1）⇒（2）见 Whitney 定理。 （2）⇒（3）设 G 中任二顶点共圈。对∀u ∈V(G) 及∀e = xy ∈ E(G)，若 x = u 或 y = u ， 则结论显然。以下假定 x, y ≠ u 。设 C 是含 u 与 x 的圈。若 y ∈C ，则 C 上含有 u 的(x, y) P P0 u P´ v Q x w