(6)→(7):对V,v,w∈V(G),存在(u,)路P含有顶点v,则P的从u到v的一段 不含有w (7)→(1):因为对vw∈(G)及va,v∈F(G),存在(u,v)路不含有顶点w,故w不 是割点。由w的任意性,G无割点。从而G是块。 证毕 §24 Menger定理 上节的 Whitney定理表明,对一个图G,G的最小点割集含至少2个点当且仅当G 中任意两点间都有至少2条内部点不交的路,即“分离”G中任意两点所需删除的最少顶点 数和这两点间内部点不交路的最大条数要么都大于等于2,要么都不超过2。这涉及到图的 连通性能的两个度量:删除顶点时图保持连通的能力和顶点间不交路径的重数。 Whitney定 理说明对2连通图这两种连通性度量是等价的。下列 Menger定理显示,这一结论对任意k 连通图都成立。 设G是一个简单图,x,y是G中任二不同顶点。如果从G中删去一组顶点后不再有 (x,y)路则称这组顶点分离x和y,而称这组顶点为一个(x,y)分离集。G中含点数最少的(x,y) 分离集称为最小x,y)分高集,其顶点数称为G的(x,y分高数,记为s(x,y)。此外,将G中 两两内部点不交的(x,y)路的最大条数记为r(x,y) 定理241( Menger,1927)对任意图G,设x,y是G中两个不相邻顶点,则G中分离x,y 所需的最少顶点数等于G中两两内部点不交的(x,y)路的最大条数,即s(x,y)=r(x,y) 证明:首先,对任意图G和G中任意两个不相邻顶点x,y,显然有sx,y)≥r(x,y)。下面用 反证法证明对任意图G和G中任意两个不相邻顶点x,y,s(x,y)≤r(x,y) 假设结论不真。则存在图G和G中两个不相邻顶点x,y,使得s(x,y)>r(x,y)。取G为 具有这种性质的所有图中顶点数最少并且边数最少的一个,即:对具有上述性质的任何一个 图H,要么D(G)<D(H),要么U(G)=D(H)且(G)≤(H)。 下面证明该图G的四条结论 (1)按照上述取法,由于s(x,y)>rx,y)≥0,可知G是连通图。如果s(x,y)=1,则必 须r(x,y)=0,这与G是连通图矛盾。因此sx,y)>1。 (2)对G的任二异于x,y的相邻顶点u和v,存在G的顶点子集U,满足|U=s(x,y)-1 且UU{础}和UU{v}都是G的(x,y)分离集。 事实上,设e=l,H=G-e。H的(x,y)分离数 SH(x,y)≥s(x,y)-1,(* (否则存在H的(x,y)分离集R使得|Rsx,y)-2,则RU{}是G的(x,y)分离集,且只含 s(x,y)-1个点,这与G的(x,y)分离数为sx,y)矛盾)。另一方面,由于s(x,y)>r(x,y),H中 两两内部点不交的(x,y)路的条数 n(x,y)≤r(x,y)≤s(x,y)-1。(*)9 （6）⇒（7）：对∀u, v,w∈V(G) ，存在(u,w) 路 P 含有顶点 v，则 P 的从 u 到 v 的一段 不含有 w。 （7）⇒（1）：因为对∀w∈V(G) 及∀u, v ∈V(G) ，存在(u, v)路不含有顶点 w，故 w 不 是割点。由 w 的任意性，G 无割点。从而 G 是块。 证毕。 §2.4 Menger 定理 上节的 Whitney 定理表明，对一个图 G，G 的最小点割集含至少 2 个点当且仅当 G 中任意两点间都有至少 2 条内部点不交的路，即“分离”G 中任意两点所需删除的最少顶点 数和这两点间内部点不交路的最大条数要么都大于等于 2，要么都不超过 2。这涉及到图的 连通性能的两个度量：删除顶点时图保持连通的能力和顶点间不交路径的重数。Whitney 定 理说明对 2 连通图这两种连通性度量是等价的。下列 Menger 定理显示，这一结论对任意 k 连通图都成立。 设 G 是一个简单图，x, y 是 G 中任二不同顶点。如果从 G 中删去一组顶点后不再有 (x, y)路则称这组顶点分离 x 和 y，而称这组顶点为一个(x, y)分离集。G 中含点数最少的(x, y) 分离集称为最小(x, y)分离集，其顶点数称为 G 的(x, y)分离数，记为 s(x, y)。此外，将 G 中 两两内部点不交的(x, y)路的最大条数记为 r(x, y)。 定理 2.4.1（Menger, 1927）对任意图 G，设 x, y 是 G 中两个不相邻顶点，则 G 中分离 x, y 所需的最少顶点数等于 G 中两两内部点不交的(x, y)路的最大条数，即 s(x, y) = r(x, y)。 证明：首先，对任意图 G 和 G 中任意两个不相邻顶点 x, y，显然有 s(x, y)≥ r(x, y) 。下面用 反证法证明对任意图 G 和 G 中任意两个不相邻顶点 x, y，s(x, y) ≤ r(x, y)。 假设结论不真。则存在图 G 和 G 中两个不相邻顶点 x, y，使得 s(x, y) > r(x, y)。取 G 为 具有这种性质的所有图中顶点数最少并且边数最少的一个，即：对具有上述性质的任何一个 图 H，要么υ(G) (H) < υ ，要么υ(G) (H) = υ 且ε (G) (H) ≤ ε 。 下面证明该图 G 的四条结论。 （1）按照上述取法，由于 s(x, y) > r(x, y) ≥ 0，可知 G 是连通图。如果 s(x, y)=1，则必 须 r(x, y)=0,这与 G 是连通图矛盾。因此 s(x, y) > 1。 （2）对G的任二异于x, y的相邻顶点u和v，存在G的顶点子集U，满足|U| ( , ) 1 = − sxy 且 U {} ∪ u 和 U {} ∪ v 都是 G 的(x, y)分离集。 事实上，设 e = uv，H = G − e。H 的(x, y)分离数 sH (x, y) ≥ s(x, y) −1， (∗) （否则存在 H 的(x, y)分离集 R 使得|R|≤ s(x, y) −2，则 R {} ∪ u 是 G 的(x, y)分离集，且只含 s(x, y) −1 个点，这与 G 的(x, y)分离数为 s(x, y)矛盾）。另一方面，由于 s(x, y) > r (x, y)，H 中 两两内部点不交的(x, y)路的条数 (, ) Hr xy ≤ r (x, y)≤ s(x, y) −1。(∗∗)