قضیه هال: اگر یک گراف دو بخشی با بخش های $X,Y$ باشد، آنگاه گراف $G$ دارای تطابقی است که همه رئوس $X$ را بپوشاند $ \Leftrightarrow $ شرط هال برقرار باشد($ \forall S \subseteq X; |N(S)| \geq |S|$).
برهان:
لزوم شرط)
اگر $M$ تطابق باشد که همه رئوس $X$ را بپوشاند، آنگاه برای هر $ \ S \subseteq X$ باید حداقل به اندازه تعداد اعضای $S$ در $Y$ همسایه وجود داشته باشد. به عبارتی دیگر:
$$ \forall S \subseteq X;|N(S)| \geq |S| $$
کفایت شرط) برهان خلف
فرض کنید برای هر $ S \subseteq X $ و $ |N(S)| \geq |S| $ ولی $G$ شامل تطابقی که همه رئوس $X$ را بپوشاند، نباشد.
تطابق $M$ را یک تطابق ماکسیمم در $G$ در نظر میگیریم.
طبق فرض خلف $M$ همه رئوس $X$ را نمی پوشاند. در نتیجه راس $x_0 \in X$ وجود دارد که $M$-ناآلوده است.
مجموعه $Z$ را مجموعه رئوسی در نظر میگیریم که با مسیرهای $M$-متناوب به $x_0 $ در ارتباط اند و قرار می دهیم:
$$ Z \cap X=S , Z \cap Y=T , Z=S \cup T $$
ادعا: $M$ یک تطابق کامل از $T$ به $S- {x_0}$ است و $T=N(S)$
رئوس در $T$ با یال هایی که در $M$ نیست و رئوس $S$ با یال های $M$ به $x_0 $ متصل می شوند.
تطابق $M$ ماکسیمم است $ \Leftarrow $ مسیر $M$-افزوده وجود ندارد. $\Leftarrow$ هر راس در $T$، $M$-آلوده است. پس$T \subseteq N(S) $
عضو دلخواه
$y \in N(S) $ $\Leftarrow$ یک مسیر متناوب از $x_0 $ به $y$ وجود دارد. $\Leftarrow$ $y \in T$. پس $T \supseteq N(S) $.
در نتیجه:
$$|T|=|N(S)|=|S-{x_0}| =|S|-1<|S| $$
عبارت بالا با فرض قضیه در تناقض است. پس: تطابق ماکزیمم در گراف $G$ وجود دارد که رئوس $X$ را میپوشاند.
نتیجه قضیه هال: هر گراف دوبخشی $k$-منتظم($k>0 $) دارای تطابق کامل است.
فرض کنید $G$ یک گراف $k$-منتظم دوبخشی با بخش های $X,Y$ باشد.
$ |E(G)|=k|X| , |E(G)|=k|Y| \Rightarrow |X|=|Y|$
هر تطابق که رئوس $X$ را آلوده کند $\Leftarrow$ همه رئوس $Y$ را آلوده می کند. $\Leftarrow$ تطابق کامل است.
حال کافی است ثابت کنیم گراف $G$ در شرط هال صدق می کند.
$$S \subseteq X \Rightarrow $$
$N(S)$تعداد یال های خارج شده از $S$ به =$k|S|$
$N(S)$تعداد یال های خارج شده از =$k|N(S)|$
چون تعداد یال های خارج شده از $N(S)$ ناکمتر از سال های خارج شده از $S$ به $N(S)$ است، پس $ |N(S)| \geq |S|$ و شرط هال برقرار است.
