ホールの定理
例 1: S = {S1, S2, S3} があり、それぞれは以下の通り。
S1 = {1, 2, 3}
S2 = {1, 4, 5}
S3 = {3, 5}
妥当なSDRは {1, 4, 5} である(ただし、これは唯一のSDRではない。例えば {2, 1, 3} でもよい)。
例 2: S = {S1, S2, S3, S4} があり、それぞれは以下の通り。
S1 = {2, 3, 4, 5}
S2 = {4, 5}
S3 = {5}
S4 = {4}
妥当なSDRは存在しない。また、部分集合 {S2, S3, S4} について結婚条件が成り立たない。
結婚定理の一般的応用例は、n人の男性とn人の女性という2つのグループを想定する。それぞれの女性は男性の部分集合のいずれかと結婚できれば幸せである(結婚してもよいと思う男性が何人かいる)。また、それぞれの男性は自分と結婚したい(してもよい)と思っている女性と結婚できれば幸せである。ここで、全員が幸せになるような組合せ(結婚)は可能か、という問題である(男女を入れ替えた設定でもよい)。
ここで Si を i番目の女性が結婚して幸せになれる男性の集合とする。結婚定理によれば、それぞれの女性が男性と幸せな結婚をできることと、集合の集まり {S1, S2, ...} が結婚条件を満たすことは同値である。