ようやく本題に入ります。次のステートメントの内容を証明します。定理5(Hallの結婚定理) をとる。とし、を仮定し、がHall条件を満たすならば (証明) に関する帰納法で示す。のときは自明。のとき、次の二つの場合に分けて考える。 (1)臨界ブロックがない場…

この記事ではHallの結婚定理の証明のうち、個別代表系(SDR)というものを用いた証明を扱います。まず、Hallの結婚定理のステートメントを確認します。Hallの結婚定理 を部集合とする二部グラフGにおいて、からへの完全マッチングが存在するための必要十分条件…