女性グループと男性グループのマッチングを考えます。女性は「カップルになってもいい」と思う男性を1人以上選んでおきます。女性全員についてカップルが成立する条件は?
グラフで表すと、このような二部グラフになります。(グラフ理論でいうグラフは、点の集合と辺の集合で表されます。二部グラフは、頂点が2つの集合に分かれて、辺が2つの集合間に引かれているグラフです)
この例の場合、次のようなマッチングがあり得ます。(マッチング:1つの頂点からの辺は1本だけ)緑の辺が、マッチングペアです。
二部グラフのA側のすべての点が、B側のどこかの点とペアになっているような状態のことをAからBへの完全マッチングと呼びます。
次の例では、点2,点3のどちらかにマッチングペアがないので、完全マッチングではありません。
上の完全マッチングではない例では、\(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’\)も条件を満たすので、完全マッチングが存在します。