Legyen $G(A,B,E)$ páros gráf és $X$ pedig $A$-nak egy tetszőleges részhalmaza. Az $X$-ben lévő csúcsok $B$-beli szomszédjainak halmazát hívjuk $N(X)$-nek. A $G$ gráfnak akkor és csak akkor van $A$-t fedő párosítása, ha bármely $X$ halmazra
\( \mid X \mid \leq \mid N(X) \mid \)
Hall tétele arról szól, hogy egy $G(A,B,E)$ páros gráfban mikor létezik $A$-t fedő párosítás.
a) Egy bárban 60 lány van. Minden lány 12 fiút ismer és minden fiú 15 lányt ismer. Az ismertségek kölcsönösek. Hány fiú van a bárban? Tudunk-e úgy fiú-lány párokat alkotni, hogy minden fiút egy ismerős lánnyal párosítunk?
b) Egy kiránduláson fényképet készítenek a résztvevőkről. Minden képen 4-en szerepelnek, és tudjuk, hogy mindenkiről legalább 4 kép készült. A kirándulás végén mindenki választhat egy képet. Igazoljuk, hogy biztosan mindenkinek jutni fog olyan kép, amin rajta van.
