結婚定理とマッチング

人 $1$ は $a$ と $b$、人 $2$ は $a$ だけ、人 $3$ は $b$ と $c$ ができるとする。
人 $2$ には $a$ しかないので、$2\to a$ と決まる。すると人 $1$ には $b$ しか残らないので $1\to b$、人 $3$ には $c$ しか残らないので $3\to c$ である。割り当て
$$ 1\to b,\qquad 2\to a,\qquad 3\to c $$
で、全員に互いに違う仕事が割り当てられた。この場合、割り当て方はこの 1 通りしかない（人 $2$ から順に、残りが 1 つずつに決まったから）。

人 $1$ は $a$ だけ、人 $2$ も $a$ だけ、人 $3$ は $a$、$b$、$c$ のどれでもできるとする。
人 $1$ と人 $2$ はどちらも $a$ しかできないので、2 人に互いに違う仕事を割り当てることはできない。人 $3$ にどれほど選択肢があっても、全員の割り当ては作れない。2 人 $\{1,2\}$ のできる仕事を合わせても $\{a\}$ の 1 つしかなく、人数 $2$ より少ないことが原因である（図 2）。

ex-mar-start の 2 部グラフ（$A=\{1,2,3\}$、$B=\{a,b,c\}$）で、空でない部分集合 $S$ は $2^3-1=7$ 個ある。

どの行でも $\lvert N(S)\rvert\ge\lvert S\rvert$ である。ex-mar-fail の 2 部グラフでは、$S=\{1,2\}$ で $N(S)=\{a\}$、$\lvert N(S)\rvert=1<2=\lvert S\rvert$ となる。

1. 場合 1 の例．$A=\{1,2,3\}$、$B=\{a,b,c\}$ で、$1$ は $a,b$、$2$ は $b,c$、$3$ は $c,a$ と隣り合うとする。1 点の $S$ では $\lvert N(S)\rvert=2=\lvert S\rvert+1$、2 点の $S$ では $N(S)=\{a,b,c\}$ で $\lvert N(S)\rvert=3=\lvert S\rvert+1$ なので、場合 1 にあたる。lem-mar-remove の組として人 $1$ と仕事 $a$ をとり、この 2 頂点を取り除くと、残りは $2$ が $b,c$、$3$ が $c$ と隣り合うグラフで、$\lvert N(\{2\})\rvert=2$、$\lvert N(\{3\})\rvert=1$、$\lvert N(\{2,3\})\rvert=2$ となり、Hall の条件を満たす（lem-mar-remove）。
2. 場合 2 の例．$A=\{1,2,3,4\}$、$B=\{a,b,c,d\}$ で、$1$ と $2$ は $a,b$、$3$ は $b,c,d$、$4$ は $c,d$ と隣り合うとする（図 3）。$S_0=\{1,2\}$ では $N(S_0)=\{a,b\}$ で等号である。$G_1$ は $1,2$ と $a,b$ のグラフ、$G_2$ は $3,4$ と $c,d$ のグラフで、辺 $3b$ は $G_2$ に入らない。$G_2$ では $N_2(\{3\})=\{c,d\}$、$N_2(\{4\})=\{c,d\}$、$N_2(\{3,4\})=\{c,d\}$ で、Hall の条件を満たす（lem-mar-split）。

ex-mar-lemmas (2) のグラフで、証明の手順を追う。場合 2 の $S_0=\{1,2\}$ で分ける。
$G_1$（$1,2$ と $a,b$）では、$\{1\}$ も $\{2\}$ も $N=\{a,b\}$ で余裕が $1$ あり、場合 1 にあたる。$1\to a$ と決めて取り除くと、$2$ には $b$ が残り $2\to b$。
$G_2$（$3,4$ と $c,d$）でも同じく $3\to c$、$4\to d$ と決まる。
合わせて $1\to a$、$2\to b$、$3\to c$、$4\to d$ で、図 3 の赤い 4 本の辺である。このグラフの $A$ 全体の割り当ては、$1,2$ に $a,b$ を、$3,4$ に $c,d$ を配る $2\times2=4$ 通りある。$3\to b$ とすると、$1$ と $2$ に残る仕事が $a$ だけになり割り当てられない。一般に、場合 2 では $S_0$ の $\lvert S_0\rvert$ 人が $N(S_0)$ の $\lvert S_0\rvert$ 個の仕事を互いに違うように使うので、どの割り当てでも $N(S_0)$ はすべて $S_0$ の人に使われ、残りの人は $B\setminus N(S_0)$ から選ぶしかない。2 つに分けても、割り当てを見落とさない。

1. 小さな場合．数字 $1,1,2,2,3,3$ の 6 枚のカードを、2 枚ずつ 3 つの山 $\{1,1\}$、$\{2,3\}$、$\{2,3\}$ に分ける。$A$ を 3 つの山、$B$ を 3 つの数字とし、カード 1 枚ごとに「そのカードの山」と「そのカードの数字」を辺で結ぶ。山 1 と数字 $1$ は 2 本の辺で結ばれる。どの山からも 2 本（山の枚数）、どの数字からも 2 本（その数字の枚数）の辺が出ているので、cor-mar-regular が使える（$k=2$）。実際、山 1 から $1$、山 2 から $2$、山 3 から $3$ を選べば、3 つの数字が 1 枚ずつそろう（山 2 から $3$、山 3 から $2$ を選んでもよい）。
2. トランプ 52 枚．よく切った 52 枚を 4 枚ずつ 13 の山に分ける。$A$ を 13 の山、$B$ を 13 の数字 A, 2, …, 10, J, Q, K とし、カード 1 枚ごとに山と数字を辺で結ぶ。どの山からも 4 本、どの数字からも 4 本（4 つのマーク）の辺が出るので、$k=4$ で cor-mar-regular が使える。山と数字の 1 対 1 の対応 $f$ があり、各山から数字 $f(\text{山})$ のカードを 1 枚ずつ選ぶと、A から K までの 13 の数字が 1 枚ずつそろう。どう分けても、このように選べる。

ex-mar-fail のグラフ（$1$ は $a$、$2$ は $a$、$3$ は $a,b,c$）では、1 点の $S$ について $\lvert N(\{1\})\rvert=\lvert N(\{2\})\rvert=1$、$\lvert N(\{3\})\rvert=3$ で、どれも $\lvert S\rvert=1$ 以上である。全体 $S=A$ でも $N(A)=\{a,b,c\}$ で $3\ge3$ である。それでも $S=\{1,2\}$ で $\lvert N(S)\rvert=1<2$ となり、割り当てはない。「全員が何かの仕事をできる」ことと「仕事の総数が人数以上」であることだけでは足りず、途中の大きさの $S$ も確かめる必要がある。

$A=\{a_0,a_1,a_2,\dots\}$、$B=\{b_1,b_2,\dots\}$ とし、$a_0$ はすべての $b_i$ と、$a_i$（$i\ge1$）は $b_i$ だけと隣り合うとする（図 5）。
$A$ の有限部分集合 $S$ はどれも $\lvert N(S)\rvert\ge\lvert S\rvert$ を満たす。$a_0\notin S$ なら $N(S)=\{b_i\mid a_i\in S\}$ で、$\lvert N(S)\rvert=\lvert S\rvert$ である。$a_0\in S$ なら $N(S)$ は $B$ 全体で、無限個の要素をもつ。$S$ が無限集合のときも、$S$ に入る $a_i$（$i\ge1$）ごとに $b_i$ が $N(S)$ に入るか、$a_0\in S$ で $N(S)=B$ となるので、$N(S)$ は無限集合である。したがって、$S$ の頂点に比べて $N(S)$ の頂点が足りない、ということはどの $S$ でも起こらない。
しかし $A$ 全体の割り当て $f$ はない。$f(a_0)=b_j$ とすると、$a_j$ と隣り合うのは $b_j$ だけなので $f(a_j)=b_j=f(a_0)$ となり、単射にならない。thm-mar-hall の証明の帰納法は $A$ の要素の個数についてのもので、$A$ が有限でないと使えない。

$A=\{1,2,3\}$、$B=\{a,b,c\}$ で、$1$、$2$、$3$ がどれも $a$ と $b$ の 2 つと隣り合うとする（図 4）。$A$ のどの頂点からも 2 本の辺が出ているが、$B$ の側は $a$ から 3 本、$b$ から 3 本、$c$ から 0 本で、そろっていない。$S=A$ で $N(A)=\{a,b\}$、$\lvert N(A)\rvert=2<3$ なので、割り当てはない。cor-mar-regular の証明の段 2 で「$N(S)$ の頂点から出る辺は $k\lvert N(S)\rvert$ 本」を使ったが、ここでは $N(A)$ の頂点から出る辺は $6$ 本で、$2\lvert N(A)\rvert=4$ 本ではない。

ex-mar-fail のグラフでは、$S=\{1,2\}$ で $\lvert S\rvert-\lvert N(S)\rvert=2-1=1$、ほかの $S$ ではこの値は $0$ 以下なので $\delta=1$ で、最大 $3-1=2$ 人を割り当てられる。実際、$1\to a$、$3\to b$ で 2 人を割り当てられ、$1$ と $2$ のどちらかは必ず余る。