ホールの定理
まず、2部グラフ G = (X + Y, E ) = G(X, Y ) が X-飽和マッチング(X の全ての頂点を飽和するようなマッチング)を持つならば、任意のW ⊆ X に対して|NG(W )| ≥ |W |であることを示す。
MをX-飽和マッチングとする。 このとき、Mによって、与えられたW ⊆ X とマッチングされているY の頂点集合をM(W )と書くと、マッチングの定義より|M(W )|=|W |。 しかし、M(W )の全ての元はW の近傍に属するので、M(W ) ⊆ NG(W )である。 よって、 |NG(W )| ≥ |M(W )| であるから、|NG(W)| ≥ |W |。
次に、任意のW ⊆ X に対して|NG(W)| ≥ |W | ならば、G(X,Y)はX-飽和マッチングを持つことを示す。
2部グラフG(X,Y)がX-飽和マッチングを持たないと仮定して矛盾を導く。 M をGの最大マッチングすると、M-非飽和点が存在するので、これをu ∈ X とする。 u を始点とする任意のM-交互道を考え、この交互道によってuと接続するすべてのY の頂点の集合をT とする。