Hall's theorem

cosmos 15th October 2017 at 7:02pm

Let BB be a Bipartite graph with vertex classes VV and WW. There is a Complete matching from V to W if and only if for any subset S of V. The size of the neighbourhood of S Γ(S)\Gamma(S):

Γ(S)S|\Gamma(S)| \geq |S|

The "only if" part is clear because a complete matching is like an Injective function. The nontrivial part is that the condition is also necessary.