連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理

0. この記事の要点

ある 2 つの拠点の間の通信を完全に断つには、途中の中継点をいくつ壊せばよいでしょうか。逆に、中継点を共有しない経路は何本取れるでしょうか。この章では、グラフのつながりの強さを数で測り、「経路の本数の最大」と「壊す個数の最小」がいつも一致することを、水を流すネットワークの話に置き換えて示します。読み終えると、グラフの頑丈さを数で言い表し、最大フロー最小カット定理を使って Menger の定理や Hall の定理を導けるようになります。

• グラフの「つながりの強さ」を、頂点を何個除けば切れるか（頂点連結度 $\kappa$）と、辺を何本除けば切れるか（辺連結度 $\lambda$）で測ります。$\kappa\le\lambda\le\delta$ が成り立ちます（定理 2.2）。
• 2-連結であることは、どの 2 頂点も共通の閉路に乗ること、閉路から始めて道（耳）を次々に付け足して作れることと同値です（定理 3.2）。一般の連結グラフは、ブロックが切断点（取り除くと非連結になる頂点）で木の形につながったものです（命題 3.4）。
• ネットワークの最大フローの流量は、最小カットの容量に等しくなります（最大フロー最小カット定理、定理 4.8）。増加道が無くなったとき、入口から増加道で届く範囲がそのまま最小カットになります。
• 容量が整数なら、整数値の最大フローがあります（定理 4.9）。この整数性が、フローの定理を組合せ論の定理に変える鍵です。
• Menger の定理（定理 5.4）: 2 頂点を結ぶ内素な道の最大本数は、2 頂点を分離する頂点の最小個数に等しい。辺素な道と辺の除去についても同じです。頂点を 2 つに割ってフローに帰着します。
• Menger の定理から、$k$-連結グラフの任意の $k$ 頂点は共通の閉路に乗ること（定理 5.7）、$\kappa\ge\alpha$ なら Hamilton 閉路（全頂点を 1 回ずつ通る閉路）があること（定理 5.8）、そして第 2 章の Hall・König の定理（命題 6.1）が導けます。

この記事で使う事前知識

• 切断点: 取り除くとグラフが非連結になる頂点。→ 切断点
• 連結成分: 辺をたどって行き来できる頂点どうしをまとめた、極大な部分。→ 連結成分
• Hamilton 閉路: グラフの全頂点をちょうど 1 回ずつ通る閉路。→ Hamilton 閉路
• マッチング: どの 2 辺も端点を共有しない辺の集まり。→ マッチング
• 独立集合: どの 2 頂点も隣接しない頂点の集合（その最大の大きさが独立数 $\alpha$）。→ 独立集合
• 頂点被覆: どの辺も、少なくとも一方の端点がその集合に入るような頂点の集合。→ 頂点被覆

1. 動機

通信網で、ある 2 つの拠点の間の通信を完全に断つには、中継点を最低いくつ壊せばよいでしょうか。逆に、互いに中継点を共有しない経路は最大で何本取れるでしょうか。経路が $k$ 本あれば、それぞれから中継点を 1 つずつ壊さなければならないので、壊す個数は $k$ 以上です。Menger の定理は、この当たり前の不等式がいつでも等号になると主張します。経路を増やせない理由は、少数の中継点というボトルネックの存在に限られるわけです。

同じ形の定理が、物を流す問題にもあります。各辺に流せる量の上限（容量）が決まったネットワークで、入口から出口へ流せる総量の最大値は、入口と出口を分ける切り口を通る容量の合計の最小値に一致します。第 2 章 の Hall の定理・König の定理も「最大 $=$ 最小」の形でした。この章では、最大フロー最小カット定理を最初に証明し、Menger・Hall・König をその系として並べます。証明の中心にあるのは、第 2 章と同じ増加道です。

グラフの語彙は 第 1 章 に従います。アルゴリズムの実装は グラフアルゴリズム を見てください。計算量についての話は 命題 4.11 の 1 つに限ります。

2. 連結度

定義 2.1（頂点連結度・辺連結度）↗

$G$ を $n$ 頂点のグラフとする。

• $S\subseteq V(G)$ は、$G-S$ が非連結になるとき分離集合という。$k\ge0$ に対し、$n>k$ で、かつ $k$ 個未満の頂点からなるどの $S$ についても $G-S$ が連結であるとき、$G$ は $k$-連結であるという。$G$ が $k$-連結であるような最大の $k$ を頂点連結度 $\kappa(G)$ という。
• $F\subseteq E(G)$ は、$G-F$ が非連結になるとき辺カットという。$n\ge2$ で、$k$ 本未満の辺からなるどの $F$ についても $G-F$ が連結であるとき、$G$ は $k$-辺連結であるという。その最大の $k$ を辺連結度 $\lambda(G)$ という（$n=1$ のときは $\lambda=0$ とする）。
• 頂点 $s,t$ と $S\subseteq V(G)\setminus\{s,t\}$ について、$s$ と $t$ が $G-S$ の異なる連結成分に属するとき、$S$ は $s$ と $t$ を分離するという。辺集合についても同様に定める。

定義から、完全グラフでは分離集合がなく、$n>k$ の制約から $\kappa(K_n)=n-1$ です。完全でないグラフでは、$\kappa(G)$ は分離集合の大きさの最小値です（隣接しない 2 頂点 $u,v$ に対し $V(G)\setminus\{u,v\}$ が分離集合なので、分離集合があり、その最小の大きさは $n-2$ 以下です）。どのグラフでも $\kappa(G)\le n-1$ です。連結であることは 1-連結であること（$n\ge2$ のとき）、切断点をもたない連結グラフ（$n\ge3$）が 2-連結グラフです。

定理 2.2（Whitney の不等式）✓

$n\ge2$ 頂点のグラフ $G$ について

$$\kappa(G)\le\lambda(G)\le\delta(G)$$

が成り立つ。

証明の方針です。$\lambda\le\delta$ は、次数が最小の頂点を孤立させるだけで分かります。$\kappa\le\lambda$ は、最小の辺カットを取り、その辺の端点を 1 つずつ選んで頂点の集合を作ると、辺の本数以下の大きさの分離集合になる、という対応で示します（辺が両側の全頂点を結んでいる極端な場合だけは別に数えます）。

証明（定理 2.2）

$\lambda\le\delta$. 次数が $\delta$ の頂点 $v$ に接続する $\delta$ 本の辺をすべて除くと、$v$ は孤立し、$n\ge2$ なのでグラフは非連結になります。

$\kappa\le\lambda$. $G$ が非連結なら $\kappa=\lambda=0$ です。$G$ を連結とし、辺の数が最小の辺カット $F$（$|F|=\lambda$）を取ります。$G-F$ の連結成分の 1 つの頂点集合を $X$、$\overline X=V(G)\setminus X$ とします（どちらも空でない）。$X$ と $\overline X$ を結ぶ $G$ の辺はすべて $F$ に入っていなければならず、それらを除くだけで非連結になるので、$F$ の最小性から、$F$ はちょうど $X$ と $\overline X$ を結ぶ辺の全体です。

場合 1: $X$ のどの頂点も $\overline X$ のどの頂点とも隣接する. このとき $\lambda=|F|=|X|\,|\overline X|$ です。$|X|=a$ とすると $a(n-a)-(n-1)=(a-1)(n-a-1)\ge0$ なので、$\lambda\ge n-1\ge\kappa$ です。

場合 2: 隣接しない $x\in X$、$y\in\overline X$ がある.

$$S=\bigl(N(x)\cap\overline X\bigr)\ \cup\ \{u\in X\setminus\{x\}: u\text{ は }\overline X\text{ に隣接点をもつ}\}$$

と置きます。$x\notin S$ で、$y$ は $x$ と隣接しない $\overline X$ の頂点なので $y\notin S$ です。$x$ から $y$ への道は、どこかで $X$ から $\overline X$ へ辺 $uv$（$u\in X$、$v\in\overline X$）で渡ります。$u=x$ なら $v\in N(x)\cap\overline X\subseteq S$、$u\ne x$ なら $u\in S$ です。よってどの道も $S$ の頂点を通り、$S$ は分離集合で、$\kappa\le|S|$ です。

$|S|\le|F|$ を示します。$v\in N(x)\cap\overline X$ には辺 $xv\in F$ を、$u\in S\cap X$ には $u$ と $\overline X$ を結ぶ辺を 1 本選んで対応させます。前者の辺は $x$ を端点にもち $\overline X$ 側の端点が相異なり、後者の辺は $X$ 側の端点 $u\ne x$ が相異なるので、この対応は $S$ から $F$ への単射です。よって $\kappa\le|S|\le|F|=\lambda$ です。

∎

例 2.3（3 つの量がすべて異なる例）

2 つの $K_5$（頂点集合 $X$、$Y$）を用意し、$x\in X$ と相異なる $y_1,y_2\in Y$ を選んで辺 $xy_1$、$xy_2$ を足します。$x$ を除くと $X\setminus\{x\}$ と $Y$ が分かれるので $\kappa=1$ です。辺 $xy_1,xy_2$ を除くと非連結になるので $\lambda\le2$ で、どの辺も閉路に乗る（$K_5$ の中の辺は三角形に、$xy_1$ と $xy_2$ は閉路 $xy_1y_2x$ に乗る）ので橋はなく（命題 4.2［道・閉路・木］）、$\lambda=2$ です。最小次数は $\delta=4$ です。したがって $\kappa=1<\lambda=2<\delta=4$ となり、定理 2.2 の 2 つの不等号はどちらも真の不等号になりえます。

次の例は、内周（最短の閉路の長さ）が 5 で 3-正則という性質から $\kappa\ge3$ を導きます。2 個以下の頂点で分離できたと仮定し、切り離された側の頂点と分離集合をつなぐ辺の本数を 2 通りに数えて矛盾を出す、という流れです。

例 2.4（Petersen グラフでは 3 つとも 3）

Petersen グラフ（第 1 章の 例 6.12［道・閉路・木］）は 3-正則で、内周は 5 です（三角形も長さ 4 の閉路も含みません）。$\kappa\le\lambda\le\delta=3$ なので、$\kappa\ge3$ を示せば $\kappa=\lambda=3$ です。

$|S|\le2$ の分離集合 $S$ があるとし、$G-S$ の頂点数最小の成分の頂点集合を $X$ とします。成分は 2 つ以上あるので $|X|\le(10-|S|)/2$、$X$ は $S$ 以外の頂点とは $X$ の中でしか隣接しません。$|X|\le5$ ですが、$|X|=5$ となるのは $S=\varnothing$ で $G$ が非連結のときだけで、Petersen グラフは連結なので $|X|\le4$ です。$G[X]$ は連結で、内周 5 から閉路を含まないので木で、辺は $|X|-1$ 本です。$X$ と $S$ を結ぶ辺の本数は、次数の和から

$$3|X|-2(|X|-1)=|X|+2$$

です。一方、$S$ の 1 頂点 $s$ が $X$ の 2 頂点 $x,x'$ と隣接すると、$x$ と $x'$ を結ぶ木の中の道と合わせて閉路ができ、その長さが 5 以上であるためには、木の中での距離が 3 以上でなければなりません。4 頂点以下の木でそのような対があるのは、道 $P_4$ の両端の 1 組だけです。したがって、$s$ が $X$ にもつ隣接点は、$|X|\le3$ なら 1 個以下、$|X|=4$ なら 2 個以下です。$X$ と $S$ を結ぶ辺は、$|X|\le3$ なら $|S|\le2$ 本以下で $|X|+2\ge3$ に反し、$|X|=4$ なら $2|S|\le4$ 本以下で $|X|+2=6$ に反します。よって $\kappa\ge3$ です。

3. 2-連結グラフとブロック

3.1. 耳分解

定義 3.1（耳・耳分解）↗

$H$ を $G$ の部分グラフとする。$G$ の中の長さ 1 以上の道 $P$ で、両端点が $H$ の相異なる頂点であり、内部の頂点と辺が $H$ に属さないものを $H$ の耳（$H$-道）という。$G$ の部分グラフの列 $G_0\subseteq G_1\subseteq\cdots\subseteq G_r=G$ で、$G_0$ が閉路、各 $G_i$ が $G_{i-1}$ にその耳を 1 本足したものであるとき、これを $G$ の耳分解という。

定理 3.2（2-連結グラフの特徴づけ）✓

$n\ge3$ 頂点のグラフ $G$ について、次は同値である。

1. $G$ は 2-連結である。
2. $G$ のどの 2 頂点も、共通の閉路の上にある。
3. $G$ は耳分解をもつ。

証明（定理 3.2）

$(1)\Rightarrow(2)$. 相異なる 2 頂点 $u,v$ を取り、距離 $d(u,v)$ についての帰納法（定理 3.2［証明の技術］）で、$u$ と $v$ を通る閉路があることを示します。

$d(u,v)=1$ のとき. 辺 $uv$ が橋でないことを示せば、命題 4.2［道・閉路・木］ から $uv$ を通る閉路があります。橋だとすると、$G-uv$ は $u$ を含む成分 $X$ と $v$ を含む成分 $Y$ に分かれます。$n\ge3$ なので、たとえば $X$ に $u$ 以外の頂点 $w$ があります。$G-u$ の中で $w$ から $v$ への道は辺 $uv$ を使えないので $G-uv$ の中の道ですが、$w$ と $v$ は $G-uv$ の異なる成分に属します。よって $G-u$ は非連結で、2-連結性に反します。

$d(u,v)=k\ge2$ のとき. $u$ から $v$ への最短の道で $v$ の直前の頂点を $w$ とすると、$d(u,w)=k-1$ です。帰納法の仮定から $u$ と $w$ を通る閉路があり、これは $u$ から $w$ への、内部の頂点を共有しない 2 本の道 $P,Q$ に分かれます。$G-w$ は連結なので、$w$ を通らない $u$ から $v$ への道 $R$ があります。$R$ の頂点のうち $P\cup Q$ の上にあるもので、$R$ に沿って最も $v$ に近いものを $z$ とします（$u$ がそうなので存在し、$z\ne w$ です）。$z$ が $P$ の上にあるとしてかまいません。このとき

$$u\ \xrightarrow{\ P\ }\ z\ \xrightarrow{\ R\ }\ v\ \longrightarrow\ w\ \xrightarrow{\ Q\text{ を逆向きに}\ }\ u$$

は閉路です。実際、$uPz$ と $Q$ は $u$ しか共有せず（$z\ne w$）、$zRv$ の $z$ より後の頂点は $P\cup Q$ の上になく、辺 $vw$ は $G$ の辺です（$z=v$ の場合は $zRv$ が 1 点になるだけです）。この閉路は $u$ と $v$ を通ります。

$(2)\Rightarrow(1)$. $n\ge3$ です。頂点 $v$ を除いたとき、残りの 2 頂点 $x,y$ は共通の閉路の上にあり、閉路は $x$ と $y$ を結ぶ内部の頂点を共有しない 2 本の道に分かれます。$v$ はその高々一方にしか乗らないので、$G-v$ に $x$ から $y$ への道が残ります。同じ理由で $G$ 自身も連結です。よって $G$ は 2-連結です。

$(1)\Rightarrow(3)$. $G$ は 2-連結なので $\delta(G)\ge2$ です（定理 2.2）。命題 3.1［道・閉路・木］ から $G$ は閉路を含みます。閉路から始めて耳を足していくことで得られる $G$ の部分グラフのうち、頂点数と辺数の和が最大のもの $H$ を取ります。$H=G$ を示します。

まず、両端が $H$ の頂点である $G$ の辺 $xy$ は、すべて $H$ の辺です。そうでなければ $xy$ は長さ 1 の耳で、$H$ に足せて最大性に反します。次に、$V(H)\ne V(G)$ とします。$G$ は連結なので、$v\in V(H)$、$w\notin V(H)$ である辺 $vw$ があります。$G-v$ は連結なので、$w$ から $H-v$ の頂点（$H$ は閉路を含むので存在します）への道が $G-v$ にあります。その道を $w$ からたどって最初に出会う $H$ の頂点を $u$（$u\ne v$）とし、そこまでの部分を $P'$ とすると、辺 $vw$ に $P'$ をつないだ道は、両端 $v\ne u$ が $H$ にあり内部が $H$ の外にある耳です。これも最大性に反します。よって $V(H)=V(G)$ で、最初に示したことから $E(H)=E(G)$ です。

$(3)\Rightarrow(1)$. 閉路グラフは、1 頂点を除くと道になるので 2-連結です。$H$ が 2-連結で、$H'$ が $H$ に耳 $P$（両端 $a\ne b$）を足したグラフなら、$H'$ も 2-連結であることを示します。$H'$ から頂点 $v$ を除きます。$v\in V(H)$ なら、$H-v$ は連結で、$P$ の内部の頂点は $P$ に沿って $a,b$ のうち $v$ でないほうへ届きます。$v$ が $P$ の内部の頂点なら、$H$ は連結で、$P$ の残りの頂点は $a$ か $b$ へ届きます。どちらの場合も $H'-v$ は連結です。耳の本数についての帰納法で、耳分解をもつグラフは 2-連結です。

∎

3.2. ブロック木

2-連結でない連結グラフは、切断点で「2-連結な部分」に分かれます。

定義 3.3（ブロック・ブロック木）↗

グラフ $G$ の連結な部分グラフで、それ自身が切断点をもたないもののうち、包含関係について極大なものを $G$ のブロックという。連結グラフ $G$ に対し、ブロックの全体 $\mathcal B$ と $G$ の切断点の全体 $\mathcal C$ を頂点集合とし、$v\in V(B)$ のとき $v\in\mathcal C$ と $B\in\mathcal B$ を結んだ二部グラフを $G$ のブロック木（ブロックグラフ）という。

ブロックは、2-連結な部分グラフで極大なもの、橋（とその両端点）、孤立点のどれかです。

命題 3.4（ブロック木は木である）✓

$G$ を連結グラフとする。

1. 相異なる 2 つのブロックは、高々 1 頂点しか共有しない。各辺はちょうど 1 つのブロックに属し、各閉路は 1 つのブロックに含まれる。
2. 頂点 $v$ が 2 つ以上のブロックに属することと、$v$ が $G$ の切断点であることは同値である。
3. $G$ のブロック木は木である。

証明の進め方です。まず、ブロックどうしの重なりは切断点に限られること（1 と 2）を示し、そのうえで、ブロックと切断点を並べたものが連結で閉路を含まない、つまり木になること（3）を示します。

証明（命題 3.4）

切断点をもたない連結な部分グラフ（1 頂点、1 辺とその両端、閉路など）は、それを含むそのような部分グラフで極大なもの、すなわちブロックに含まれます。この事実を繰り返し使います。

1. ブロック $B_1\ne B_2$ が 2 頂点以上を共有するとします。$H=B_1\cup B_2$ から頂点 $v$ を除くと、$B_1-v$ と $B_2-v$ はどちらも連結で（$B_i$ は切断点をもたない）、共有する頂点が少なくとも 1 つ残るので、$H-v$ は連結です。$H$ 自身も連結です。よって $H$ は切断点をもたない連結な部分グラフで、$B_1$ を真に含みます（極大なものどうしなので $B_2\not\subseteq B_1$）。これは $B_1$ の極大性に反します。

各辺は（その両端とともに）あるブロックに含まれ、2 つのブロックに含まれると両端の 2 頂点が共有されるので、ちょうど 1 つのブロックに属します。閉路は切断点をもたない連結な部分グラフなので、あるブロックに含まれます。

2. 2 つのブロックに属する頂点は切断点. $v\in V(B_1)\cap V(B_2)$、$B_1\ne B_2$ とします。$B_i$ が $v$ だけからなるなら、もう一方に含まれて極大でないので、$B_i$ は $v$ の隣接点 $x_i$ を含みます。1 から $x_1\ne x_2$ です。$v$ が切断点でなければ、$G-v$ に $x_1$ から $x_2$ への道があり、辺 $x_2v$、$vx_1$ と合わせて閉路 $C$ になります。$C$ はあるブロック $B$ に含まれます。$B$ と $B_1$ は 2 頂点 $v,x_1$ を共有するので $B=B_1$、同様に $B=B_2$ となり、$B_1\ne B_2$ に反します。

切断点は 2 つのブロックに属する. $v$ が切断点なら、$G-v$ は 2 つ以上の成分をもちます。$G$ は連結なので、どの成分にも $v$ の隣接点があります。異なる成分から隣接点 $x,y$ を取ります。辺 $vx$ と $vy$ が同じブロック $B$ に属するとすると、$B-v$ は連結で $x,y$ を含むので、$x$ と $y$ が $G-v$ の同じ成分に属することになり矛盾です。よって $v$ は 2 つの異なるブロックに属します。

3. 連結であること. 切断点は 2 からあるブロックと結ばれているので、2 つのブロック $B,B'$ がブロック木の中でつながることを示せば十分です。$x\in V(B)$、$y\in V(B')$ を取り、$G$ の中の道 $x=p_0p_1\cdots p_k=y$ を取ります（$k=0$ のときは、$B=B'$ であるか、$x$ が 2 つのブロックに属する切断点で $B,x,B'$ がブロック木の歩道です）。辺 $p_{i-1}p_i$ の属するブロックを $B_i$ とします。$B_i\ne B_{i+1}$ なら、両方に属する $p_i$ は 2 から切断点で、ブロック木で $B_i$ と $B_{i+1}$ の両方と隣接します。$B$ と $B_1$（ともに $x$ を含む）、$B_k$ と $B'$（ともに $y$ を含む）についても同じです。よって $B$ から $B'$ への歩道があります。

閉路を含まないこと. ブロック木が閉路 $B_1v_1B_2v_2\cdots B_kv_kB_1$（$k\ge2$、ブロックも切断点も相異なる、$v_i\in V(B_i)\cap V(B_{i+1})$、添字は $k$ を法とする）を含むとします。$H=B_1\cup\cdots\cup B_k$ から頂点 $v$ を除きます。各 $B_i-v$ は連結です。$B_i-v$ と $B_{i+1}-v$ は、$v\ne v_i$ である限り $v_i$ を共有します。$v$ は相異なる $v_1,\dots,v_k$ の高々 1 つとしか一致しないので、円環状に並んだ $k$ 個のつなぎ目のうち切れるのは高々 1 か所で、$H-v$ は連結です。$H$ も連結です。したがって $H$ は切断点をもたない連結な部分グラフで、$B_1$ を真に含み、$B_1$ の極大性に反します。

∎

4. ネットワークフロー

4.1. フローとカット

定義 4.1（有向グラフ・ネットワーク・フロー）↗

有向グラフ $D=(V,E)$ は、有限集合 $V$ と、相異なる頂点の順序対 $(u,v)$（$u$ から $v$ への有向辺）の集合 $E$ からなる。$(u,v)$ と $(v,u)$ が両方あってもよい。ネットワークとは、有向グラフ $D$、容量 $c:E\to\mathbb{R}_{\ge0}$、相異なる 2 頂点 $s$（入口）、$t$（出口）の組である。

関数 $f:E\to\mathbb{R}$ と頂点集合 $S\subseteq V$ に対し

$$f^+(S)=\sum_{(u,v)\in E,\ u\in S,\ v\notin S}f(u,v),\qquad f^-(S)=\sum_{(u,v)\in E,\ u\notin S,\ v\in S}f(u,v)$$

と書く（$S$ から出る量、$S$ に入る量）。$f^\pm(v)=f^\pm(\{v\})$ とする。$f$ がフローであるとは、

• 容量制約: すべての $e\in E$ で $0\le f(e)\le c(e)$、
• 保存則: $s,t$ 以外のすべての頂点 $v$ で $f^+(v)=f^-(v)$

を満たすことをいう。$|f|=f^+(s)-f^-(s)$ をフローの流量という。流量が最大のフローを最大フローという。

定義 4.2（カット）↗

$s\in S$、$t\notin S$ である頂点集合 $S\subseteq V$ を $s$–$t$ カットといい、

$$c(S)=\sum_{(u,v)\in E,\ u\in S,\ v\notin S}c(u,v)$$

をその容量という。容量が最小のカットを最小カットという。

補題 4.3（流量はどのカットでも測れる）✓

フロー $f$ と $s$–$t$ カット $S$ について

$$|f|=f^+(S)-f^-(S)\le c(S)$$

が成り立つ。等号 $|f|=c(S)$ が成り立つのは、$S$ から出る辺がすべて $f(e)=c(e)$、$S$ に入る辺がすべて $f(e)=0$ のとき、そのときに限る。

証明（補題 4.3）

$S$ の頂点 $v$ について $f^+(v)-f^-(v)$ を足し合わせます。保存則から $v\ne s$ の項は 0 で（$t\notin S$）、和は $|f|$ です。一方、同じ和を辺ごとに整理します。両端が $S$ に入る辺 $(u,v)$ は、$f^+(u)$ に $+f(u,v)$、$f^-(v)$ に $-f(u,v)$ として現れて打ち消し合います。$S$ から出る辺は $+f(e)$ だけ、$S$ に入る辺は $-f(e)$ だけが現れます。よって

$$|f|=\sum_{v\in S}\bigl(f^+(v)-f^-(v)\bigr)=f^+(S)-f^-(S)$$

です。容量制約から $f^+(S)\le c(S)$、$f^-(S)\ge0$ なので $|f|\le c(S)$ で、等号は $f^+(S)=c(S)$ かつ $f^-(S)=0$ のとき、すなわち主張の条件のときです。

∎

この補題から、どのフローの流量も、どのカットの容量以下です。「流量 $=$ 容量」となるフローとカットの組が見つかれば、そのフローは最大、カットは最小です（第 2 章の 補題 2.3［マッチング］ と同じ構図です）。

4.2. 増加道

定義 4.4（残余ネットワーク・増加道）↗

フロー $f$ に対し、各辺 $e=(x,y)\in E$ から 2 種類の残余辺を作る。

• $f(e)<c(e)$ のとき、$x$ から $y$ への順方向の残余辺 $e^+$。残余容量は $c(e)-f(e)$。
• $f(e)>0$ のとき、$y$ から $x$ への逆方向の残余辺 $e^-$。残余容量は $f(e)$。

残余辺の全体を $f$ の残余ネットワーク $R_f$ という。相異なる頂点の列 $s=v_0,v_1,\dots,v_k=t$ と、$v_{i-1}$ から $v_i$ への残余辺 $a_i$ の列を $f$-増加道といい、$a_i$ の残余容量の最小値 $\varepsilon>0$ をその残余容量という。増加道に沿って $f$ を増加するとは、$a_i=e^+$ である辺 $e$ で $f(e)$ を $\varepsilon$ 増やし、$a_i=e^-$ である辺 $e$ で $f(e)$ を $\varepsilon$ 減らすことをいう。

逆方向の残余辺を使うことは、すでに流している量を押し戻して別の経路に回すことにあたります。第 2 章の増加道で、マッチングの辺を外して付け替えたのと同じです。

補題 4.5（増加すると流量が増える）✓

フロー $f$ を残余容量 $\varepsilon$ の増加道に沿って増加したものを $f'$ とすると、$f'$ はフローで、$|f'|=|f|+\varepsilon$ である。

証明（補題 4.5）

容量制約. 順方向に使う辺では $f'(e)=f(e)+\varepsilon\le f(e)+(c(e)-f(e))=c(e)$、逆方向に使う辺では $f'(e)=f(e)-\varepsilon\ge0$ です。増加道の頂点は相異なるので、同じ辺 $e$ が 2 回（$e^+$ と $e^-$ の両方として）使われることはありません。

保存則と流量. 頂点 $v$ の正味の流出量を $\partial f(v)=f^+(v)-f^-(v)$ と書きます。増加道の第 $i$ 歩が $\partial f$ に与える変化を調べます。$a_i=e^+$、$e=(v_{i-1},v_i)$ なら、$f^+(v_{i-1})$ と $f^-(v_i)$ が $\varepsilon$ 増えます。$a_i=e^-$、$e=(v_i,v_{i-1})$ なら、$f^-(v_{i-1})$ と $f^+(v_i)$ が $\varepsilon$ 減ります。どちらの場合も、$\partial f(v_{i-1})$ は $\varepsilon$ 増え、$\partial f(v_i)$ は $\varepsilon$ 減ります。途中の頂点 $v_i$（$0<i<k$）は第 $i$ 歩の終点と第 $i+1$ 歩の始点にちょうど 1 回ずつなるので、$\partial f'(v_i)=\partial f(v_i)=0$ です。道の上にない頂点では何も変わりません。$s=v_0$ は第 1 歩の始点にだけなるので、$|f'|=\partial f'(s)=|f|+\varepsilon$ です。

∎

補題 4.6（増加道が無ければ流量と等しい容量のカットがある）✓

フロー $f$ が増加道をもたないとする。$s$ から残余辺をたどって届く頂点の集合を $S$ とすると、$S$ は $s$–$t$ カットで、$|f|=c(S)$ である。したがって $f$ は最大フロー、$S$ は最小カットである。

証明（補題 4.6）

$s\in S$ です。$t\in S$ なら、$s$ から $t$ へ残余辺をたどる歩道があり、頂点の重複を取り除けば増加道になるので、仮定に反します。よって $S$ は $s$–$t$ カットです。

$S$ から出る辺 $e=(x,y)$（$x\in S$、$y\notin S$）で $f(e)<c(e)$ とすると、順方向の残余辺 $e^+$ で $y$ に届き、$y\in S$ となって矛盾します。よって $f(e)=c(e)$ です。$S$ に入る辺 $e=(x,y)$（$x\notin S$、$y\in S$）で $f(e)>0$ とすると、逆方向の残余辺 $e^-$ で $y$ から $x$ に届き、$x\in S$ となって矛盾します。よって $f(e)=0$ です。補題 4.3 の等号条件から $|f|=c(S)$ です。同じ補題から、どのフロー $g$ についても $|g|\le c(S)=|f|$、どのカット $S'$ についても $c(S')\ge|f|=c(S)$ です。

∎

4.3. 最大フロー最小カット定理

次の補題は、流量が最大のフローが本当に存在するかを確かめるためのものです。フローの候補は無限にあるので、候補全体が有界で閉じた集合であることを使って、最大値が実際に取られることを言います。位相の言葉を使いますが、この補題を使わない別の証明が 注意 4.12 にあります。

補題 4.7（最大フローの存在）✓

容量が非負の実数であるどのネットワークにも、最大フローが存在する。

証明（補題 4.7）

$m=|E|$ とし、関数 $f:E\to\mathbb{R}$ を $\mathbb{R}^m$ の点と見ます。フローの全体 $\mathcal F$ は、直方体 $\prod_{e}[0,c(e)]$ の点のうち、有限個の一次式の等式 $f^+(v)-f^-(v)=0$（$v\ne s,t$）を満たすものの集合です。直方体は有界な閉集合で、一次式は連続なので、各等式の解の集合（閉集合 $\{0\}$ の連続写像による逆像）も閉集合です。よって $\mathcal F$ は有界な閉集合で、Heine–Borel の定理（定理 5.2［コンパクト性］）からコンパクトです。恒等的に 0 の関数はフローなので $\mathcal F\ne\varnothing$ です。流量 $f\mapsto|f|$ は一次式なので連続で、最大値・最小値の定理（系 6.2［コンパクト性］）から $\mathcal F$ の上で最大値を取ります。

∎

定理 4.8（最大フロー最小カット定理）✓

どのネットワークでも、フローの流量の最大値は、$s$–$t$ カットの容量の最小値に等しい。

$$\max_f|f|=\min_Sc(S).$$

証明（定理 4.8）

補題 4.7 から最大フロー $f$ があります。$f$ が増加道をもてば、補題 4.5 から流量のより大きいフローができて最大性に反するので、$f$ は増加道をもちません。補題 4.6 から、$|f|=c(S)$ となる $s$–$t$ カット $S$ があり、$S$ は最小カットです。

∎

定理 4.9（整数性定理）✓

容量がすべて非負整数のネットワークには、すべての辺で値が整数である最大フローが存在する。それは、恒等的に 0 のフローから始めて、増加道がある限り増加を繰り返すことで得られる（Ford–Fulkerson の方法）。

証明（定理 4.9）

恒等的に 0 のフローは整数値です。$f$ が整数値のフローなら、残余容量 $c(e)-f(e)$ と $f(e)$ はすべて整数なので、増加道の残余容量 $\varepsilon$ は正の整数で、増加したフローも整数値、流量は 1 以上増えます（補題 4.5）。流量は $c(\{s\})$ 以下（補題 4.3）なので、増加は高々 $c(\{s\})$ 回で止まります。止まったときのフローは整数値で増加道をもたないので、補題 4.6 から最大フローです。

∎

例 4.10（6 頂点のネットワークで増加道を 3 回追う）

頂点 $s,a,b,c,d,t$、辺と容量が

$$(s,a):2,\ (s,b):2,\ (a,c):2,\ (a,d):1,\ (b,d):2,\ (c,t):2,\ (d,t):1$$

のネットワークを考えます。

例のネットワーク。数字は容量。破線は最小カット S = {s, b, d} の境界

0 のフローから始め、わざと遠回りの増加道を先に選びます。

1. 増加道 $s\to a\to d\to t$（すべて順方向、残余容量 $\min(2,1,1)=1$）。$f(s,a)=f(a,d)=f(d,t)=1$、流量 1。
2. 増加道 $s\to a\to c\to t$（残余容量 $\min(1,2,2)=1$）。$f(s,a)=2$、$f(a,c)=f(c,t)=1$、流量 2。
3. $(s,a)$ と $(d,t)$ は飽和しました。$s\to b\to d$ と進んだあと、辺 $(a,d)$ を逆方向に使って $a$ に戻り、$a\to c\to t$ と進みます。残余容量は $\min(2,2,1,1,1)=1$ です。$f(s,b)=f(b,d)=1$、$f(a,d)=0$、$f(a,c)=f(c,t)=2$、流量 3。

3 回目の増加は、$a$ から $d$ に流していた 1 を $a\to c$ に回し、空いた $(d,t)$ を $b$ からの流れが使う、という付け替えです。この時点で $s$ から残余辺で届くのは $b$（$f(s,b)=1<2$）と $d$（$f(b,d)=1<2$）だけです。$d$ からは、$(d,t)$ が飽和し、$(a,d)$ の流れが 0 なので先へ進めません。$S=\{s,b,d\}$ から出る辺は $(s,a)$ と $(d,t)$ で、$c(S)=2+1=3=|f|$ です。補題 4.6 のとおり、最大フローと最小カットが同時に得られました。

4.4. 増加道の選び方と停止性

容量が整数（したがって有理数）なら Ford–Fulkerson の方法は必ず止まりますが、増加の回数は容量の大きさに比例しうるうえ、容量が実数のときは止まる保証がありません。増加道を辺の数が最小になるように選べば、容量の値によらない回数で止まります。

命題 4.11（最短の増加道を選べば nm 回以内で止まる）✓

頂点が $n$ 個、辺が $m$ 本のネットワーク（容量は非負の実数）で、あるフローから始めて、毎回、残余辺の本数が最小の増加道に沿って増加する。このとき、増加の回数は $nm$ 回以下である。

証明の方針です。残余ネットワークでの $s$ からの最短距離を追います。(1) 増加しても距離は減らない、(2) ある残余辺が再びボトルネック（その増加でちょうど使い切られる辺）になるまでに、その辺の始点の距離は 2 以上増える、という 2 点から、1 本の残余辺がボトルネックになる回数を数え上げます。

証明（命題 4.11）

フロー $g$ に対し、残余ネットワーク $R_g$ の中で $s$ から $v$ へ残余辺をたどる歩道の残余辺の本数の最小値を $d_g(v)$ と書きます（届かなければ $\infty$）。残余辺 $a$ が $x$ から $y$ へ向かうとき、$a$ の逆とは、同じ辺 $e$ から作られる $y$ から $x$ への残余辺（$e^+$ に対する $e^-$、$e^-$ に対する $e^+$）のことです。

手順 1（距離は減らない）. $f$ を最短の増加道 $P$ に沿って増加して $f'$ になったとします。すべての頂点 $x$ について $d_{f'}(x)\ge d_f(x)$ を示します。$P$ の上の残余辺が $u$ から $v$ へ向かうなら、$P$ が最短なので $d_f(v)=d_f(u)+1$ です。$R_{f'}$ にあって $R_f$ にない残余辺は、増加で値が変わった辺から新しく生じたもので、$P$ の上の残余辺の逆に限られます。それは $v$ から $u$ へ向かい、$d_f(u)=d_f(v)-1$ を満たします。

$R_{f'}$ の中の $s$ から $x$ への最短の歩道 $s=x_0,x_1,\dots,x_k=x$（$k=d_{f'}(x)$）を取ります。各残余辺（$x_{i-1}$ から $x_i$ へ）は、$R_f$ にもあるか、$P$ の上の残余辺の逆です。前者なら $d_f(x_i)\le d_f(x_{i-1})+1$、後者なら $d_f(x_i)=d_f(x_{i-1})-1\le d_f(x_{i-1})+1$ です。$i$ について足し上げて $d_f(x)\le d_f(s)+k=d_{f'}(x)$ です。

手順 2（同じ残余辺がボトルネックになる回数）. 増加道の上で残余容量が最小値 $\varepsilon$ に等しい残余辺をボトルネックと呼びます。増加ごとに少なくとも 1 本のボトルネックがあります。$u$ から $v$ へ向かう残余辺 $a$ が、フロー $f$ での増加でボトルネックになったとします。増加後、$a=e^+$ なら $f'(e)=c(e)$、$a=e^-$ なら $f'(e)=0$ となり、$a$ は残余ネットワークから消えます。$a$ がふたたび現れるのは、$e$ の値が逆向きに変わったとき、すなわち $a$ の逆（$v$ から $u$ へ）が、あとのフロー $g$ での増加道に使われたときに限ります。そのとき、最短性と手順 1 から

$$d_g(u)=d_g(v)+1\ge d_f(v)+1=d_f(u)+2$$

です。$a$ が次にボトルネックになるフロー $h$ では、手順 1 から $d_h(u)\ge d_g(u)\ge d_f(u)+2$ です。つまり、$a$ がボトルネックになるたびに、そのときの $d(u)$ は 2 以上増えています。

$a$ が増加道の上にあるとき、$u$ は増加道の $t$ 以外の頂点で、増加道の頂点は相異なるので $0\le d(u)\le n-2$ です。この範囲で 2 以上ずつ増える値は高々 $\lfloor(n-2)/2\rfloor+1\le n/2$ 個なので、$a$ がボトルネックになるのは $n/2$ 回以下です。

手順 3（合計）. 残余辺になりうるものは各辺につき $e^+$ と $e^-$ の 2 つ、合計 $2m$ 個です。増加のたびにそのどれかがボトルネックになるので、増加の回数は $2m\cdot n/2=nm$ 以下です。

∎

注意 4.12

命題 4.11 の方法で止まったときのフローは増加道をもたないので、補題 4.6 から最大フローです。これは 補題 4.7 の、コンパクト性を使わない別証明になっています。増加道を勝手に選んだ場合には、容量に無理数があると、増加が無限に続き、流量が最大値より真に小さい値に収束する例が知られています（Ford と Fulkerson による。参考文献の Ford–Fulkerson の本を見てください）。その例が示すのは「どの増加道を選ぶか」に注意が必要だということで、定理そのものは実数の容量で成り立ちます。

注意 4.13

辺を抵抗、フローを電流と見ると、保存則は Kirchhoff の電流則にあたります。電流は保存則に加えて電位の存在（電圧則）を満たす特別なフローで、グラフの Laplacian（定義 2.3［グラフと行列式］）を係数とする連立一次方程式の解として定まります。この章のフローには電圧則にあたる条件はなく、容量の範囲で自由に選べる点が違います。

5. Menger の定理

定義 5.1（内素な道・辺素な道）↗

$s$ から $t$ への何本かの道が、$s,t$ 以外に頂点を共有しないとき内素であるといい、辺を共有しないとき辺素であるという。

整数性定理を使うための準備として、0 と 1 だけを値に取るフローが道に分解できることを示します。

補題 5.2（0-1 フローは道に分解できる）✓

ネットワークのフロー $f$ がすべての辺で 0 か 1 の値を取り、流量が整数 $k\ge0$ であるとする。このとき、$f(e)=1$ の辺だけを使う $s$ から $t$ への有向道（頂点の重複がないもの）が $k$ 本あり、どの 2 本も辺を共有しない。

証明（補題 5.2）

$k$ についての帰納法（定理 3.2［証明の技術］）で示します。$k=0$ なら示すことはありません。$k\ge1$ とします。$f(e)=1$ の辺をたどって $s$ から届く頂点の集合を $R$ とします。$t\notin R$ なら $R$ は $s$–$t$ カットで、$R$ から出る辺はすべて $f(e)=0$ なので、補題 4.3 から $|f|=f^+(R)-f^-(R)\le0$ となり、$k\ge1$ に反します。よって $f(e)=1$ の辺だけを使う $s$ から $t$ への歩道があり、辺の本数が最小のものを取れば頂点の重複のない有向道 $P$ になります。

$P$ の辺で値を 1 減らした関数を $f'$ とします。$f'$ は 0 か 1 の値を取ります。$P$ の途中の頂点では入る辺と出る辺が 1 本ずつ減るので保存則が保たれ、$s$ では出る辺が 1 本減るだけなので $|f'|=k-1$ です。帰納法の仮定から、$f'(e)=1$ の辺だけを使う辺素な道が $k-1$ 本あります。これらは $P$ の辺（$f'(e)=0$）を使わないので、$P$ と合わせて $k$ 本の辺素な道になります。

∎

補題 5.3（有向グラフの辺版）✓

有向グラフ $D$ と相異なる頂点 $s,t$ について、$s$ から $t$ への辺素な有向道の最大本数は、除くと $s$ から $t$ への有向道がなくなる辺集合の大きさの最小値に等しい。

証明（補題 5.3）

辺素な道が $k$ 本あり、辺集合 $F$ を除くと有向道がなくなるなら、$F$ は各道から辺を 1 本以上含み、それらは相異なるので $|F|\ge k$ です。逆向きを示します。すべての辺の容量を 1 としたネットワークを考えます。定理 4.9 から整数値（したがって 0 か 1）の最大フロー $f$ があり、その流量を $k$ とします。補題 5.2 から辺素な有向道が $k$ 本あります。定理 4.8 から容量 $k$ の $s$–$t$ カット $S$ があります。容量がすべて 1 なので、$S$ から出る辺はちょうど $k$ 本です。$s$ から $t$ への有向道は $S$ から出る辺を必ず使うので、この $k$ 本を除くと有向道はなくなります。

∎

定理 5.4（Menger の定理）✓

$G$ をグラフ、$s\ne t$ をその頂点とする。

1. （頂点版） $s$ と $t$ が隣接しないとき、$s$ から $t$ への内素な道の最大本数は、$s$ と $t$ を分離する頂点集合 $X\subseteq V(G)\setminus\{s,t\}$ の大きさの最小値に等しい。
2. （辺版） $s$ から $t$ への辺素な道の最大本数は、$s$ と $t$ を分離する辺集合の大きさの最小値に等しい。

証明の方針です。「道の本数 $\le$ 分離する集合の大きさ」は易しいので、逆向きをフローに帰着します。辺版は、各辺を向きの異なる 2 本の有向辺にして容量を 1 にします。頂点版は、各頂点を入り側と出側に割って、その間を容量 1 の辺で結びます。こうすると、頂点を通れるのは 1 回だけ、という制限が辺の容量で表せます。

証明（定理 5.4）

どちらも「道の本数 $\le$ 分離する集合の大きさ」は、各道が分離する集合の元を少なくとも 1 つ含み、それらが道ごとに異なることから従います（頂点版では、$s,t$ が隣接しないので各道は内部の頂点をもち、分離集合の元は内部の頂点です）。逆向きの不等式を、フローに帰着して示します。

2（辺版）. $G$ の各辺 $uv$ を 2 本の有向辺 $(u,v)$、$(v,u)$ に置き換えた有向グラフ $D$ を作り、すべての容量を 1 とします。定理 4.9 から 0-1 値の最大フロー $f$ があり、流量を $k$ とします。ある $u,v$ で $f(u,v)=f(v,u)=1$ なら、両方を 0 に変えます。$u$ でも $v$ でも入る量と出る量が 1 ずつ減るので、フローのままで流量も変わりません。これを繰り返して、どの辺 $uv$ についても $f(u,v)$ と $f(v,u)$ の少なくとも一方が 0 であるようにします。補題 5.2 から、$f(e)=1$ の有向辺だけを使う辺素な有向道が $k$ 本あります。これらは $G$ の道として、同じ辺を 2 本が使うことはありません（逆向きに使うこともありません）。よって $G$ に辺素な道が $k$ 本あります。

一方、定理 4.8 から容量 $k$ の $s$–$t$ カット $S$ があります。$S$ から出る有向辺は $k$ 本で、これは $G$ で $S$ と $V(G)\setminus S$ を結ぶ辺がちょうど $k$ 本であることを意味します。この $k$ 本を除けば $s$ と $t$ は分離されます。

1（頂点版）. $n=|V(G)|$ とし、次のネットワーク $D'$ を作ります。

• 頂点: $s$、$t$、および $s,t$ 以外の各頂点 $v$ に対する 2 つの頂点 $v^-$（入り側）、$v^+$（出側）。便宜上 $s^+=s$、$t^-=t$ と書く。
• 頂点辺: 各 $v\ne s,t$ に対し $(v^-,v^+)$。容量 1。
• つなぎ辺: $G$ の各辺 $uv$ に対し $(u^+,v^-)$ と $(v^+,u^-)$。ただし $s$ に入るもの、$t$ から出るものは作らない。容量 $n$。

容量の小さいカットがある. $S_0=\{s\}\cup\{v^-:v\ne s,t\}$ は $s$–$t$ カットです。$s$ から出るつなぎ辺は $v^-$ に入り（$s$ と $t$ は隣接しないので $t$ には入りません）、$v^-$ から出る辺は頂点辺だけなので、$S_0$ から出る辺は $n-2$ 本の頂点辺で、$c(S_0)=n-2$ です。

最小カットから分離集合を作る. 定理 4.9 から整数値の最大フロー $f$ があり、流量を $k$ とします。定理 4.8 から容量 $k\le n-2<n$ の最小カット $S$ があります。容量 $n$ のつなぎ辺が $S$ から出ると $c(S)\ge n$ となるので、$S$ から出る辺はすべて頂点辺で、ちょうど $k$ 本です。それらを $(v^-,v^+)$（$v\in X$）とすると $|X|=k$、$X\subseteq V(G)\setminus\{s,t\}$ です。$G-X$ に $s$ から $t$ への道 $sv_1v_2\cdots v_rt$ があるとすると、

$$s,\ v_1^-,\ v_1^+,\ v_2^-,\ v_2^+,\ \dots,\ v_r^-,\ v_r^+,\ t$$

は $D'$ の有向道です。$s\in S$、$t\notin S$ なので、この有向道は $S$ から出る辺を使いますが、使う頂点辺は $(v_i^-,v_i^+)$（$v_i\notin X$）だけで、$S$ から出る辺を使えません。矛盾です。よって $X$ は $s$ と $t$ を分離します。

フローから内素な道を作る. $f$ は頂点辺で 0 か 1 の値を取ります。つなぎ辺 $(u^+,v^-)$ では、$u\ne s$ のとき $u^+$ に入る辺が頂点辺 $(u^-,u^+)$ だけなので、保存則から $f(u^+,v^-)\le f^+(u^+)=f^-(u^+)\le1$ です。$u=s$ のときは、$v^-$ から出る辺が頂点辺だけなので $f(s,v^-)\le f^-(v^-)=f^+(v^-)\le1$ です。よって $f$ は 0-1 値で、補題 5.2 から辺素な有向道が $k$ 本あります。各有向道は上の形をしていて、$G$ の $s$ から $t$ への道 $sv_1\cdots v_rt$ を与えます。2 本の道が $G$ の頂点 $v\ne s,t$ を共有したとします。$v^-$ を通る有向道は次に頂点辺 $(v^-,v^+)$ を使うしかなく、$v^+$ を通る有向道は直前に頂点辺 $(v^-,v^+)$ を使うしかないので、2 本とも同じ頂点辺を使うことになり、辺素であることに反します。よって $k$ 本の道は内素です。

∎

頂点版の証明の要点は、頂点を「入り側」と「出側」に割って、その間の辺の容量で頂点の通過回数を制限することです。容量の制約を頂点に付けたい場面でいつも使える手法です。

頂点の分割。左の頂点 v は、右では入り側 v⁻ と出側 v⁺ に割られ、間を容量 1 の辺で結ぶ（ほかの辺は容量 n）

系 5.5（Menger の定理の大域版）✓

$k\ge1$、$G$ を 2 頂点以上のグラフとする。

1. $G$ が $k$-連結であるためには、どの相異なる 2 頂点も $k$ 本の内素な道で結ばれることが必要十分である。
2. $G$ が $k$-辺連結であるためには、どの相異なる 2 頂点も $k$ 本の辺素な道で結ばれることが必要十分である。

証明（系 5.5）

2. $G$ が $k$-辺連結であることは、$k$ 本未満の辺ではどの 2 頂点も分離できないことと同じです。定理 5.4 の 2 から、これは、どの 2 頂点についても辺素な道の最大本数が $k$ 以上であることと同値です。

1 の十分性. どの 2 頂点も $k$ 本の内素な道で結ばれるとします。相異なる 2 頂点 $u,v$ を結ぶ $k$ 本の内素な道のうち、内部の頂点をもたないもの（辺 $uv$ そのもの）は高々 1 本で、残りの $k-1$ 本は相異なる内部の頂点をもつので、$n\ge2+(k-1)=k+1$ です。$|S|<k$ である $S$ について $G-S$ が非連結だとすると、異なる成分の頂点 $u,v$ を結ぶ $k$ 本の内素な道はどれも $S$ の頂点を内部に含み、それらは相異なるので $|S|\ge k$ となって矛盾します。

1 の必要性. $G$ を $k$-連結、$u\ne v$ とします。

$u,v$ が隣接しないとき. $u$ と $v$ を分離する頂点集合は分離集合なので、大きさは $k$ 以上です。定理 5.4 の 1 から内素な道が $k$ 本あります。

$u,v$ が隣接するとき. $k=1$ なら辺 $uv$ が求める道です。$k\ge2$ とし、$G'=G-uv$ と置きます。$G'$ で $u$ と $v$ を分離する頂点集合 $S$ の大きさが $k-1$ 以上であることを示します。$|S|\le k-2$ とすると、$G-S$ は連結で、$G-S$ から辺 $uv$ を除くと $u$ を含む成分 $X$ と $v$ を含む成分 $Y$ に分かれます。$G-S$ の頂点数は $n-|S|\ge(k+1)-(k-2)=3$ なので、たとえば $X$ に $u$ 以外の頂点 $w$ があります。$G-(S\cup\{u\})$ の中の $w$ から $v$ への道は、辺 $uv$ を使わない $G-S$ の道なので、存在しません。すると $S\cup\{u\}$ は大きさ $k-1$ 以下の分離集合となり、$k$-連結性に反します。よって 定理 5.4 の 1 を $G'$ に使って、$G'$ に $u$ から $v$ への内素な道が $k-1$ 本あり、辺 $uv$ と合わせて $k$ 本です。

∎

5.1. 扇の補題と、指定した頂点を通る閉路

補題 5.6（扇の補題）✓

$k\ge1$、$G$ を $k$-連結グラフ、$x$ をその頂点、$Y\subseteq V(G)\setminus\{x\}$ を $|Y|\ge k$ である頂点集合とする。このとき、$x$ から $Y$ の相異なる頂点への $k$ 本の道で、どの 2 本も $x$ 以外に頂点を共有せず、各道が終点以外に $Y$ の頂点を含まないもの（$x$ から $Y$ への $k$-扇）が存在する。

証明（補題 5.6）

$G$ に新しい頂点 $z$ を足し、$Y$ の全頂点と結んだグラフを $G^+$ とします。$G^+$ は $k$-連結です。実際、頂点数は $k+1$ より大きく、$k$ 個未満の頂点の集合 $S$ を除くと、$z\in S$ なら $G^+-S=G-(S\setminus\{z\})$ は連結、$z\notin S$ なら $G-S$ は連結で、$z$ は $Y\setminus S\ne\varnothing$（$|Y|\ge k>|S|$）の頂点と隣接するので、やはり連結です。

系 5.5 の 1 から、$G^+$ に $x$ から $z$ への内素な道が $k$ 本あります。各道を $x$ からたどって最初に $Y$ の頂点に出会ったところで打ち切ります（$z$ の隣接点は $Y$ の頂点だけなので、必ず出会います）。打ち切った道は $G$ の道で、終点以外に $Y$ の頂点を含みません。終点は元の道の内部の頂点なので、道ごとに異なります。$x$ 以外の頂点を共有しないことは、元の道が内素であることから従います。

∎

定理 5.7（k-連結グラフでは任意の k 頂点が閉路に乗る）✓

$k\ge2$ とする。$k$-連結グラフ $G$ の任意の $k$ 個の頂点に対し、それらをすべて通る閉路が存在する。

証明の方針です。$k-1$ 個の頂点を通る閉路 $C$ から始め、残りの 1 頂点 $x_k$ から $C$ へ扇を張ります。そして $C$ の一部を、$x_k$ を経由する道に付け替えて、$k$ 個すべてを通る閉路にします。

証明（定理 5.7）

$k$ についての帰納法（定理 3.2［証明の技術］）です。$k=2$ は 定理 3.2 の $(1)\Rightarrow(2)$ です。$k\ge3$ とし、$k-1$ では正しいとします。$x_1,\dots,x_k$ を $G$ の相異なる頂点とします。$G$ は $(k-1)$-連結でもあるので、$x_1,\dots,x_{k-1}$ を通る閉路 $C$ があります。$x_k$ が $C$ の上にあれば終わりなので、ないとします。

場合 1: $C$ の頂点が $k$ 個以上. 補題 5.6 を $x=x_k$、$Y=V(C)$ に使い、$x_k$ から $C$ への $k$-扇を取ります。扇の道は終点でだけ $C$ と交わります。$C$ に向きを付け、$x_1,\dots,x_{k-1}$ が $C$ の上でこの順に並んでいるとして（番号を付け替えればよい）、$C$ の頂点を $k-1$ 個の区間

$$I_j=\{x_j\text{ から向きに沿って進み、}x_{j+1}\text{ の直前までの頂点}\}\qquad(j=1,\dots,k-1,\ x_k\text{ の代わりに }x_1)$$

に分けます。扇の終点は $k$ 個あるので、鳩の巣原理（定理 7.5［数え上げと母関数］）から、同じ区間 $I_j$ に入る 2 つの終点 $y,y'$ があります。向きに沿って $y$、$y'$ の順に並んでいるとすると、$C$ の上で $y$ から $y'$ へ向きに沿って進む部分の内部には、$x_1,\dots,x_{k-1}$ のどれもありません。$C$ のこの部分を、扇の 2 本の道をつないだ「$y$ から $x_k$ を経て $y'$ へ」の道で置き換えると、$x_1,\dots,x_k$ をすべて通る閉路になります。

場合 2: $C$ の頂点が $k-1$ 個. このとき $V(C)=\{x_1,\dots,x_{k-1}\}$ です。$G$ は $(k-1)$-連結なので、補題 5.6 から $x_k$ から $V(C)$ への $(k-1)$-扇があり、その終点は $C$ の全頂点です。$C$ の上で隣り合う 2 頂点 $y,y'$ を選び（$k-1\ge2$）、辺 $yy'$ を「$y$ から $x_k$ を経て $y'$ へ」の道で置き換えれば、$x_1,\dots,x_k$ をすべて通る閉路になります。

∎

定理 5.8（Chvátal–Erdős の定理）✓

$n\ge3$ 頂点のグラフ $G$ が $\kappa(G)\ge\alpha(G)$ を満たせば、$G$ は Hamilton 閉路をもつ。ここで $\alpha(G)$ は独立数（定義 2.2［マッチング］）である。

証明（定理 5.8）

$k=\kappa(G)$ と置きます。$\alpha(G)=1$ なら $G$ は完全グラフで、$n\ge3$ なので Hamilton 閉路をもちます。$\alpha(G)\ge2$ とすると $k\ge2$ で、定理 2.2 から $\delta(G)\ge k\ge2$ です。命題 3.1［道・閉路・木］ から $G$ は長さ $k+1$ 以上の閉路を含みます。

$G$ の最長の閉路 $C$ を取り、向きを付けます。$C$ が Hamilton 閉路でないとして矛盾を導きます。$G-V(C)$ の連結成分 $H$ を 1 つ取り、$H$ の頂点と隣接する $C$ の頂点の集合を $N$ とします。

$|N|\ge k$. $N=V(C)$ なら $|N|=|V(C)|\ge k+1$ です。$N\ne V(C)$ なら、$H$ の頂点から $V(C)\setminus N$ の頂点への道は必ず $N$ を通る（$H$ から外へ出る辺は $N$ の頂点にしか行きません）ので、$N$ は分離集合で、$|N|\ge k$ です。

$v\in N$ に対し、$C$ の上で向きに沿って $v$ の次の頂点を $v^+$ と書き、$N^+=\{v^+:v\in N\}$ とします。$u,v\in N$ が相異なるとき、$u$ の隣接点 $h_u\in V(H)$ と $v$ の隣接点 $h_v\in V(H)$ を $H$ の中の道で結ぶことで、$u$ から $v$ への、内部の頂点がすべて $H$ に属する（1 個以上ある）道が取れます。これを $uHv$ と書きます。

$N^+\cap N=\varnothing$. $v\in N$ かつ $v^+\in N$ とすると、$C$ の辺 $vv^+$ を道 $vHv^+$ で置き換えた閉路は $C$ より長く、矛盾です。

$N^+$ は独立集合. $u\ne v$ を $N$ の頂点とし、$u^+v^+\in E(G)$ とします。$u^+$ から $C$ を向きに沿って $v$ まで進み、道 $vHu$ で $u$ に移り、$u$ から $C$ を向きと逆に $v^+$ まで進み、辺 $v^+u^+$ で戻る閉じた歩道を考えます。$C$ は向きに沿って $u,u^+,\dots,v,v^+,\dots$ と並んでいるので、この歩道は $C$ の全頂点を 1 回ずつ通り、さらに $H$ の頂点を 1 個以上通る閉路です。$C$ より長く、矛盾です。

矛盾. $h\in V(H)$ を取ります。$N^+$ の頂点は $N$ に属さないので $h$ と隣接しません。よって $N^+\cup\{h\}$ は独立集合で、その大きさは $|N|+1\ge k+1>\alpha(G)$ です。これは $\alpha(G)$ の定義に反します。

∎

Dirac の定理（定理 6.6［道・閉路・木］）と比べてみます。$\delta\ge n/2$ のグラフでは $\kappa\ge\alpha$ が成り立つ（演習 7.3）ので、Dirac の定理は Chvátal–Erdős の定理から導き直せます。逆に、Petersen グラフは $\kappa=3$（例 2.4）で、外側と内側の五角形から 2 頂点ずつ選んだ独立集合があるので $\alpha\ge4>\kappa$ であり、Hamilton 閉路をもたないことと矛盾しません。

6. フローから Hall と König を導く

第 2 章では Hall の定理と König–Egerváry の定理を交互道で直接証明しました。ここでは、Menger の定理（したがって最大フロー最小カット定理）だけから両方を導き直します。3 つの最大最小定理が同じ 1 つの原理の現れであることが分かります。

命題 6.1（Menger の定理から König と Hall が従う）✓

$G$ を二部グラフ、$(A,B)$ をその二部分割とする。$G$ に新しい頂点 $s,t$ を足し、$s$ を $A$ の全頂点と、$t$ を $B$ の全頂点と結んだグラフを $G^\pm$ とする。

1. $G^\pm$ の $s$ から $t$ への内素な道の最大本数は $\nu(G)$ に等しく、$s$ と $t$ を分離する頂点集合の大きさの最小値は $\tau(G)$ に等しい。したがって 定理 5.4 の 1 から $\nu(G)=\tau(G)$ が従う。
2. $\nu(G)=\tau(G)$ から、「どの $S\subseteq A$ についても $|N(S)|\ge|S|$ ならば、$A$ を飽和するマッチングがある」が従う。

証明（命題 6.1）

1. 道とマッチング. $G$ のマッチング $\{a_1b_1,\dots,a_kb_k\}$（$a_i\in A$、$b_i\in B$）に対し、道 $sa_ib_it$ は $k$ 本の内素な道です。逆に、$s$ から $t$ への $k$ 本の内素な道を取ります。各道から $s,t$ を除くと、$A$ の頂点から始まり $B$ の頂点で終わる $G$ の道なので、$A$ の頂点と $B$ の頂点を結ぶ辺を少なくとも 1 本含みます。各道からそのような辺を 1 本ずつ選ぶと、道が内素なので端点を共有せず、大きさ $k$ のマッチングになります。よって内素な道の最大本数は $\nu(G)$ です。

分離集合と頂点被覆. $X\subseteq A\cup B$ とします。$X$ が頂点被覆でなければ、両端が $X$ に入らない辺 $ab$ があり、道 $sabt$ が $G^\pm-X$ に残るので、$X$ は $s,t$ を分離しません。$X$ が頂点被覆なら、$s$ から $t$ への道はどれも上で見たように $G$ の辺を含み、その端点の一方が $X$ に入るので、$X$ は $s,t$ を分離します。よって分離する頂点集合の最小の大きさは $\tau(G)$ です。

$s$ と $t$ は隣接しないので、定理 5.4 の 1 から両者は等しく、$\nu(G)=\tau(G)$ です。

2. 大きさ $\tau(G)=\nu(G)$ の頂点被覆 $K$ を取ります。$A\setminus K$ の頂点に接続する辺は、$B$ 側の端点で覆われていなければならないので、$N(A\setminus K)\subseteq K\cap B$ です。仮定から

$$|K\cap B|\ge|N(A\setminus K)|\ge|A\setminus K|$$

なので、$\nu(G)=|K|=|K\cap A|+|K\cap B|\ge|K\cap A|+|A\setminus K|=|A|$ です。大きさ $|A|$ のマッチングは $A$ の全頂点を飽和します。

∎

例 6.2（二部グラフの最大マッチングをフローで求める）

$G^\pm$ の辺を $s\to A\to B\to t$ の向きに向け、すべての容量を 1 にしたネットワークを考えます。整数値のフロー（定理 4.9）は、$A$ の各頂点に入る量が 1 以下、$B$ の各頂点から出る量が 1 以下なので、流れている $A$ から $B$ への辺の全体がマッチングになり、流量がその大きさです。第 2 章の 例 3.4［マッチング］ のグラフ（辺 $a_1b_1,a_1b_2,a_2b_1,a_2b_3,a_3b_2$）で、マッチング $\{a_1b_2,a_2b_1\}$ に対応する流量 2 のフローから出発すると、増加道

$$s\to a_3\to b_2\ \overset{\text{逆}}{\to}\ a_1\to b_1\ \overset{\text{逆}}{\to}\ a_2\to b_3\to t$$

が見つかります。これは第 2 章の $M$-増加道の前後に $s$ と $t$ を付けたものです。フローの増加道の「逆方向の残余辺」は、マッチングの増加道の「$M$ の辺」にちょうど対応しています。

注意 6.3

辺連結度に関する最大最小定理には、ほかに「辺素な全域木の最大本数」を与える Nash-Williams と Tutte の定理があります。グラフが $k$ 本の辺素な全域木をもつのは、頂点集合のどの分割についても、異なる部分を結ぶ辺が $k(\text{部分の個数}-1)$ 本以上あるとき、そのときに限る、というものです。この章では使わないので、主張の紹介にとどめます（参考文献の Diestel の第 2 章にあります）。

7. 演習

演習 7.1標準

超立方体 $Q_n$（第 1 章の 例 6.13［道・閉路・木］）について $\kappa(Q_n)=\lambda(Q_n)=n$ を示せ。

解答

$Q_n$ は $n$-正則なので、定理 2.2 から $\kappa\le\lambda\le n$ です。$\kappa(Q_n)\ge n$ を $n$ についての帰納法で示します。$Q_1=K_2$ は $\kappa=1$ です。$n\ge2$ とします。$Q_n$ の頂点を先頭の文字が 0 のもの $V_0$ と 1 のもの $V_1$ に分けると、$Q_n[V_0]$ と $Q_n[V_1]$ はどちらも $Q_{n-1}$ と同型で、先頭の文字だけが異なる頂点どうしを結ぶ $2^{n-1}$ 本の辺（完全マッチング）で結ばれています。

$|S|\le n-1$ である頂点集合 $S$ を除いても連結であることを示します（$k$-連結の定義にある頂点数の条件 $2^n>n$ は成り立っています）。

$|S\cap V_0|\le n-2$ かつ $|S\cap V_1|\le n-2$ のとき. 帰納法の仮定 $\kappa(Q_{n-1})\ge n-1$ から、$Q_n[V_0]-S$ と $Q_n[V_1]-S$ はどちらも連結です。$V_0$ と $V_1$ を結ぶ $2^{n-1}$ 本の辺のうち、$S$ の頂点を端点にもつものは $|S|\le n-1$ 本以下で、$n\ge2$ では $2^{n-1}>n-1$ なので、両端が $S$ に入らない辺が残ります。よって $Q_n-S$ は連結です。

そうでないとき. $S$ の $n-1$ 個の頂点がすべて一方、たとえば $V_0$ に入っています。$Q_n[V_1]$ は無傷で連結で、$V_0\setminus S$ の各頂点は $V_1$ に隣接点をもつので、$Q_n-S$ は連結です。

演習 7.2易

例 4.10 のネットワークで、辺 $(d,t)$ の容量を 1 から 3 に変える。最大フローの流量と最小カットを求めよ。

解答

$S=\{s\}$ の容量は $2+2=4$ なので、流量は 4 以下です。$s\to a\to c\to t$ に 2、$s\to b\to d\to t$ に 2 を流すと、容量制約（$(a,c):2$、$(c,t):2$、$(b,d):2$、$(d,t):3$）と保存則を満たす流量 4 のフローになります。補題 4.3 から、これが最大フローで、$\{s\}$ が最小カットです。$\{s,a,b\}$ から出る辺は $(a,c),(a,d),(b,d)$ で容量は $2+1+2=5$ なので、こちらは最小カットではありません。

演習 7.3標準

$n\ge3$ 頂点のグラフ $G$ が $\delta(G)\ge n/2$ を満たせば $\kappa(G)\ge\alpha(G)$ であることを示せ（したがって Dirac の定理は Chvátal–Erdős の定理から従う）。

解答

$G$ が完全グラフなら $\kappa=n-1\ge1=\alpha$ です。完全でないとし、最小の分離集合 $S$（$|S|=\kappa$）と最大の独立集合 $I$（$|I|=\alpha$）を取ります。$\kappa<\alpha$ と仮定して矛盾を導きます。

$I\setminus S$ は $G-S$ の 1 つの成分に含まれる. $|I|>|S|$ なので $I\setminus S\ne\varnothing$ です。$u,v\in I\setminus S$ を相異なる 2 頂点とします。$I$ は独立集合なので $N(u)$ と $N(v)$ はどちらも $V(G)\setminus I$（$n-\alpha$ 個）に含まれ、

$$|N(u)\cap N(v)|=|N(u)|+|N(v)|-|N(u)\cup N(v)|\ge2\delta-(n-\alpha)\ge\alpha>|S|$$

です（$2\delta\ge n$ を使いました）。よって $u$ と $v$ は $S$ に入らない共通の隣接点をもち、$G-S$ の同じ成分に属します。$I\setminus S$ を含む成分の頂点集合を $Z$ とすると、$I\subseteq Z\cup S$ です。

$Z\cup S$ は大きい. $u\in I\setminus S$ を 1 つ取ります。$u\in Z$ なので $N(u)\subseteq Z\cup S$ で、$N(u)\cap I=\varnothing$ です。$Z\cup S$ は互いに交わらない $I$ と $N(u)$ を含むので、$|Z\cup S|\ge\alpha+\delta$ です。

別の成分も大きい. $S$ は分離集合なので、$Z$ と異なる成分 $Z'$ があります。$y\in Z'$ を取ると $N(y)\subseteq Z'\cup S$ なので、$|Z'|\ge1+d(y)-|S|\ge\delta+1-|S|$ です。

矛盾. $Z\cup S$ と $Z'$ は交わらないので

$$n\ge|Z\cup S|+|Z'|\ge(\alpha+\delta)+(\delta+1-|S|)=2\delta+1+(\alpha-|S|)\ge2\delta+2>n$$

です（$\alpha-|S|\ge1$ と $2\delta\ge n$ を使いました）。これは矛盾なので、$\kappa\ge\alpha$ です。

演習 7.4難

フローを使わずに Menger の定理を証明する。グラフ $G$ と頂点集合 $A,B\subseteq V(G)$ に対し、$A$ の頂点から $B$ の頂点への道（1 点だけの道も含める）を $A$–$B$ 道と呼び、$G-X$ に $A$–$B$ 道がなくなる $X\subseteq V(G)$ の大きさの最小値を $k$ とする。$G$ には互いに頂点を共有しない $A$–$B$ 道が $k$ 本あることを、辺の数についての帰納法で示せ。辺 $e=xy$ を縮約したグラフ $G/e$（$x,y$ を 1 頂点 $v_e$ にまとめ、$x$ または $y$ の隣接点すべてと結ぶ。$x,y$ の一方が $A$ に属せば $v_e$ も $A$ に属するとし、$B$ も同様）と、$e$ を除いたグラフ $G-e$ を使う。

解答

辺がなければ、$A$–$B$ 道は $A\cap B$ の 1 点だけの道で、$k=|A\cap B|$ 本あります。辺 $e=xy$ があるとし、辺の数がより少ないグラフでは主張が正しいとします。$G$ に頂点を共有しない $A$–$B$ 道が $k$ 本ないとして矛盾を導きます。

$G/e$ を見る. $G/e$ に頂点を共有しない $A$–$B$ 道が $k$ 本あれば、$v_e$ を通る道（高々 1 本）で $v_e$ を $x$、$y$、または辺 $xy$ に置き換えて（前後の頂点が $x,y$ のどちらと隣接するか、端点なら $x,y$ のどちらが $A$ や $B$ に属するかに合わせて選びます）、$G$ の $k$ 本の道が得られます。よって $G/e$ にはそのような $k$ 本はなく、帰納法の仮定から、$G/e$ には $A$–$B$ 道をなくす頂点集合 $Y$ で $|Y|\le k-1$ のものがあります。$v_e\notin Y$ なら $Y$ は $G$ でも $A$–$B$ 道をなくす（$G-Y$ の $A$–$B$ 道は $G/e-Y$ の $A$–$B$ 歩道を与える）ので、$k$ の最小性に反します。よって $v_e\in Y$ で、$X=(Y\setminus\{v_e\})\cup\{x,y\}$ は $G$ の $A$–$B$ 道をなくす集合で $|X|\le k$、したがって $|X|=k$ です。

$G-e$ を見る. $G-e$ の中で $A$–$X$ 道をなくす頂点集合 $Z$ を取ります。$G$ の $A$–$B$ 道 $P$ は $X$ の頂点を通るので、$P$ を $A$ 側からたどって最初に $X$ に出会うまでの部分は $A$–$X$ 道で、$X$ の頂点を 1 つしか含まないので辺 $e=xy$ を使いません。これは $G-e$ の $A$–$X$ 道なので $Z$ の頂点を通ります。よって $Z$ は $G$ の $A$–$B$ 道もなくし、$|Z|\ge k$ です。$G-e$ は辺が少ないので、帰納法の仮定から頂点を共有しない $A$–$X$ 道が $k$ 本あります。各道を最初に $X$ に出会ったところで打ち切ると、$|X|=k$ なので、$X$ の各頂点がちょうど 1 本の終点になり、各道は終点以外で $X$ と交わりません。同様に、頂点を共有しない $X$–$B$ 道が $k$ 本あり、$X$ の各頂点がちょうど 1 本の始点で、始点以外で $X$ と交わりません。

つなぐ. $A$–$X$ 道と $X$–$B$ 道が $X$ の外の頂点 $z$ を共有したとすると、前者を $A$ から $z$ まで、後者を $z$ から $B$ までたどる歩道は $X$ を通らない $A$–$B$ 歩道となり、$X$ の性質に反します。よって、$X$ の各頂点で 2 本の道をつなぐと、頂点を共有しない $A$–$B$ 道が $k$ 本でき、仮定に反します。

定理 5.4 の 1 は、$G-\{s,t\}$ で $A=N(s)$、$B=N(t)$ とした場合です。

参考文献

• R. Diestel, Graph Theory, Graduate Texts in Mathematics 173, Springer — 第 3 章（連結度、Menger の定理）、第 6 章（フロー）。
• J. A. Bondy, U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008 — 連結度とフローの章。
• L. R. Ford, D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962.
• J. Edmonds, R. M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems”, J. ACM 19 (1972), 248–264.
• V. Chvátal, P. Erdős, “A note on Hamiltonian circuits”, Discrete Math. 2 (1972), 111–113.