ホールの結婚定理

ペアマッチングに関する定理。

N人の女性とM人の男性がいる。
それぞれ幸せに結婚できるペアが複数ある。

N人すべての女性が幸せな結婚をするには、
N人のうち任意のK人を選んだとき、
そのペアになりうる男性がK人以上いれば条件を達成する。

この定理は女性が幸せになる条件であり、男性はその限りでない。
また、すべてマッチングしない場合のマッチング数を求めることはできない。