霍尔定理:此定理使用于组合问题中;二部图G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4, .........,Xm} , Y={y1, y2, y3, y4 , .........,yn},G中有一组无公共点的边,一端恰好为组成X的点的充分必要条件是:X中的任意k个点至少与Y中的k个点相邻。(1≤k≤m)本论还有一个重要推论: 二部图G中的两部分顶点组成的集合分别为X,Y, 若∣X∣=∣Y∣,且G中有一组无公共端点的边,一端恰好组成X中的点,一端恰好组成Y中的点,则称二部图G中存在完美匹配。若图G的每个点度数为t,则称二部图G为t---正则的二部图存在完美匹配。本定理是二分图匹配问题中匈牙利算法的基础。