ホールの定理
結婚定理はグラフ理論にも応用される。グラフ理論の用語で問題を表すと次のようになる。
有限な2部グラフ G:= (X + Y, E) で X と Y が同じ大きさとしたとき、マッチングは存在するか? すなわち、G の各頂点が必ず1つの辺と接合するような辺の集合は存在するか?
結婚定理がこの問題の答えを与える。
G の頂点の集合 W について、G における W の近傍を N G ( W ) {\displaystyle N_{G}(W)} で表す。近傍とは、W の何らかの元に隣接する全頂点の集合である。グラフ理論における結婚定理(ホールの定理)によれば、完全マッチングが存在することと X のあらゆる部分集合 W について次が成り立つことは同値である。
| W | ≤ | N G ( W ) | {\displaystyle |W|\leq |N_{G}(W)|}
言い換えれば、X のあらゆる部分集合 W は Y に属する頂点と十分に隣接している。
任意のグラフに一般化したものがタットの定理である。
S = {S1, S2, ... } が有限集合の集まりとする(可算である必要はない)。Sの横断集合 (transversal) または S の完全代表系 (system of distinct representatives; SDR) とは、別個の元からなる集合 X = {x1, x2, ...}(ここで |X| = |S|)で、全ての i について xi∈Si となっている集合である。
Sの結婚条件 (marriage condition) とは、Sの任意の部分集合 T ⊆ S {\displaystyle T\subseteq S} についての次の条件である。
| T | ≤ | ⋃ A ∈ T A | {\displaystyle |T|\leq {\Bigl |}\bigcup _{A\in T}A{\Bigr |}}
ここで、|T| は集合 Tの元の数を意味する。
ホールの定理は、SDR X が存在することと、S が結婚条件を満たすことは同値であるというものである。