Barion Pixel Hall tétel | mateking
 

Hall tétel

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.