# マッチング：Hall の結婚定理・König の定理・Tutte の定理
> 増加道による Berge の定理から出発し、二部グラフの Hall の結婚定理と König–Egerváry の定理、Gallai の恒等式、Birkhoff–von Neumann の定理、一般のグラフの Tutte の 1-因子定理と Tutte–Berge の公式、安定マッチングの Gale–Shapley の定理を証明する。
> https://rikai.mugen-giken.com/mathematics/graph-theory/matchings
## 0. この記事の要点
仕事の割り当てや、組み合わせの相手決めのように、「互いに重ならないように相手を 1 人ずつ選ぶ」問題がこの記事の主題です。選べないときに、その理由を 1 つの小さな「障害」で言い切れるか、というのが素朴な疑問になります。読み終えると、割り当てが可能かどうかを判定する条件と、不可能なときにその理由を示す方法が分かります。以下の箇条書きは全体の地図なので、初めて見る用語があっても、各節で順に説明するので読み進めてください。
- マッチングが最大であることと、増加道が存在しないことは同値です（**Berge の定理**、
## 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$ が小さい頂点被覆になります。
二部グラフ $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$ である。
**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$ です。
二部グラフ $G$（二部分割 $(A,B)$）が $A$ の全頂点を飽和するマッチングをもつためには、
$$
|N(S)|\ge|S|\qquad(\text{すべての }S\subseteq A)
$$
が成り立つこと（**Hall の条件**）が必要十分である。
**必要性.** $M$ が $A$ を飽和するとします。$S\subseteq A$ の各頂点の相手は $N(S)$ に属し、相異なります。よって $|N(S)|\ge|S|$ です。
**十分性の第 1 の証明（$|A|$ についての帰納法）.** 完全帰納法（