Zbiór różnych reprezentantów

Niech będzie dany zbiór $X$ i pewna rodzina podzbiorów $\cal{X}$ tego zbioru. Kiedy istnieje zbiór $Y \subset X$ taki, że istnieje różnowartościowa funkcja $g: \cal{X}$$\rightarrow Y$? Jeśli taki zbiór $Y$ istnieje, nazywamy go zbiorem różnych reprezentantów rodziny $\cal{X}$.

Przykład 8.3   W sejmie, senacie^8.9 istnieją różne komisje zajmujące się różnymi problemami^8.10 Komisje te kędziemy traktowali jako podzbioru zbioru posłów (lub senatorów). Każda komisja ma swojego przewodniczącego. Wygodnie jest by przewodniczącymi róznych komisji były różne osoby. Powstaje więc problem: jak powinny być dobrane komisje by mogło tak być?

Problem istnienia zbioru różnych reprezentantów można przetłumaczyć na język teorii grafów następująco:
Niech każdemu zbiorowi $X_i \in {\cal X}$ odpowiada wierzchołek $x_i$ i niech $A=\{ x_i: X_i \in \cal{X}\}$, oraz $B=X$. Niech teraz $G$ bedzie grafem dwudzielnym $G=(A,B;E)$ takim, że $E=\{x_ix: x \in X_i\}$. Problem istnienia zbioru różnych reprezentantów rodziny $\cal{X}$ jest równoważny istnieniu w $G$ skojarzenia pełnego zbioru $A$. Stąd i z twierdzenia wynika bardzo łatwo następujący wniosek.

Wniosek 8.2 (Hall)   [10]