Hallの結婚定理とその証明

対偶を示す。条件2が成立しないとき，ある $U$ の部分集合 $A$ が存在して，$|A| > |\Gamma(A)|$ となる。

よって，$A$ をカバーするようなマッチングは存在せず，条件1は成り立たない。

$|U|$ に関する帰納法で証明する。 $|U|=1$ のときは自明。

$|U|\leq k$ のときにHallの結婚定理が成立すると仮定する。 $|U|=k+1$ でありHallの条件を満たすグラフ $G$ でを考える。以下二通りに場合分け。

・ $U$ の任意の真部分集合 $A$ に対して $|A|+1\leq |\Gamma(A)|$ となる場合。

このときは余裕があるので，適当に辺 $(u,v)$ を一本選べばよい。そして，頂点 $u$ と $v$ を除いた二部グラフ $G'(U',V')$ を考えると，$G'$ においてもHallの条件を満たしている。よって，帰納法の仮定により $U'$ をカバーするマッチング $M$ が存在する。全体のマッチングとして $M$ と $(u,v)$ の和集合を持ってくればよい。

・ $|A|=|\Gamma(A)|$ を満たす $U$ の真部分集合 $A$ が存在する場合。

「 $A$ と $\Gamma(A)$ から構成される二部グラフ」がHallの条件を満たしていることと，帰納法の仮定により，頂点 $A$ をカバーするマッチング $M_1$ が存在する。そして，そのマッチングは $A$ と $\Gamma(A)$ の間の完全マッチング（全頂点をカバーするマッチング）である。

よって，残ったグラフ $G'(U',V')$ に $U'$ をカバーするマッチング $M_2$ が存在することを証明すればよい。

ここで，$U'$ の部分集合 $B$ を考えてみると，$G$ がHallの条件を満たしていることから $|A\cup B|\leq |\Gamma(A\cup B)|$ である。よって，$A\cup B$ の行き先で $\Gamma(A)$ に属さないものが少なくとも $|B|$ 個は存在する。それらは $A$ とはつながっていないので，全て $B$ とつながっている。すなわち，$|\Gamma (B)|\geq |B|$ 。よって． $G'$ もHallの条件を満たすので帰納法の仮定により $U'$ をカバーするマッチング $M_2$ が存在する。