マッチング：Hall の結婚定理・König の定理・Tutte の定理

0. この記事の要点

仕事の割り当てや、組み合わせの相手決めのように、「互いに重ならないように相手を 1 人ずつ選ぶ」問題がこの記事の主題です。選べないときに、その理由を 1 つの小さな「障害」で言い切れるか、というのが素朴な疑問になります。読み終えると、割り当てが可能かどうかを判定する条件と、不可能なときにその理由を示す方法が分かります。以下の箇条書きは全体の地図なので、初めて見る用語があっても、各節で順に説明するので読み進めてください。

• マッチングが最大であることと、増加道が存在しないことは同値です（Berge の定理、定理 3.3）。2 つのマッチングの対称差が道と偶閉路に分かれることが根拠です。
• 二部グラフでは、片側 $A$ を飽和するマッチングがあることと、どの $S\subseteq A$ についても $|N(S)|\ge|S|$ であることが同値です（Hall の結婚定理、定理 4.2）。帰納法と増加道の 2 通りで証明します。
• 二部グラフでは、最大マッチングの大きさ $\nu$ と最小頂点被覆の大きさ $\tau$ が一致します（König–Egerváry の定理、定理 4.9）。これは半順序集合の Dilworth の定理と互いに導けます。
• 二重確率行列は置換行列の凸結合です（Birkhoff–von Neumann の定理、定理 6.2）。Hall の定理を行列の言葉に直したものです。
• 一般のグラフが完全マッチングをもつのは、どの頂点集合 $S$ についても $G-S$ の奇成分が $|S|$ 個以下のとき、そのときに限ります（Tutte の 1-因子定理、定理 7.2）。辺極大な反例の構造を調べて証明します。
• 選好順位つきの二部マッチングには、必ず安定なものがあり、提案する側にとって最良のものが提案の手続きで得られます（Gale–Shapley の定理、定理 8.2）。

この記事で使う事前知識

• 隣接・次数: 2 つの頂点が辺で結ばれているとき隣接するといい、頂点に接続する辺の本数を次数という。→ 隣接
• 道・閉路: 頂点を辺でたどった列が道で、始点に戻るものが閉路。→ 閉路
• 部分グラフ: 頂点と辺の一部だけを取り出したグラフ。全頂点を残すものを全域部分グラフという。→ 部分グラフ
• 連結成分: グラフを辺でつながった塊に分けたときの、それぞれの塊。→ 連結成分
• 半順序集合: 反射律・反対称律・推移律を満たす大小関係をもつ集合（§5 で使う）。→ 半順序集合
• 行列式: 正方行列に対して決まる数で、置換についての和で書かれる（§6 の例で使う）。→ 行列式

1. 動機

5 人の応募者と 5 つの仕事があり、各応募者にはこなせる仕事がいくつかあるとします。全員に、別々の、こなせる仕事を割り当てられるでしょうか。できない理由として分かりやすいのは、「ある 3 人がこなせる仕事を全部集めても 2 つしかない」という状況です。この 3 人に別々の仕事は割り当てられません。Hall の結婚定理は、割り当てができない理由はこの型のものしかないと主張します。

この「障害がなければ、できる」という形は、この章のどの定理にも共通しています。障害は、Hall の定理では近傍の小さい集合、König の定理では小さい頂点被覆、Tutte の定理では奇成分をたくさん残す頂点集合です。最大マッチングの大きさ（最大化問題の答え）が、障害の大きさ（最小化問題の答え）と一致するという形に書けるので、これらは最大最小定理と呼ばれます。第 3 章 では、同じ型の Menger の定理と最大フロー最小カット定理を扱い、そこから Hall と König の定理を導き直します。

証明の道具は、二部グラフと一般のグラフで切り替えます。二部グラフ（§4）では「増加道が無いときに、非飽和な頂点から交互道で届く範囲を調べる」という 1 つの議論（補題 4.1）で Hall と König の両方を示します。一般のグラフ（§7）ではこの議論が奇閉路のために壊れるので、「完全マッチングをもたない辺極大なグラフはどんな形か」を調べる議論に切り替えます。

グラフの語彙は 第 1 章 に従い、グラフは有限・単純・無向とします。

2. マッチング・被覆・独立集合

定義 2.1（マッチング）↗

グラフ $G$ の辺集合 $M\subseteq E(G)$ で、どの 2 辺も端点を共有しないものをマッチングという。$M$ の辺の端点になっている頂点は $M$ で飽和されているといい、そうでない頂点は非飽和であるという。$uv\in M$ のとき、$v$ を $u$ の（$M$ での）相手という。辺の数が最大のマッチングを最大マッチング、その辺の数をマッチング数 $\nu(G)$ という。全頂点を飽和するマッチングを完全マッチングまたは 1-因子という。一般に、$k$-正則な全域部分グラフを $k$-因子という。

定義 2.2（頂点被覆・独立集合・辺被覆）↗

• $K\subseteq V(G)$ が頂点被覆であるとは、どの辺も $K$ の頂点を端点にもつことをいう。最小の大きさを被覆数 $\tau(G)$ という。
• $I\subseteq V(G)$ が独立集合であるとは、$I$ のどの 2 頂点も隣接しないことをいう。最大の大きさを独立数 $\alpha(G)$ という。
• $L\subseteq E(G)$ が辺被覆であるとは、どの頂点も $L$ のある辺の端点であることをいう。最小の大きさを辺被覆数 $\rho(G)$ という（孤立点のないグラフでだけ定義される）。
• $S\subseteq V(G)$ の近傍を $N(S)=\bigcup_{v\in S}N(v)$ と書く。

補題 2.3（弱双対性）✓

どのグラフでも、マッチング $M$ と頂点被覆 $K$ について $|M|\le|K|$ である。とくに $\nu(G)\le\tau(G)$ であり、$|M|=|K|$ となる組があれば $M$ は最大マッチング、$K$ は最小頂点被覆である。

証明（補題 2.3）

$M$ の各辺 $e$ は $K$ の頂点を端点にもつので、その 1 つを $\varphi(e)\in K$ と選びます。$M$ の辺は端点を共有しないので、$\varphi:M\to K$ は単射で、$|M|\le|K|$ です。最大マッチングと最小頂点被覆に当てはめれば $\nu\le\tau$ です。$|M|=|K|$ なら $|M|\le\nu\le\tau\le|K|=|M|$ となり、すべて等号です。

∎

三角形 $K_3$ では $\nu=1$、$\tau=2$ なので、一般には等号は成り立ちません。二部グラフでは等号が成り立つ、というのが König–Egerváry の定理です。

3. 増加道と Berge の定理

定義 3.1（交互道・増加道）↗

$M$ をマッチングとする。道 $P=x_0x_1\cdots x_k$ が $M$-交互道であるとは、辺 $x_{i-1}x_i$ が $M$ に属するものと属さないものが交互に並ぶことをいう。両端点 $x_0\ne x_k$ がどちらも $M$ で非飽和な $M$-交互道を $M$-増加道という。

増加道の最初と最後の辺は、端点が非飽和なので $M$ に属しません。したがって増加道の長さは奇数で、$M$ に属さない辺が属する辺より 1 本多くなっています。

補題 3.2（最大次数 2 のグラフの形）✓

最大次数が 2 以下の連結グラフは、道グラフか閉路グラフである。

証明（補題 3.2）

$H$ を最大次数 2 以下の連結グラフ、$P=v_0\cdots v_k$ を $H$ の最長の道とします。$k=0$ なら、連結性から $H$ は 1 頂点です。$k\ge1$ とします。内部の頂点 $v_1,\dots,v_{k-1}$ は道の上で 2 つの隣接点をもつので、それ以外の辺をもちません。端点 $v_0$ の隣接点は、$P$ が最長なので $P$ の上にあります（命題 3.1［道・閉路・木］ の証明の手順 1）。それは $v_1$ のほかには、まだ次数に余裕のある $v_k$ しかありえません。$v_k$ についても同じです。したがって、$P$ の頂点の間の辺は、$P$ の辺と、あるとすれば $v_0v_k$（$k\ge2$）だけで、$P$ の頂点と $P$ の外の頂点を結ぶ辺はありません。$H$ は連結なので $V(H)=V(P)$ で、$H$ は $P$ か、$P$ に $v_0v_k$ を足した閉路です。

∎

定理 3.3（Berge の定理）✓

グラフ $G$ のマッチング $M$ が最大マッチングであるためには、$M$-増加道が存在しないことが必要十分である。

証明（定理 3.3）

必要性（増加道があれば大きくできる）. $P=x_0\cdots x_k$ を $M$-増加道とし、$M'=M\triangle E(P)$（対称差。$P$ の上で $M$ の辺とそうでない辺を入れ替える）と置きます。$M'$ がマッチングであることを確かめます。$P$ の外の頂点に接続する $M'$ の辺は $M$ の辺と同じです。$P$ の内部の頂点 $x_i$ では、$P$ の 2 辺のうち一方だけが $M$ に属し、$x_i$ に接続する $M$ の辺はそれだけなので、入れ替えたあとも $x_i$ に接続する $M'$ の辺はちょうど 1 本です。端点 $x_0,x_k$ は $M$ で非飽和だったので、接続する $M'$ の辺は $P$ の端の辺 1 本だけです。よって $M'$ はマッチングで、$|M'|=|M|+1$ です。$M$ は最大ではありません。

十分性（最大でなければ増加道がある）. $|M'|>|M|$ であるマッチング $M'$ があるとします。全域部分グラフ $H=(V(G),M\triangle M')$ を考えます。各頂点に接続する $M$ の辺も $M'$ の辺も高々 1 本なので、$H$ の最大次数は 2 以下です。補題 3.2 から、$H$ の各連結成分は道か閉路です。$H$ の次数 2 の頂点では、接続する 2 辺の一方が $M\setminus M'$、他方が $M'\setminus M$ に属します。したがって、各成分の上で $M$ の辺と $M'$ の辺は交互に並びます。

閉路の成分では、交互に並ぶので $M$ の辺と $M'$ の辺は同数です。$|M'\setminus M|>|M\setminus M'|$ なので、$M'$ の辺のほうが多い成分があり、それは道 $Q$ で、最初と最後の辺が $M'$ に属します。$Q$ は $M$-交互道です。

$Q$ の端点 $x$ が $M$ で非飽和であることを示します。$x$ に接続する $Q$ の辺を $e\in M'\setminus M$ とします。$x$ が $M$ の辺 $f$ で飽和されているとすると、$e\notin M$ から $f\ne e$ です。$f\in M'$ なら $x$ に $M'$ の辺が 2 本接続して矛盾するので、$f\in M\setminus M'\subseteq E(H)$ です。すると $x$ の $H$ での次数は 2 以上となり、$x$ が道 $Q$ の端点（次数 1）であることに反します。よって $Q$ は $M$-増加道です。

∎

例 3.4（増加道を追う）

$A=\{a_1,a_2,a_3\}$、$B=\{b_1,b_2,b_3\}$ とし、$K_{3,3}$ から 4 辺を除いて辺を $a_1b_1,\ a_1b_2,\ a_2b_1,\ a_2b_3,\ a_3b_2$ の 5 本にしたグラフを考えます。マッチング $M=\{a_1b_2,\ a_2b_1\}$ では $a_3$ と $b_3$ が非飽和です。$a_3$ から出発すると、

$$a_3\ \overset{\notin M}{\longrightarrow}\ b_2\ \overset{\in M}{\longrightarrow}\ a_1\ \overset{\notin M}{\longrightarrow}\ b_1\ \overset{\in M}{\longrightarrow}\ a_2\ \overset{\notin M}{\longrightarrow}\ b_3$$

が $M$-増加道です。入れ替えると $M'=\{a_3b_2,\ a_1b_1,\ a_2b_3\}$ となり、これは完全マッチングです。$a_3$ の隣接点は $b_2$ だけなので、$a_3$ を飽和するには、いったん $a_1$ を $b_2$ から引きはがして $b_1$ に移し、$a_2$ を $b_3$ に移すという玉突きが必要でした。増加道はこの玉突きを記述しています。

次の動画で、増加道が $a_3$ から $b_3$ へ 1 辺ずつ伸び、最後に道の上で入れ替わってマッチングが 1 本増える様子を見てください。

例の増加道をたどる動画。赤が道、太線がマッチングです。道の上で $M$ の辺と $M$ にない辺を入れ替えると、$M^{\prime }$ は完全マッチングになります。

4. 二部グラフ：Hall の定理と König の定理

この節では $G$ を二部グラフとし、二部分割 $(A,B)$ を 1 つ固定します。二部グラフの交互道は $A$ と $B$ の頂点を交互に通ります。$A$ の非飽和な頂点 $u$ から出発する $M$-交互道 $x_0x_1x_2\cdots$（$x_0=u$）では、$x_0$ が非飽和なので最初の辺は $M$ に属さず、

$$x_{2j}\in A,\quad x_{2j+1}\in B,\quad x_{2j}x_{2j+1}\notin M,\quad x_{2j+1}x_{2j+2}\in M$$

となります。「$A$ から $B$ へは $M$ に属さない辺で、$B$ から $A$ へは $M$ の辺で」進むわけです。

次の補題のねらいは、増加道が無いときに、非飽和な頂点から交互道でたどれる頂点を $A$ 側の集合 $S$ と $B$ 側の集合 $T$ に分けて調べることです。結論は、$T$ が $S$ の近傍そのものになり、しかも $T$ の大きさが $S$ より非飽和な頂点の数だけ小さい、というものです。この $S$ が Hall の条件を破る集合になり、$(A\setminus S)\cup T$ が小さい頂点被覆になります。

補題 4.1（交互道で届く範囲）✓

二部グラフ $G$（二部分割 $(A,B)$）のマッチング $M$ が増加道をもたないとする。$A$ の $M$-非飽和な頂点の集合を $U$ とし、$U$ の頂点から出発する $M$-交互道で届く頂点全体を $Z$、$S=Z\cap A$、$T=Z\cap B$ と置く（長さ 0 の道を含めるので $U\subseteq S$）。このとき次が成り立つ。

1. $T$ の頂点はすべて $M$ で飽和されていて、その相手は $S\setminus U$ に属する。$M$ は $T$ から $S\setminus U$ への全単射を与え、$|T|=|S|-|U|$ である。
2. $N(S)=T$ である。

証明（補題 4.1）

1. $t\in T$ とし、$U$ の頂点 $x_0$ から $t$ への $M$-交互道 $P=x_0x_1\cdots x_{2k+1}$（$x_{2k+1}=t$）を取ります。$t$ が非飽和なら $P$ は両端が非飽和な交互道、すなわち増加道となり、仮定に反します。よって $t$ は飽和されています。相手を $t'\in A$ とします。$t'$ が $P$ の上にあるとすると、$t'=x_{2j}$（$A$ の頂点なので添字は偶数）です。$j=0$ なら $x_0$ が非飽和であることに反し、$j\ge1$ なら $x_{2j}$ の相手は $x_{2j-1}\ne t$ なので矛盾します。したがって $t'$ は $P$ の上になく、$P$ に $M$ の辺 $tt'$ を足した道も $M$-交互道で、$t'\in S$ です。$t'$ は飽和されているので $t'\in S\setminus U$ です。

$M$ はマッチングなので、対応 $t\mapsto t'$ は単射です。全射であることを示します。$s\in S\setminus U$ とすると、$s$ への交互道 $x_0\cdots x_{2j}$（$x_{2j}=s$）は、$s\notin U$ かつ $s\ne x_0$（$x_0=s$ だと $s\in U$）なので $j\ge1$ で、最後の辺 $x_{2j-1}x_{2j}$ は $M$ に属します。$x_{2j-1}\in T$ で、その相手が $s$ です。よって全単射で、$|T|=|S\setminus U|=|S|-|U|$ です。

2. $T\subseteq N(S)$ を示します。$t\in T$ への交互道 $x_0\cdots x_{2k+1}$ で、$x_{2k}\in S$ は $t$ と隣接します。

$N(S)\subseteq T$ を示します。$s\in S$、$b\in N(s)$ とします。$sb\in M$ のとき、$s$ は飽和されているので $s\in S\setminus U$ で、1 の全射性の証明から、$s$ の相手 $b$ は $T$ に属します。$sb\notin M$ のとき、$U$ の頂点から $s$ への交互道 $P$（長さは偶数）を取ります。$b$ が $P$ の上にあれば、$P$ の途中までの部分も交互道なので $b\in Z\cap B=T$ です。$b$ が $P$ の上になければ、$P$ の最後の辺は（あれば）$M$ に属するので、$P$ に $M$ に属さない辺 $sb$ を足した道も交互道で、$b\in T$ です。

∎

補題の例。$A=\{a_1,a_2,a_3\}$、$B=\{b_1,b_2\}$、辺は $a_1{b}_1,a_2{b}_1,a_2{b}_2,a_3{b}_1$、$M=\{a_1{b}_1,a_2{b}_2\}$（太線）。非飽和な $a_3$ から届くのは $a_3\to b_1\to a_1$ で、$S=\{a_3,a_1\}$（塗りつぶし）、$T=\{b_1\}$（塗りつぶし）です。$N(S)=\{b_1\}=T$ で、$|T|=|S|-|U|=1$ になっています。

定理 4.2（Hall の結婚定理）✓

二部グラフ $G$（二部分割 $(A,B)$）が $A$ の全頂点を飽和するマッチングをもつためには、

$$|N(S)|\ge|S|\qquad(\text{すべての }S\subseteq A)$$

が成り立つこと（Hall の条件）が必要十分である。

証明（定理 4.2）

必要性. $M$ が $A$ を飽和するとします。$S\subseteq A$ の各頂点の相手は $N(S)$ に属し、相異なります。よって $|N(S)|\ge|S|$ です。

十分性の第 1 の証明（$|A|$ についての帰納法）. 完全帰納法（定理 4.3［証明の技術］）を使います。$|A|=0$ なら空のマッチングでよく、$|A|=1$ なら $|N(A)|\ge1$ なので辺が 1 本取れます。$|A|\ge2$ とし、$A$ 側の頂点数がより小さい二部グラフでは定理が正しいとします。

場合 1: 空でない真部分集合 $S\subsetneq A$ がすべて $|N(S)|\ge|S|+1$ を満たす. 辺 $ab$（$a\in A$、$b\in B$）を 1 本選び、$G'=G-\{a,b\}$ とします。空でない $S\subseteq A\setminus\{a\}$ について、$N_{G'}(S)=N(S)\setminus\{b\}$ なので $|N_{G'}(S)|\ge|N(S)|-1\ge|S|$ です。$G'$ は Hall の条件を満たすので、帰納法の仮定から $A\setminus\{a\}$ を飽和するマッチングがあり、辺 $ab$ を足せば $A$ を飽和します。

場合 2: 空でない真部分集合 $S_0\subsetneq A$ で $|N(S_0)|=|S_0|$ となるものがある. $G_1=G[S_0\cup N(S_0)]$ では、$S\subseteq S_0$ の近傍は $G$ での近傍と同じなので、Hall の条件が成り立ちます。$|S_0|<|A|$ なので、帰納法の仮定から $G_1$ に $S_0$ を飽和するマッチング $M_1$ があります。

$G_2=G-(S_0\cup N(S_0))$ とします。$S\subseteq A\setminus S_0$ について $N_{G_2}(S)=N(S)\setminus N(S_0)$ です。$N(S\cup S_0)$ は $N(S_0)$ と $N(S)\setminus N(S_0)$ の非交和なので、$G$ の Hall の条件から

$$|N_{G_2}(S)|=|N(S\cup S_0)|-|N(S_0)|\ge(|S|+|S_0|)-|S_0|=|S|$$

です。$|A\setminus S_0|<|A|$ なので、$G_2$ に $A\setminus S_0$ を飽和するマッチング $M_2$ があります。$M_1$ と $M_2$ は頂点を共有しないので、$M_1\cup M_2$ は $A$ を飽和するマッチングです。

十分性の第 2 の証明（増加道）. $M$ を $G$ の最大マッチングとします。定理 3.3 の必要性の側から、$M$-増加道はありません。$A$ に非飽和な頂点があるとして、補題 4.1 の $U\ne\varnothing$、$S$、$T$ を取ると、

$$|N(S)|=|T|=|S|-|U|<|S|$$

となり、Hall の条件に反します。よって $M$ は $A$ を飽和します。

∎

第 2 の証明は、Hall の条件を破る集合 $S$ を具体的に与えます。最大マッチングを 1 つ求めれば、「なぜこれ以上大きくできないか」の証拠が交互道で届く範囲として手に入るわけです。

系 4.3（不足数版）✓

二部グラフ $G$（二部分割 $(A,B)$）の不足数を $\operatorname{def}(G)=\max_{S\subseteq A}\bigl(|S|-|N(S)|\bigr)$ と定める（$S=\varnothing$ を取れるので $\operatorname{def}(G)\ge0$）。このとき

$$\nu(G)=|A|-\operatorname{def}(G)$$

である。

証明（系 4.3）

$d=\operatorname{def}(G)$ と置きます。

$\nu\le|A|-d$. $M$ をマッチング、$S\subseteq A$ とします。$S$ の飽和された頂点の相手は $N(S)$ の相異なる頂点なので、$S$ の飽和された頂点は $|N(S)|$ 個以下で、$A$ の非飽和な頂点は $|S|-|N(S)|$ 個以上です。$S$ を動かして $|M|\le|A|-d$ を得ます。

$\nu\ge|A|-d$. $B$ に新しい頂点を $d$ 個足し、それぞれを $A$ の全頂点と結んだ二部グラフを $G^+$ とします。空でない $S\subseteq A$ について $|N_{G^+}(S)|=|N(S)|+d\ge|S|$ なので、$G^+$ は Hall の条件を満たし、定理 4.2 から $A$ を飽和するマッチング $M^+$ があります。新しい頂点に接続する辺は $M^+$ に高々 $d$ 本なので、それらを除くと $G$ のマッチングで辺が $|A|-d$ 本以上のものが残ります。

∎

系 4.4（相異なる代表系）✓

有限集合の族 $A_1,\dots,A_n$ について、相異なる元 $x_1,\dots,x_n$ で $x_i\in A_i$ となるもの（相異なる代表系、SDR）が存在するためには、どの $I\subseteq\{1,\dots,n\}$ についても $\bigl|\bigcup_{i\in I}A_i\bigr|\ge|I|$ であることが必要十分である。

証明（系 4.4）

添字の集合 $A=\{1,\dots,n\}$ と元の集合 $B=\bigcup_iA_i$ を 2 つの側とし（添字と元は別の頂点として扱います）、$x\in A_i$ のとき $i$ と $x$ を結んだ二部グラフを作ります。$I\subseteq A$ の近傍は $\bigcup_{i\in I}A_i$ で、$A$ を飽和するマッチングは SDR にほかなりません。定理 4.2 がそのまま主張を与えます。

∎

系 4.5（正則二部グラフの完全マッチング）✓

$k\ge1$ とする。$k$-正則な二部グラフは完全マッチングをもつ。

証明（系 4.5）

二部分割を $(A,B)$ とします。辺の数を $A$ 側、$B$ 側から数えると $k|A|=|E(G)|=k|B|$ なので $|A|=|B|$ です。$S\subseteq A$ とします。$S$ の頂点に接続する辺は $k|S|$ 本で、そのもう一方の端点はすべて $N(S)$ に入ります。$N(S)$ の頂点に接続する辺は全部で $k|N(S)|$ 本なので、$k|S|\le k|N(S)|$、すなわち $|N(S)|\ge|S|$ です。定理 4.2 から $A$ を飽和するマッチングがあり、$|A|=|B|$ なのでそれは完全マッチングです。

∎

例 4.6（トランプ 52 枚を 13 山に分ける）

ジョーカーを除く 52 枚のトランプを、4 枚ずつ 13 の山に勝手に分けます。このとき、各山から 1 枚ずつ選んで、A, 2, …, K の 13 種類の数字がすべてそろうようにできます。山を $A$ 側、数字を $B$ 側とし、山にその数字のカードが入っているとき結んだ二部グラフを考えます。$k$ 個の山には $4k$ 枚のカードがあり、同じ数字のカードは 4 枚しかないので、そこに現れる数字は $k$ 種類以上です。Hall の条件が成り立つので、定理 4.2 から 13 の山を相異なる数字に対応させるマッチングがあり、数字は 13 種類なのですべてそろいます。

例 4.7（Latin 長方形は Latin 方陣に延長できる）

$r\times n$ の表（$r<n$）の各マスに $1,\dots,n$ の数字を入れ、どの行にもどの列にも同じ数字が 2 回現れないようにしたものを Latin 長方形といいます。これには必ず $r+1$ 行目を足せます。列を $A$ 側、数字を $B$ 側とし、列にまだその数字が現れていないとき結びます。各列には $r$ 個の数字が現れているので、列の次数は $n-r$ です。各数字は各行にちょうど 1 回、つまり $r$ 個の相異なる列に現れているので、数字の次数も $n-r$ です。$(n-r)$-正則な二部グラフなので、系 4.5 から完全マッチングがあり、それが $r+1$ 行目を与えます。繰り返せば $n\times n$ の Latin 方陣になります。

例 4.8（無限グラフでは Hall の条件だけでは足りない）

$A=\{a_0,a_1,a_2,\dots\}$、$B=\{b_1,b_2,\dots\}$ とし、$a_0$ をすべての $b_j$ と、$a_i$（$i\ge1$）を $b_i$ だけと結びます。有限集合 $S\subseteq A$ について、$a_0\notin S$ なら $|N(S)|=|S|$、$a_0\in S$ なら $N(S)=B$ は無限集合なので、Hall の条件は成り立ちます。しかし $A$ を飽和するマッチングはありません。$a_0$ の相手を $b_k$ とすると、$a_k$ の唯一の隣接点が取られてしまうからです。定理 4.2 の証明は、どちらも有限性（帰納法、最大マッチングの存在）を使っています。

定理 4.9（König–Egerváry の定理）✓

二部グラフ $G$ では $\nu(G)=\tau(G)$ である。

証明（定理 4.9）

$M$ を最大マッチングとします。定理 3.3 から増加道はないので、補題 4.1 の $U,S,T$ が取れます。

$$K=(A\setminus S)\cup T$$

が頂点被覆で、$|K|=|M|$ であることを示します。そうすれば 補題 2.3 から $\nu=|M|=|K|=\tau$ です。

$K$ は頂点被覆. 辺 $ab$（$a\in A$、$b\in B$）を取ります。$a\notin S$ なら $a\in K$ です。$a\in S$ なら、補題 4.1 の 2 から $b\in N(S)=T\subseteq K$ です。

$|K|=|M|$. $A\setminus S$ の頂点は、$U\subseteq S$ なのですべて飽和されています。$T$ の頂点も 補題 4.1 の 1 からすべて飽和されています。よって $K$ の各頂点は $M$ の辺をちょうど 1 本もちます。$M$ の 1 本の辺 $ab$ が $K$ の頂点を 2 つ含むとすると、$a\in A\setminus S$ かつ $b\in T$ ですが、$T$ の頂点の相手は $S$ に属する（同 1）ので矛盾します。よって対応「$K$ の頂点 $\mapsto$ それを含む $M$ の辺」は単射で、$|K|\le|M|$ です。逆向きの不等式は 補題 2.3 です。

∎

5. Gallai の恒等式と Dilworth の定理との関係

この節の後半では半順序集合の言葉が出ます。鎖は、どの 2 元も大小が比べられる部分集合、反鎖は、どの 2 元も大小が比べられない部分集合のことで、幅は反鎖の大きさの最大値です。

4 つの量 $\nu,\tau,\alpha,\rho$ の間には、二部グラフに限らず成り立つ 2 つの関係があります。

定理 5.1（Gallai の恒等式）✓

$n$ 頂点のグラフ $G$ について $\alpha(G)+\tau(G)=n$ が成り立つ。さらに $G$ に孤立点がなければ $\nu(G)+\rho(G)=n$ が成り立つ。

証明（定理 5.1）

$\alpha+\tau=n$. $I\subseteq V(G)$ が独立集合であることは、両端が $I$ に入る辺がないこと、すなわちどの辺も $V(G)\setminus I$ に端点をもつことと同じで、これは $V(G)\setminus I$ が頂点被覆であることです。よって最大の独立集合の補集合は最小の頂点被覆で、$\alpha=n-\tau$ です。

$\rho\le n-\nu$. 最大マッチング $M$ を取ります。非飽和な頂点は $n-2\nu$ 個あり、孤立点はないので、それぞれに接続する辺を 1 本ずつ選んで $M$ に足すと辺被覆になります。その辺の数は $\nu+(n-2\nu)=n-\nu$ 以下です。

$\rho\ge n-\nu$. 最小の辺被覆 $L$ を取り、$L$ に含まれるマッチングのうち辺の数が最大のもの $M$ を取ります。$M$ で非飽和な頂点の集合を $W$ とすると、$|W|=n-2|M|$ です。$L$ の辺で両端が $W$ に入るものはありません（あれば $M$ に足せて、$M$ の選び方に反します）。$W$ の各頂点は $L$ の辺で覆われ、その辺は $M$ に属さず（$W$ の頂点は $M$ で非飽和）、$W$ の頂点を 1 つしか含みません。よって $|L\setminus M|\ge|W|$ で、

$$\rho=|L|\ge|M|+(n-2|M|)=n-|M|\ge n-\nu$$

です。

∎

二部グラフでは 定理 4.9 と合わせて $\alpha=n-\nu$、孤立点がなければ $\alpha=\rho$ となります。

König–Egerváry の定理は、半順序集合の Dilworth の定理（定理 8.2［半順序集合と Möbius 反転］。鎖分割の最小個数は幅に等しい）と同じ内容を別の言葉で述べたものです。鎖・反鎖・幅の定義は 定義 8.1［半順序集合と Möbius 反転］ に従います。

命題 5.2（König の定理と Dilworth の定理は互いに導ける）✓

1. 二部グラフ $G$（二部分割 $(A,B)$、$n$ 頂点）に対し、$V(G)$ 上の半順序を「$a<b\iff a\in A,\ b\in B,\ ab\in E(G)$」で定めると、鎖分割の最小個数は $n-\nu(G)$、幅は $n-\tau(G)$ である。したがって、この半順序集合に対する Dilworth の定理の主張は $\nu(G)=\tau(G)$ と同値である。
2. $n$ 元の有限半順序集合 $P=\{p_1,\dots,p_n\}$ に対し、頂点 $a_1,\dots,a_n,b_1,\dots,b_n$ をもち「$a_ib_j$ が辺 $\iff p_i<p_j$」である二部グラフ $G_P$ を作る。このとき $P$ は $n-\nu(G_P)$ 個の鎖に分割でき、大きさ $n-\tau(G_P)$ 以上の反鎖をもつ。したがって、$\nu(G_P)=\tau(G_P)$ から $P$ に対する Dilworth の定理が従う。

証明（命題 5.2）

1. 定めた関係は、$x<y<z$ となる 3 元がない（$y$ は $B$ と $A$ の両方に属することになる）ので推移律を自明に満たし、半順序です。鎖は 1 元か、隣接する 2 元 $\{a,b\}$ です。鎖分割で 2 元の鎖の全体はマッチングをなし、逆にマッチング $M$ は「$M$ の辺と、非飽和な頂点 1 つずつ」という $n-|M|$ 個の鎖への分割を与えます。よって鎖分割の最小個数は $n-\nu(G)$ です。相異なる 2 元が比較可能であることは隣接することと同じなので、反鎖は独立集合で、幅は $\alpha(G)=n-\tau(G)$ です（定理 5.1）。「鎖分割の最小個数 $=$ 幅」は $n-\nu=n-\tau$ となります。

2. 鎖分割. $G_P$ の最大マッチング $M$ を取り、$a_ib_j\in M$ のとき $p_i\to p_j$ と矢印を引きます。$a_i$ は $M$ の辺を高々 1 本もつので各元から出る矢印は高々 1 本、$b_j$ についても同様に各元に入る矢印は高々 1 本です。矢印 $p_i\to p_j$ は $p_i<p_j$ を意味するので、矢印をたどって元に戻ることはありません。矢印を辺と見たグラフが閉路をもつとすると、閉路の各頂点で 2 本の辺の一方が入る矢印、他方が出る矢印でなければならず、矢印をたどって一周できてしまうので、このグラフは森です。辺は $|M|=\nu(G_P)$ 本なので、連結成分は $n-\nu(G_P)$ 個です（補題 2.2［グラフと行列式］）。各成分は最大次数 2 以下の木、すなわち道（補題 3.2）で、矢印の向きに $p_{i_1}<p_{i_2}<\cdots$ と並ぶ鎖です。これで $P$ が $n-\nu(G_P)$ 個の鎖に分割されました。

反鎖. $G_P$ の最小頂点被覆 $K$ を取り、$Q=\{p_i: a_i\notin K\text{ かつ }b_i\notin K\}$ とします。$K$ の各頂点が除外する添字は 1 つなので $|Q|\ge n-|K|=n-\tau(G_P)$ です。$p_i,p_j\in Q$ で $p_i<p_j$ とすると、辺 $a_ib_j$ の両端がどちらも $K$ に入らず、$K$ が頂点被覆であることに反します。よって $Q$ は反鎖です。

Dilworth の定理. 鎖と反鎖は高々 1 元でしか交わらないので、どの鎖分割の鎖の個数も、どの反鎖の大きさ以上です。$\nu(G_P)=\tau(G_P)$ なら、上で作った鎖分割と反鎖は個数と大きさが一致する（$n-\nu(G_P)$ 個の鎖と、$n-\nu(G_P)$ 元以上の反鎖）ので、鎖分割の最小個数と幅はどちらも $n-\nu(G_P)$ に等しくなります。

∎

反鎖への分割についての双対な主張（Mirsky の定理、命題 8.3［半順序集合と Möbius 反転］）は、最長の鎖の長さで層に分けるだけで示せます。Dilworth の定理のほうが深いのは、König の定理と同じく「増加道」にあたる組み替えが必要だからです。

6. Birkhoff–von Neumann の定理

定義 6.1（二重確率行列・置換行列）↗

成分がすべて非負の実数で、各行の和と各列の和がすべて 1 である $n$ 次正方行列を二重確率行列という。$\{1,\dots,n\}$ の置換 $\sigma$ に対し、$(i,\sigma(i))$ 成分が 1 でほかの成分が 0 の行列 $P_\sigma$ を置換行列という。

定理 6.2（Birkhoff–von Neumann の定理）✓

$n$ 次の二重確率行列 $A$ は、置換行列の凸結合である。すなわち、置換 $\sigma_1,\dots,\sigma_r$ と正の実数 $\lambda_1,\dots,\lambda_r$ で

$$A=\sum_{k=1}^r\lambda_kP_{\sigma_k},\qquad\sum_{k=1}^r\lambda_k=1$$

となるものがある。

証明（定理 6.2）

少し一般にして、次を示します。

主張. 成分が非負で、各行の和と各列の和がすべて同じ値 $s\ge0$ である $n$ 次正方行列 $A$ は、$A=\sum_k\lambda_kP_{\sigma_k}$（$\lambda_k>0$、$\sum_k\lambda_k=s$）と書ける。

$A$ の正の成分の個数についての完全帰納法（定理 4.3［証明の技術］）で示します。正の成分がなければ $A=O$、$s=0$ で、空の和が答えです。

正の成分があるとします。このとき $s>0$ です。行 $1,\dots,n$ を一方の側、列 $1,\dots,n$ を他方の側とし、$a_{ij}>0$ のとき行 $i$ と列 $j$ を結んだ二部グラフ $H$ を作ります。行の集合 $S$ を取ると、$S$ の行の成分の総和は $s|S|$ です。この総和に寄与する正の成分はすべて $N(S)$ の列にあり、$N(S)$ の列の成分の総和は $s|N(S)|$ なので、$s|S|\le s|N(S)|$、すなわち $|N(S)|\ge|S|$ です。定理 4.2 から行をすべて飽和するマッチングがあり、行と列は同数なのでこれは完全マッチングです。言い換えると、置換 $\sigma$ で、すべての $i$ について $a_{i\sigma(i)}>0$ となるものがあります。

$\lambda=\min_ia_{i\sigma(i)}>0$ とし、$A'=A-\lambda P_\sigma$ と置きます。$A'$ の成分は非負で、各行・各列の和は $s-\lambda\ge0$ です（$\lambda\le a_{i\sigma(i)}\le s$）。最小値を達成する成分が 0 になるので、$A'$ の正の成分は $A$ より少なくなります。帰納法の仮定から $A'=\sum_k\lambda_kP_{\sigma_k}$、$\sum_k\lambda_k=s-\lambda$ と書け、$A=\lambda P_\sigma+\sum_k\lambda_kP_{\sigma_k}$ が求める表示です。

定理は $s=1$ の場合です。

∎

例 6.3（分解の計算と、行列式の展開項との対応）

$$A=\frac14\begin{pmatrix}2&2&0\\1&1&2\\1&1&2\end{pmatrix}$$

は二重確率行列です。証明の手順を実行します。置換を $(\sigma(1),\sigma(2),\sigma(3))$ で表します。$\sigma=(1,2,3)$ は $a_{11},a_{22},a_{33}>0$ を満たし、最小値は $1/4$ です。引くと $\frac14\begin{pmatrix}1&2&0\\1&0&2\\1&1&1\end{pmatrix}$ が残ります。次に $\sigma=(2,3,1)$ を係数 $1/4$ で引くと $\frac14\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}$、さらに $\sigma=(1,3,2)$ を係数 $1/4$ で引くと $\frac14\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}=\frac14P_{(2,1,3)}$ が残ります。したがって

$$A=\tfrac14\bigl(P_{(1,2,3)}+P_{(2,3,1)}+P_{(1,3,2)}+P_{(2,1,3)}\bigr)$$

です。

証明に現れた二部グラフ $H$ の完全マッチングは、「すべての $i$ で $a_{i\sigma(i)}\ne0$ となる置換 $\sigma$」、つまり行列式 $\det A=\sum_\sigma\operatorname{sgn}(\sigma)\prod_ia_{i\sigma(i)}$ の 0 でない展開項と 1 対 1 に対応します。第 1 行で余因子展開（定理 5.2［行列式とその性質］）することは、行 1 の相手の列を選んで残りの $2\times2$ の問題に帰着することにあたります。この例では 0 でない項はちょうど上の 4 つの置換で、$4A$ について各項の絶対値は $4$、符号は順に $+,+,-,-$ なので $\det(4A)=0$ です（第 2 行と第 3 行が等しいことと合っています）。完全マッチングがあっても、符号の相殺で行列式は 0 になりえます。符号を付けない和（パーマネント）は $16$ で、完全マッチングの「重み付きの個数」です。平面的グラフでは符号をうまく付けて行列式で完全マッチングを数えられます（Kasteleyn の定理、定理 4.6［グラフと行列式］）。

7. 一般のグラフ：Tutte の定理

二部グラフでないグラフでは、補題 4.1 の議論が壊れます。奇閉路があると、同じ頂点に $M$ の辺で届く交互道と $M$ でない辺で届く交互道の両方がありえて、「$A$ 側・$B$ 側」の区別ができないからです。ここからは、交互道を追う代わりに、完全マッチングをもたないグラフに辺を足せるだけ足したらどんな形になるかを調べます。

定義 7.1（奇成分）↗

頂点数が奇数の連結成分を奇成分といい、グラフ $H$ の奇成分の個数を $o(H)$ と書く。$G-v$ がどの頂点 $v$ についても完全マッチングをもつグラフ $G$ を因子臨界という。

$S\subseteq V(G)$ を除いたとき、$G-S$ の奇成分 $C$ の頂点を $C$ の中だけで完全にマッチングすることはできません。少なくとも 1 頂点は $S$ の頂点を相手にする必要があります。したがって、完全マッチングがあるなら $o(G-S)\le|S|$ でなければなりません。Tutte の定理は、これが唯一の障害だと主張します。

定理 7.2（Tutte の 1-因子定理）✓

グラフ $G$ が完全マッチングをもつためには、

$$o(G-S)\le|S|\qquad(\text{すべての }S\subseteq V(G))$$

が成り立つこと（Tutte の条件）が必要十分である。

証明の方針は、完全マッチングをもたない反例があるなら、辺を足せるだけ足した極大な反例を作り、その形が完全グラフの寄せ集めになることを示して、完全マッチングを実際に組み立てて矛盾させる、というものです。手順 3 の $x,y,z,w$ は、「完全グラフでない」と仮定した成分から、辺を 1 本足すだけで完全マッチングが現れる 2 か所を取り出すための頂点です。

証明（定理 7.2）

必要性. $M$ を完全マッチング、$S\subseteq V(G)$ とします。$G-S$ の奇成分 $C$ の頂点がすべて $C$ の中の相手をもつとすると $|V(C)|$ が偶数になるので、$C$ には $S$ の頂点を相手とする頂点があります。その相手を $\varphi(C)\in S$ とすると、$M$ はマッチングなので $\varphi$ は単射で、$o(G-S)\le|S|$ です。

十分性. $G$ が Tutte の条件を満たすのに完全マッチングをもたないとして、矛盾を導きます。

手順 0: $n$ は偶数. $S=\varnothing$ とすると $o(G)\le0$ なので、$G$ のどの成分も頂点数が偶数で、$n=|V(G)|$ は偶数です。

手順 1: 辺を足しても Tutte の条件は保たれる. $G'=G+e$ とし、$S\subseteq V(G)$ を取ります。$G'-S$ の各連結成分は、$G-S$ の連結成分 1 つか、2 つの合併です。$G'-S$ の奇成分は、その中に $G-S$ の奇成分を少なくとも 1 つ（奇数個）含みます。よって $o(G'-S)\le o(G-S)\le|S|$ です。

手順 2: 辺極大な反例を取る. $n$ は偶数なので $K_n$ は完全マッチングをもちます。$G$ に辺を足していくと、いつか完全マッチングをもつようになります。そこで、$G$ を含む同じ頂点集合上のグラフ $G^*$ で、完全マッチングをもたず、どの非隣接な 2 頂点の間に辺を足しても完全マッチングをもつようになるものが取れます。手順 1 から $G^*$ も Tutte の条件を満たします。

手順 3: $G^*$ の構造. 他のすべての頂点と隣接する頂点の集合を $U$ とします。$G^*-U$ のどの連結成分も完全グラフであることを示します。

そうでないとすると、ある成分に隣接しない 2 頂点があります。それらを結ぶ成分内の最短の道の最初の 3 頂点を $x,y,z$ とすると、$xy,yz\in E(G^*)$、$xz\notin E(G^*)$ です（$xz$ が辺なら道を短くできます）。$y\notin U$ なので、$yw\notin E(G^*)$ となる頂点 $w\ne y$ があります（$w\ne x,z$ です）。$G^*$ の極大性から、$G^*+xz$ は完全マッチング $M_1$ を、$G^*+yw$ は完全マッチング $M_2$ をもちます。$G^*$ 自身は完全マッチングをもたないので、$xz\in M_1$、$yw\in M_2$ です。また $xz\notin M_2$、$yw\notin M_1$ です。

$F=M_1\triangle M_2$ とします。各頂点は $M_1$ の辺と $M_2$ の辺をちょうど 1 本ずつもち、それらが同じ辺なら $F$ での次数は 0、違えば 2 です。補題 3.2 から、$F$ の辺をもつ成分は閉路で、その上で $M_1$ の辺と $M_2$ の辺が交互に並びます（とくに長さは偶数）。$xz$ と $yw$ はどちらも $F$ に属します。

場合 A: $xz$ と $yw$ が $F$ の異なる閉路に乗る. $yw$ の乗る閉路を $C$ とします。$C$ の上では $M_1$ の辺を、$C$ の外では $M_2$ の辺を選ぶと、これは完全マッチングです（$C$ の頂点は $C$ の上の $M_1$ の辺で、$C$ の外の頂点は $C$ の外の $M_2$ の辺で、ちょうど 1 回ずつ覆われます）。$C$ の上の $M_1$ の辺に $xz$ はなく（$xz$ は別の閉路の上）、$C$ の外の $M_2$ の辺に $yw$ はないので、これは $G^*$ の完全マッチングとなり、矛盾です。

場合 B: $xz$ と $yw$ が同じ閉路 $C$ に乗る. $C$ を $y$ から、辺 $yw$ でないほうの辺を通って進み、

$$y=c_0,\ c_1,\ c_2,\ \dots,\ c_L=w$$

と頂点を並べます（最後に辺 $wy$ で戻ります）。$yw\in M_2$ なので、辺 $c_ic_{i+1}$ は $i$ が偶数のとき $M_1$、奇数のとき $M_2$ に属します。辺 $xz$ はこの列の隣り合う 2 頂点を結びます。$xz=c_jc_{j+1}$ とし、$a=c_j$、$b=c_{j+1}$ と置きます（$\{a,b\}=\{x,z\}$）。$xz\in M_1$ なので $j$ は偶数で、$y\ne x,z$ から $j\ge2$ です。

次の辺の集合 $M$ を考えます。

• $c_1c_2,\ c_3c_4,\ \dots,\ c_{j-1}c_j$（$M_2$ の辺。$c_1,\dots,c_j$ を覆う）、
• 辺 $yb=c_0c_{j+1}$（$b\in\{x,z\}$ は $y$ と隣接するので $G^*$ の辺）、
• $c_{j+2}c_{j+3},\ \dots,\ c_{L-1}c_L$（$M_1$ の辺。$L$ は奇数なので $c_{j+2},\dots,c_L$ をちょうど覆う）、
• $C$ の外では $M_2$ の辺。

$L$ が奇数であることは、$C$ の長さ $L+1$ が偶数であることから分かります。$M$ は全頂点をちょうど 1 回ずつ覆う完全マッチングです。$M$ は $xz=c_jc_{j+1}$ も $yw=c_Lc_0$ も含まないので、$G^*$ の完全マッチングです。これは矛盾です。

以上から、$G^*-U$ の連結成分はすべて完全グラフです。

手順 4: 完全マッチングを作る. $G^*$ は Tutte の条件を満たすので $o(G^*-U)\le|U|$ です。$G^*-U$ の各奇成分から 1 頂点ずつ選び、$U$ の相異なる頂点と結びます（$U$ の頂点は全頂点と隣接し、奇成分は $|U|$ 個以下なので可能です）。各成分の残りの頂点は偶数個で、成分は完全グラフなので、成分の中で 2 つずつ組にできます。最後に、$U$ のまだ相手のいない頂点が残ります。$n$ は偶数で、ここまでに相手の決まった頂点は偶数個なので、残りは偶数個です。$U$ の頂点は互いに隣接するので、2 つずつ組にできます。これで $G^*$ の完全マッチングができ、$G^*$ の選び方に反します。

∎

系 7.3（Petersen の定理）✓

橋をもたない 3-正則グラフは、完全マッチングをもつ。

証明（系 7.3）

Tutte の条件を確かめます。$S\subseteq V(G)$ とし、$C$ を $G-S$ の奇成分とします。$C$ と $S$ を結ぶ辺の本数を $e(C,S)$ とします。$C$ は $G-S$ の連結成分なので、$C$ の頂点に接続する辺は、$C$ の中の辺か、$S$ への辺です。握手補題（補題 2.2［道・閉路・木］）と同じ数え方で、$C$ の頂点の次数の和は

$$3|V(C)|=2|E(C)|+e(C,S)$$

です。$|V(C)|$ は奇数なので、$e(C,S)$ は奇数です。$e(C,S)=1$ だとすると、その 1 本の辺を除けば $C$ の頂点から $C$ の外へ出る辺がなくなるので、この辺の両端は異なる連結成分に属し、この辺は橋です。$G$ は橋をもたないので、$e(C,S)\ge3$ です。

一方、$S$ の頂点に接続する辺は全部で $3|S|$ 本以下です。奇成分ごとに $S$ への辺が 3 本以上あり、異なる成分への辺は異なるので、

$$3\,o(G-S)\le\sum_C e(C,S)\le3|S|$$

となり、$o(G-S)\le|S|$ です。定理 7.2 から $G$ は完全マッチングをもちます。

∎

例 7.4（「橋をもたない」を外すと成り立たない）

頂点 $c$ を 3 つの頂点 $a_1,a_2,a_3$ と結びます。各 $a_i$ に 4 頂点 $p_i,q_i,r_i,s_i$ を用意し、辺 $a_ip_i,\ a_iq_i,\ p_ir_i,\ p_is_i,\ q_ir_i,\ q_is_i,\ r_is_i$ を引きます。次数は $c$ が 3、$a_i$ が $c,p_i,q_i$ の 3、$p_i$ と $q_i$ が $a_i,r_i,s_i$ の 3、$r_i$ と $s_i$ が $p_i,q_i$ と互いの 3 で、3-正則な 16 頂点のグラフです。$S=\{c\}$ とすると、$G-S$ は 5 頂点の成分 3 つからなり、$o(G-S)=3>1=|S|$ です。定理 7.2 から完全マッチングはありません。3 本の辺 $ca_i$ はどれも橋です。なお、第 1 章の Petersen グラフは橋のない 3-正則グラフなので完全マッチングをもちます（たとえば 5 本のスポーク）。

Tutte の定理は、完全マッチングがないときに最大マッチングがどれだけ小さくなるかまで教えてくれます。

定理 7.5（Tutte–Berge の公式）✓

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

$$\nu(G)=\min_{S\subseteq V(G)}\frac{n+|S|-o(G-S)}{2}$$

が成り立つ。

証明（定理 7.5）

$d=\max_{S\subseteq V(G)}\bigl(o(G-S)-|S|\bigr)$ と置きます。$S=\varnothing$ が取れるので $d\ge0$ です。示すべき式は $\nu(G)=(n-d)/2$ です。

$\nu\le(n-d)/2$. $M$ をマッチング、$S\subseteq V(G)$ とします。$G-S$ の奇成分のうち、頂点がすべて $M$ で飽和されているものは、定理 7.2 の必要性の証明と同じ理由で、$S$ の頂点を相手とする頂点を含みます。そのような成分は $|S|$ 個以下です。残りの少なくとも $o(G-S)-|S|$ 個の奇成分は非飽和な頂点を含みます。$S$ を動かすと、非飽和な頂点は $d$ 個以上で、$2|M|\le n-d$ です。

偶奇. どの $S$ についても、$n=|S|+\sum_C|V(C)|$（$C$ は $G-S$ の成分）で、$|V(C)|$ が奇数の成分が $o(G-S)$ 個なので、$n\equiv|S|+o(G-S)\pmod2$、すなわち $o(G-S)-|S|\equiv n\pmod2$ です。とくに $d\equiv n\pmod2$ です。

$\nu\ge(n-d)/2$. $G$ に $d$ 個の新しい頂点の集合 $D$ を足し、$D$ の各頂点を他のすべての頂点（$V(G)$ の頂点と $D$ の他の頂点）と結んだグラフを $G^+$ とします。$G^+$ が Tutte の条件を満たすことを示します。$S'\subseteq V(G^+)$ とします。

• $D\subseteq S'$ のとき: $S=S'\setminus D$ と置くと $G^+-S'=G-S$ で、$o(G-S)\le|S|+d=|S'|$ です。
• $D\not\subseteq S'$ のとき: $S'$ に入らない $D$ の頂点は残りの全頂点と隣接するので、$G^+-S'$ は連結で、$o(G^+-S')\le1$ です。$S'\ne\varnothing$ なら $o(G^+-S')\le1\le|S'|$ です。$S'=\varnothing$ なら、$G^+$ の頂点数 $n+d$ は偶数なので $o(G^+)=0$ です。

定理 7.2 から $G^+$ は完全マッチング $M^+$ をもちます。$D$ の頂点に接続する $M^+$ の辺を除くと、$G$ のマッチングで、非飽和な頂点が $d$ 個以下のものが残ります。その辺の数は $(n-d)/2$ 以上です。

∎

注意 7.6

最小値を達成する $S$ をうまく選ぶと、$G-S$ の奇成分がすべて因子臨界で、偶成分が完全マッチングをもつようにできます（Gallai–Edmonds の構造定理）。また、一般のグラフの最大マッチングを多項式時間で求める Edmonds のアルゴリズムは、交互道の探索で出会った奇閉路を 1 点に縮約することで、§4 の議論を奇閉路のあるグラフに延長します。この章ではどちらも使いません。詳しくは参考文献の Lovász–Plummer を見てください。

8. 安定マッチング：Gale–Shapley の定理

最後に、頂点が相手に選好順位をもつ場合を考えます。大きさではなく「不満をもつ組がない」ことを求める点が、これまでと違います。

定義 8.1（安定マッチング）↗

$|A|=|B|=n$ とし、$A$ の各元は $B$ の元全体に、$B$ の各元は $A$ の元全体に、同順位のない順位（選好）を付けているとする。$A$ と $B$ の間の完全マッチング $M$ に対し、$M$ で組になっていない $a\in A$、$b\in B$ が、「$a$ は $M$ での相手より $b$ を好み、$b$ も $M$ での相手より $a$ を好む」を満たすとき、$(a,b)$ をブロッキング対という。ブロッキング対をもたない完全マッチングを安定マッチングという。

Gale–Shapley の手続き（$A$ が提案する版）は次のとおりです。最初はだれも組になっていません。各ラウンドで、相手のいない $a\in A$ はそれぞれ、まだ自分を断っていない $B$ の元のうち最も好む相手に提案します。各 $b\in B$ は、そのラウンドに受けた提案と、いま保留している相手のうち、最も好む 1 人を保留し、残りを断ります。相手のいない $a$ がいなくなったら終了し、保留の組をそのままマッチングにします。

定理 8.2（Gale–Shapley の定理）✓

どんな選好に対しても、Gale–Shapley の手続きは高々 $n^2$ 回の提案で終了し、安定マッチング $M^*$ を出力する。さらに $M^*$ は提案側に最適である。すなわち、どの $a\in A$ についても、$M^*$ での相手は、あらゆる安定マッチングでの $a$ の相手のうち $a$ が最も好む相手である。

証明の方針は、手続きが終わること、完全マッチングになること、安定であること、提案側に最適であることの順に確かめます。最後の部分は、「実現可能な相手に断られる」最初の出来事を考え、それがブロッキング対を生んで矛盾することを使います。

証明（定理 8.2）

手続きの定め方から、次の 2 つが成り立ちます。(i) $a$ は好む順に提案し、同じ相手に 2 回提案しない。(ii) $b$ は一度提案を受けると、それ以後ずっとだれかを保留していて、保留する相手は $b$ にとってよくなる一方である。

終了. (i) から、提案は全部で $n^2$ 回以下です。相手のいない $a$ がいる限り、次に述べるように $a$ には提案先が残っているので、各ラウンドで少なくとも 1 回の提案が行われ、手続きは終了します。

完全マッチングになる. ある $a$ が $B$ の全員に断られたとします。$b$ が $a$ を断るのは、$a$ より好む相手を保留するときなので、(ii) からその時点以後 $b$ はだれかを保留しています。すると $B$ の $n$ 人全員が、$a$ 以外の相異なる $A$ の元を保留していることになりますが、$a$ 以外の $A$ の元は $n-1$ 人しかいません。矛盾です。よって、相手のいない $a$ には必ず提案先が残っており、終了時には $A$ の全員が保留されています。保留は 1 対 1 なので、完全マッチング $M^*$ が得られます。

安定である. $a$ が $M^*$ での相手より $b$ を好むとします。(i) から $a$ は $b$ に提案して断られています。断ったとき $b$ は $a$ より好む相手を保留していて、(ii) から $M^*$ での $b$ の相手は $a$ より好ましい相手です。よって $(a,b)$ はブロッキング対ではありません。

提案側に最適である. ある安定マッチングで $a$ と組になる $b$ を、$a$ にとって実現可能な相手と呼びます。手続きの中で、どの $a$ も実現可能な相手から断られることはないことを示します。

そうでないとし、実現可能な相手から断られる最初の出来事を考えます。$a$ が $b$ に断られ、$a$ と $b$ を組にする安定マッチング $M'$ があるとします。断ったとき、$b$ は $a$ より好む $a'$ を保留しました。$a'$ はこの時点までに実現可能な相手から断られていません（最初の出来事だからです）。$a'$ は好む順に提案するので、$a'$ が $b$ より好む相手はすべて $a'$ を断っており、したがって $a'$ にとって実現可能ではありません。$M'$ での $a'$ の相手 $b'$ は $a'$ にとって実現可能で、$b'\ne b$（$M'$ で $b$ の相手は $a$）なので、$a'$ は $b'$ より $b$ を好みます。まとめると、$M'$ で組になっていない $a'$ と $b$ について、$a'$ は $M'$ での相手 $b'$ より $b$ を好み、$b$ は $M'$ での相手 $a$ より $a'$ を好みます。$(a',b)$ は $M'$ のブロッキング対で、$M'$ が安定であることに反します。

よって、$a$ が $M^*$ での相手より好む $b$ は、すべて $a$ を断っているので実現可能ではありません。$M^*$ は安定なので、$M^*$ での $a$ の相手は実現可能です。これが、実現可能な相手のうち最も好ましいものです。

∎

例 8.3（3 対 3 の選好表で実行する）

選好を次のように定めます（左ほど好む）。

	選好		選好
$a_1$	$b_1,b_2,b_3$	$b_1$	$a_3,a_2,a_1$
$a_2$	$b_1,b_3,b_2$	$b_2$	$a_1,a_2,a_3$
$a_3$	$b_2,b_1,b_3$	$b_3$	$a_1,a_3,a_2$

• ラウンド 1: $a_1\to b_1$、$a_2\to b_1$、$a_3\to b_2$。$b_1$ は $a_2$ を保留して $a_1$ を断り、$b_2$ は $a_3$ を保留します。
• ラウンド 2: $a_1\to b_2$。$b_2$ は $a_3$ より $a_1$ を好むので、$a_1$ を保留して $a_3$ を断ります。
• ラウンド 3: $a_3\to b_1$。$b_1$ は $a_2$ より $a_3$ を好むので、$a_3$ を保留して $a_2$ を断ります。
• ラウンド 4: $a_2\to b_3$。$b_3$ は $a_2$ を保留します。全員に相手ができたので終了です。

出力は $M^*=\{a_1b_2,\ a_2b_3,\ a_3b_1\}$ です。安定性を確かめます。$a_1$ が相手より好むのは $b_1$ ですが、$b_1$ の相手 $a_3$ は $b_1$ の第 1 希望です。$a_2$ が相手より好むのも $b_1$ で、同じ理由でブロッキング対になりません。$a_3$ が相手より好むのは $b_2$ ですが、$b_2$ の相手 $a_1$ は $b_2$ の第 1 希望です。$B$ 側が提案する版を実行しても同じマッチングが得られます（$b_1\to a_3$、$b_2\to a_1$、$b_3\to a_1$ から始まり、$b_3$ が $a_1$、$a_3$ に断られて $a_2$ に落ち着きます）。提案側最適なマッチングが両側で一致するので、この選好では安定マッチングはただ 1 つです（演習 9.4 を参照してください）。

9. 演習

演習 9.1易

木は完全マッチングを高々 1 つしかもたないことを示せ。

解答

木 $T$ が相異なる完全マッチング $M_1,M_2$ をもつとします。$F=M_1\triangle M_2\ne\varnothing$ です。各頂点は $M_1$ と $M_2$ の辺を 1 本ずつもつので、$F$ の辺に接続する頂点は、$F$ の辺をちょうど 2 本もちます。$F$ の辺とその端点からなる $T$ の部分グラフは最小次数 2 なので、命題 3.1［道・閉路・木］ から閉路を含みます。これは $T$ が閉路を含まないことに反します。

演習 9.2標準

頂点 $s$ と 3 つの三角形 $T_1,T_2,T_3$（合わせて 9 頂点）を用意し、$s$ を各三角形の 1 頂点 $t_i$ と結んだ 10 頂点のグラフ $G$ を考える。Tutte の条件を破る $S$ を見つけ、$\nu(G)$ を求めよ。

解答

$S=\{s\}$ とすると、$G-S$ は 3 つの三角形で、$o(G-S)=3>1=|S|$ です。定理 7.2 から完全マッチングはありません。定理 7.5 で $S=\{s\}$ を取ると $\nu(G)\le(10+1-3)/2=4$ です。一方、辺 $st_1$、$T_1$ の残り 2 頂点を結ぶ辺、$T_2$ の辺 1 本、$T_3$ の辺 1 本は大きさ 4 のマッチングです。よって $\nu(G)=4$ です。

演習 9.3標準

辺が $m$ 本、最大次数が $\Delta\ge1$ の二部グラフは、大きさ $m/\Delta$ 以上のマッチングをもつことを示せ。また、二部グラフでないと成り立たない例を挙げよ。

解答

$K$ を頂点被覆とします。1 つの頂点が覆う辺は $\Delta$ 本以下なので、$m\le\Delta|K|$、すなわち $\tau\ge m/\Delta$ です。二部グラフでは 定理 4.9 から $\nu=\tau\ge m/\Delta$ です。

三角形 $K_3$ は $m=3$、$\Delta=2$ で $m/\Delta=3/2$ ですが、$\nu=1$ です。

演習 9.4難

$A$ が提案する Gale–Shapley の手続きの出力 $M^*$ では、どの $b\in B$ の相手も、あらゆる安定マッチングでの $b$ の相手のうち $b$ にとって最も好ましくない相手であることを示せ。これを使って、$A$ が提案する版と $B$ が提案する版の出力が一致するなら、安定マッチングはただ 1 つであることを示せ。

解答

$M^*$ での $b$ の相手を $a$ とします。ある安定マッチング $M'$ で、$b$ の相手 $a'$ が $b$ にとって $a$ より好ましくないとします（$a'\ne a$）。$M'$ での $a$ の相手を $b'$ とすると $b'\ne b$ です。定理 8.2 から、$b$ は $a$ にとって実現可能な相手のうち最良なので、$a$ は $b'$ より $b$ を好みます。$b$ は $a'$ より $a$ を好みます。よって $(a,b)$ は $M'$ のブロッキング対で、$M'$ の安定性に反します。

後半を示します。$B$ が提案する版の出力を $M^{**}$ とします。定理 8.2 を $A$ と $B$ を入れ替えて使うと、$M^{**}$ では各 $b$ が安定マッチングの中で最良の相手を得ます。前半から、$M^*$ では各 $b$ が最悪の相手を得ます。$M^*=M^{**}$ なら、各 $b$ にとって最良の相手と最悪の相手が一致するので、どの安定マッチングでも $b$ の相手は同じです。したがって安定マッチングは 1 つしかありません。

参考文献

• L. Lovász, M. D. Plummer, Matching Theory, North-Holland, 1986 — 二部グラフのマッチング、Tutte の定理、Gallai–Edmonds の構造定理。
• R. Diestel, Graph Theory, Graduate Texts in Mathematics 173, Springer — 第 2 章（マッチング）。
• J. A. Bondy, U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008 — マッチングの章。
• P. Hall, “On representatives of subsets”, J. London Math. Soc. 10 (1935), 26–30.
• W. T. Tutte, “The factorization of linear graphs”, J. London Math. Soc. 22 (1947), 107–111.
• D. Gale, L. S. Shapley, “College admissions and the stability of marriage”, Amer. Math. Monthly 69 (1962), 9–15.