Mengerの定理

要点：辺 $e=xy$ を 1 本選び、$e$ を縮約したグラフで小さい分離集合を見つけ、それをもとに $x,y$ を含む大きさ $k$ の分離集合 $X$ を作る。$e$ を除いたグラフで $A$ から $X$ へ、$X$ から $B$ へ $k$ 本ずつ道を引き、$X$ でつなぐ。
すべての有限グラフと $A,B$ について、辺の本数 $|E|$ に関する帰納法で示す。$E=\emptyset$ なら、$A$–$B$ 道は $A\cap B$ の頂点 1 つからなる道だけなので、$X$ が分離することは $A\cap B\subset X$ と同値であり、$k=|A\cap B|$ で、それらの $k$ 本の道が互いに素である。
$E\ne\emptyset$ とし、辺 $e=xy$ をとる。$e$ を縮約したグラフ $G/e$ を、$x,y$ を新しい 1 頂点 $v_e$ に置き換え、$x$ か $y$ に隣接していた頂点を $v_e$ と隣接させたものとする。$G/e$ では、$x$ か $y$ が $A$ に属するとき $v_e$ を $A$ の頂点とみなした集合を $A'$ とし、$B'$ も同様に定める。$G/e$ の辺は $G$ より少ない。
段 1（$G/e$ に道が足りる場合）。 $G/e$ に互いに素な $A'$–$B'$ 道が $k$ 本あれば、$G$ にも互いに素な $A$–$B$ 道が $k$ 本ある。実際、$v_e$ を通らない道はそのまま $G$ の $A$–$B$ 道である。$v_e$ を通る道 $P$ については、$P$ の $v_e$ 以外の頂点と $x,y$ を合わせた集合で $G$ を制限したグラフは連結で、$A$ と $B$ の頂点を含むので、その中に $A$–$B$ 道がある（$A$ の頂点から $B$ の頂点への道のうち最短のものをとればよい）。他の道は $v_e$ を通らないので $x,y$ を含まず、互いに素であることは保たれる。
段 2（分離集合 $X$）。 以下、$G/e$ に互いに素な $A'$–$B'$ 道が $k$ 本はないとする。帰納法の仮定から、$G/e$ には $A'$ と $B'$ を分離する $k-1$ 個以下の頂点の集合 $Y$ がある。$G$ の $A$–$B$ 道 $P$ の $x,y$ を $v_e$ に置き換える（続けて現れる $v_e$ は 1 つにまとめる）と $G/e$ の $A'$ の頂点から $B'$ の頂点への歩道になり、その中の $A'$–$B'$ 道の頂点は $Y$ と交わる。$v_e\notin Y$ なら、その頂点は $P$ の頂点で $Y$ に属し、$Y$ は $G$ で $A$ と $B$ を分離して $k$ の最小性に反する。よって $v_e\in Y$ であり、$X:=(Y\setminus\{v_e\})\cup\{x,y\}$ は（同じ議論で）$G$ で $A$ と $B$ を分離する。$|X|=|Y|+1\le k$ と $k$ の最小性から $|X|=k$ である。
段 3（$e$ を除いたグラフ）。 $G-e$ を $G$ から辺 $e$ だけを除いたグラフとする。$Z$ が $G-e$ で $A$ と $X$ を分離すれば、$Z$ は $G$ で $A$ と $B$ を分離する。実際、$G$ の $A$–$B$ 道 $P$ は $X$ と交わり、$P$ の始点から最初に $X$ に入る頂点までの部分は $X$ の頂点を終点にしか含まないので、両端が $X$ に属する辺 $e$ を通らず、$G-e$ の $A$ の頂点から $X$ の頂点への道で、$Z$ と交わる。よって $|Z|\ge k$ であり、$X$ 自身は $A$ と $X$ を分離するので、$G-e$ での最小の大きさはちょうど $k$ である。帰納法の仮定から、$G-e$ に互いに素な $A$–$X$ 道 $P_1,\dots,P_k$ がある。同様に互いに素な $X$–$B$ 道 $Q_1,\dots,Q_k$ がある。$|X|=k$ なので、各 $v\in X$ はちょうど 1 本の $P_i$ の終点、ちょうど 1 本の $Q_j$ の始点であり、それらを $P_v$、$Q_v$ と書く。
段 4（つなぐ）。 $P_v$ と $Q_w$ が $X$ の外の頂点 $u$ を共有したとすると、$P_v$ の始点から $u$ まで、$u$ から $Q_w$ の終点までの部分はどちらも $X$ と交わらず、つなぐと $X$ を避ける $A$ の頂点から $B$ の頂点への歩道になって、$X$ が分離することに反する。よって $P_v$ と $Q_w$ は $X$ の頂点しか共有せず、$P_v\cap X=\{v\}$、$Q_w\cap X=\{w\}$ だから、$v\ne w$ なら交わらず、$v=w$ なら $v$ だけを共有する。$P_v$ と $Q_v$ を $v$ でつないだ道は $A$ の頂点から $B$ の頂点への道であり、その中の $A$–$B$ 道をとれば、互いに素な $A$–$B$ 道が $k$ 本得られる。$\square$

$s$ の隣接頂点の集合を $N(s)$ と書く。$H:=G-\{s,t\}$、$A:=N(s)$、$B:=N(t)$ として thm-menger-sets を使う。$G$ の $s$–$t$ 道 $(s,w_1,\dots,w_m,t)$ は、$s,t$ が隣接しないので $m\ge1$ で、$w_1\in A$、$w_m\in B$ だから、$(w_1,\dots,w_m)$ は $H$ の $A$ の頂点から $B$ の頂点への道であり、$A$–$B$ 道を含む。逆に $H$ の $A$–$B$ 道の前に $s$、後ろに $t$ を付けると $G$ の $s$–$t$ 道になる。したがって、$X\subset V\setminus\{s,t\}$ が $s$–$t$ 頂点分離集合であることと、$H$ で $A$ と $B$ を分離することは同値である。また、互いに素な $A$–$B$ 道 $k$ 本に $s,t$ を付ければ内部頂点素な $s$–$t$ 道が $k$ 本得られる。よって最大本数は最小の大きさ以上であり、逆の不等式は定義の後に述べた。$\square$

1：すべての弧の容量を $1$ とし、整数値の最大流 $f$ と、$\operatorname{val}(f)=c(S)$ となるカット $S$ をとる（整数性定理と最大流最小カット定理）。$s$–$t$ 有向道は $S$ から外へ出る弧を必ず通るので、$S$ から出る弧の集合は大きさ $c(S)=\operatorname{val}(f)$ の弧カットである。一方、フローの分解により $f$ は正の整数係数の $s$–$t$ 有向道と有向閉路の和で、道の係数の和は $\operatorname{val}(f)$ である。容量が $1$ なので、ある弧を通る道は係数 $1$ のもの 1 本だけであり、道は $\operatorname{val}(f)$ 本の互いに弧素な有向道になる。よって最大本数 $\ge$ 最小の大きさである。
2：$s,t$ 以外の頂点 $v$ を 2 頂点 $v^-,v^+$ と弧 $v^-\to v^+$ に置き換え、$u\to v$ の弧を $u^+\to v^-$ に付け替えた有向グラフ $D'$ を作る（$s,t$ は分けず、$s^\pm=s$、$t^\pm=t$ とみなす）。$s\to t$ の弧がないので、$D'$ の $s$–$t$ 有向道は $s,w_1^-,w_1^+,\dots,w_m^-,w_m^+,t$（$m\ge1$）の形で、$D$ の有向道 $(s,w_1,\dots,w_m,t)$ と 1 対 1 に対応する。2 本の $D$ の道が内部頂点 $v$ を共有すれば、対応する $D'$ の道はどちらも $v^-\to v^+$ を通る。逆に $D'$ の 2 本の道が弧を共有すれば、その弧の端の $v^\pm$（$v\ne s,t$）の $v$ を両方の $D$ の道が内部頂点にもつ。よって内部頂点素な道の最大本数 $k$ は $D'$ の弧素な道の最大本数に等しく、1 により大きさ $k$ の弧カット $Z$ がある。$s$–$t$ 有向道に現れる弧は少なくとも一方の端が $v^\pm$（$v\ne s,t$）なので、$Z$ のそのような各弧にその $v$ を 1 つ対応させると、得られる $X\subset V\setminus\{s,t\}$ は $|X|\le k$ で、$D$ のすべての $s$–$t$ 有向道の内部頂点と交わる。$\square$

辺 $uw$ ごとに弧 $u\to w$ と $w\to u$ を置いた有向グラフを $D$ とし、thm-menger-directed の 1 で、弧カットの最小の大きさ $l$ と同じ本数の弧素な $s$–$t$ 有向道をとる。
まず辺カットについて：大きさ $l$ の弧カット $Z$ を除いた $D$ で $s$ から有向道で行ける頂点の集合を $S$ とすると $t\notin S$ で、$u\in S$、$w\notin S$ となる辺 $uw$ では弧 $u\to w$ が $Z$ に属する（属さなければ $w$ に行ける）。そのような辺の集合は大きさ $l$ 以下で、$s$–$t$ 道はどれも $S$ から出る辺を通るので、辺カットである。
次に道について：$l$ 本の弧素な $s$–$t$ 有向道の族のうち、使う弧の総数が最小のものをとる。2 本の道 $P,Q$ が逆向きの弧 $u\to w$ と $w\to u$ を使うとすると、$P$ の $s$ から $u$ までと $Q$ の $u$ から $t$ まで、$Q$ の $s$ から $w$ までと $P$ の $w$ から $t$ までをつなぐと 2 本の $s$–$t$ 有向歩道ができる。この 2 本は $P,Q$ の弧のうち $u\to w$、$w\to u$ 以外を重複なく分け合うので、それぞれに含まれる $s$–$t$ 有向道で $P,Q$ を置き換えると、弧の総数の小さい弧素な $l$ 本の族が得られて最小性に反する。よって逆向きの弧を使う 2 本の道はなく、向きを忘れた $l$ 本の $s$–$t$ 道は互いに辺素である。$\square$

1 の「道があれば $k$-連結」：隣接しない 2 頂点があれば、その間の $k$ 本の道の内部頂点は相異なるので $|V|\ge k+2$ である。どの 2 頂点も隣接するなら $G$ は完全グラフ $K_n$ で、2 頂点の間の内部頂点素な道は辺 1 本と他の $n-2$ 頂点を 1 つずつ経由する道で高々 $n-1$ 本なので、$k\le n-1$ である。どちらでも $|V|>k$ である。$|X|< k$ の $X$ を除いても、$X$ の外の 2 頂点を結ぶ $k$ 本の道のうち $X$ と交わるのは $|X|$ 本以下なので、残る道があり $G-X$ は連結である。
1 の逆：$G$ が $k$-連結で、2 頂点 $a,b$ を結ぶ内部頂点素な道が $k$ 本ないとする。$a,b$ が隣接しなければ、cor-menger-vertex により $k-1$ 個以下の $a$–$b$ 頂点分離集合があり、それを除くと非連結になって $k$-連結に反する。よって $a,b$ は隣接する。$G':=G-ab$（辺 $ab$ だけを除く）に内部頂点素な $a$–$b$ 道が $k-1$ 本あれば、辺 $ab$ だけの道を加えて $G$ に $k$ 本できるので、$G'$ では $k-2$ 本以下である。$G'$ で $a,b$ は隣接しないので、cor-menger-vertex により $k-2$ 個以下の頂点分離集合 $X$ がある。$|V|>k$ なので $v\notin X\cup\{a,b\}$ がとれる。$G'-X$ で $a$ と $b$ は別の連結成分にあるので、$v$ はどちらかと別の成分にあり、たとえば $a$ と別なら、$G-(X\cup\{b\})$ で $v$ と $a$ は結ばれない。$|X\cup\{b\}|\le k-1$ なので $k$-連結に反する。
2：thm-menger-edge により、$k$ 本の辺素な道がないことと、$k$ 本未満の辺カットがあることは同値である。$\square$

互いに素な $A$–$B$ 道の本数は $k$ 以下なので、本数が最大の族 $\mathcal P$ をとり、$|\mathcal P|< k$ と仮定する。