Hall定理(霍爾定理)證明及推廣
引言
網路上有許多Hall定理的證明，但是對於Hall定理的幾個推廣的介紹卻少之又少，因此本文來簡單介紹一下
注：為了使這篇文章看起來簡單易懂，本文將不會使用圖論語言，會圖論的朋友們可以自行翻譯為圖論語言。
背景：
在遙遠的地方有一個神奇國家，這個國家有n個男生和m個女生（n m）。每個男生都喜歡著若干個女生(注：這個國家不存在基佬，即男生不能喜歡男生)，現在男生們希望每位男生都可以找到一位自己喜歡的女生作為女朋友（注：不能與他人共用女朋友）。
1. 霍爾定理
霍爾定理聲稱每位男生都可以找到一位自己喜歡的女生作為女朋友當且僅當從這n個男生中任取若干個男生（不妨為k個）都有 至少被他們中1個男生喜歡的女生數量大於等於k人。
霍爾定理證明：
1）必要性：必要性是顯然的：如果k個男生喜歡的女生總共只有小於等於k-1個，那麼顯然一定至少有一個可憐鬼找不到女朋友
2）充分性：下對男生個數n歸納證明霍爾定理的充分性成立。
n=1時顯然成立，若小於n時均成立，n時：
如果任取若干個男生（不妨為k個（k不等於n））都有 至少被他們中1個男生喜歡的女生數量大於等於k+1人
那麼我們將隨便一個男生與一個他喜歡的女生組為男女朋友，之後將他們去掉。不難發現剩下的人依舊滿足霍爾定理的條件但此時男生只剩下n-1個，由歸納假設知：成立
如果存在若干個男生（不妨為k個（k不等於n））滿足至少被他們中1個男生喜歡的女生數量恰好為k人
那麼由歸納假設知：這k個男生與k個女生可以組為k對男女朋友，將這k對男女朋友去掉。不難發現剩下的人依然滿足霍爾定理條件（如果有若干的男生不滿足，那麼這些男生與去掉的那k個男生在初始時就不滿足條件），由歸納假設知：成立。
綜上，n時成立，所以霍爾定理的充分性成立。
證畢。
2. 霍爾定理-加強1
然而現實是殘酷的，不可能每個人都能找到屬於自己的女朋友，因此男生們希望最多有a（a<n）個人找不到自己的女朋友，那麼此時的充要條件又是什麼呢？
霍爾定理-加強1 聲稱：最多可以有a個男生找不到自己的女朋友當且僅當從這n個男生中任取若干個男生（不妨為k個）都有 至少被他們中1個男生喜歡的女生數量大於等於k-a人。
霍爾定理-加強1 證明：
1）必要性：必要性依舊是顯然的，如果k個男生喜歡的女生總共只有小於等於k-a-1個，那麼顯然一定至少有a+1個可憐鬼找不到女朋友
2）充分性：充分性的證明與霍爾定理充分性的證明基本相同，還是對男生個數n歸納證明。
n=a,a+1時顯然成立，若小於n時均成立，n時：
如果任取若干個男生（不妨為k個（k不等於n））都有 至少被他們中1個男生喜歡的女生數量大於等於k-a+1人
那麼我們將隨便一個男生與一個他喜歡的女生組為男女朋友，之後將他們去掉。不難發現剩下的人依舊滿足霍爾定理-加強1的條件但此時男生只剩下n-1個，由歸納假設知：成立
如果存在若干個男生（不妨為k個（k不等於n））滿足至少被他們中1個男生喜歡的女生數量恰好為k-a人
那麼由歸納假設知：這k個男生與k-a個女生可以組為k-a對男女朋友（有a個可憐鬼找不到女朋友），將這k個男生與k-a個女生去掉。不難發現剩下的人滿足霍爾定理條件（注意是霍爾定理不是霍爾定理-加強1）（如果有若干的男生不滿足，那麼這些男生與去掉的那k個男生在初始時就不滿足條件），由霍爾定理知：成立。
綜上，n時成立，所以霍爾定理-加強1的充分性成立。
3. 霍爾定理-加強2
為了更加深入了了解這個國家（大霧） 我們穿越到了古代，在古代這個國家還是有n個男生與m個女生，只不過這時候男生們的標配不再是1個女朋友了，他們需要1位妻子與4位元小妾（大大霧） ，男生們希望每位男生都可以找到五位自己喜歡的女生作為女朋友（注：不能與他人共用女朋友）。那麼此時的等價條件又是什麼呢？
霍爾定理-加強2聲稱：每位男生都可以找到五位自己喜歡的女生作為女朋友當且僅當從這n個男生中任取若干個男生（不妨為k個）都有 至少被他們中1個男生喜歡的女生數量大於等於5*k人。
霍爾定理-加強2 證明：
眾所周知，數學家喜歡把未知的問題化歸為已知的問題，那麼這個問題該怎麼化歸呢？
很顯然我們需要穿越回近代來考慮這個問題。在近代找1位妻子與4位元小妾是犯法的，因此這些男生被五馬分屍了（太可憐了），每一位男生都被分為了5塊（太太可憐了），每個男生的5塊屍首分別被他的5個女朋友儲存著。誒？等等，你發現了什麼？這不就是霍爾定理嗎？只不過從男生找女朋友變為了男生的屍首找女朋友（屍首還能找女朋友？？？），在古代每個男生能找到5位女朋友等價於在近代他的每個屍首都能找到1位女朋友（害怕）因此由霍爾定理他的等價條件就是從5n個屍首中任取若干個（不妨為k個） 都有：至少被他們中1個屍首的主人喜歡的女生數量大於等於k個，而顯然的這等價於從這n個男生中任取若干個男生（不妨為k個）都有 至少被他們中1個男生喜歡的女生數量大於等於5*k人。於是霍爾定理-加強2就被我們證完了（神奇吧！）
霍爾定理-加強2 推廣：
在古代也是有階級之分的，每個人的需求也是不同的，如果第i個男生希望找r(i)個女朋友那麼此時的等價條件又是什麼呢？
很容易猜到第i位男生都可以找到r(i)位自己喜歡的女生作為女朋友當且僅當從這n個男生中任取若干個男生（不妨為k個）都有 至少被他們中1個男生喜歡的女生數量大於等於S人，其中S為這k個男生的r(i)之和。