A $G(A, B, E)$ páros gráfban akkor és csak akkor létezik teljes párosítás, ha
$ \mid A \mid = \mid B \mid$ és
$ \mid X \mid \leq \mid N(X) \mid $ minden $X \subseteq A $ ponthalmazra.
Frobenius tétele arról szól, hogy mikor létezik egy gráfban teljes párosítás.
1.
a) Egy bálon 10 fiú és 10 lány vesz részt. Minden lány legalább 6 fiút ismer és minden fiú is legalább 6 lányt. Az ismertségek kölcsönösek. A nyitótáncon mindenki ismerőssel szeretne táncolni. Bizonyítsuk be, hogy ez lehetséges.
b) Egy 12 csúcsú páros gráfban minden csúcs foka 3 vagy 4. Bizonyítsuk be, hogy van a gráfban teljes párosítás.
