ホールの結婚定理

女性グループと男性グループのマッチングを考えます。女性は「カップルになってもいい」と思う男性を1人以上選んでおきます。女性全員についてカップルが成立する条件は？

グラフで表すと、このような二部グラフになります。（グラフ理論でいうグラフは、点の集合と辺の集合で表されます。二部グラフは、頂点が2つの集合に分かれて、辺が2つの集合間に引かれているグラフです）

この例の場合、次のようなマッチングがあり得ます。（マッチング：１つの頂点からの辺は1本だけ）緑の辺が、マッチングペアです。

二部グラフのA側のすべての点が、B側のどこかの点とペアになっているような状態のことをAからBへの完全マッチングと呼びます。

次の例では、点２，点３のどちらかにマッチングペアがないので、完全マッチングではありません。

上の完全マッチングではない例では、\(S=\{2,3\}\)の場合、\(N(S)=\{b\}\)なので、不等式は成立していません。

ホールの結婚定理の証明

必要性の証明
（完全マッチングが存在するなら、\(A\)の任意の部分集合\(S\)に対して\(|S| \leq |N(S)|\) が成立する）
対偶を示します。
\(A\)のある部分集合\(T\)に対して、\(|T| \gt |N(T)|\)が成立するなら、マッチングペアのない\(T\)の頂点が存在することになり、完全マッチングではなくなります。

十分性の証明
（\(A\)の任意の部分集合\(S\)に対して\(|S| \leq |N(S)|\) が成立するなら、\(A\)から\(B\)への完全マッチングが存在する）
\(|A|\)に関する帰納法で証明します。\(|A|=1\)のときは自明。

\(|A| \leq k\)のときに、ホールの結婚定理が成立すると仮定します。\(|A|=k+1\)で、条件を満たすグラフ\(G\)を考えます。

・\(A\)の任意の部分集合\(X\)に対して、\(|X|+1 \leq |N(X)|\)となる場合
辺を1本選び、それぞれの頂点を除いた二部グラフ\(G'(A’,B’)\)を考えます。\(G’\)は条件を満たしているので、完全マッチングが存在します。このマッチングに、最初に省いた辺を加えると、\(G\)に完全マッチングが存在することになります。

・\(|X|=|N(X)|\)となる部分集合\(X\)が存在する場合
帰納法の仮定により、\(X\)と\(N(X)\)の間の完全マッチングが存在するので、残ったグラフ\(G'(A’,B’)\)について、完全マッチングが存在することを証明します。

\(A’\)の部分集合\(Y\)を考えます。\(G\)は条件を満たしているので、
\(|Y| \gt|N(Y)| \)だとしたら、\(|X|=|N(X)|\)より、\(|X \cup Y|\gt |N(X \cup Y)|\)となり矛盾。

すなわち、\(|Y| \leq|N(Y)| \)となり、\(G’\)も条件を満たすので、完全マッチングが存在します。