Hall’s Marriage Theorem

Description:

• The bipartite graph 𝐺 = (𝑉, 𝐸) with bipartition $(V_1,V_2)$ has a complete matching from $V_1$ to $V_2$ if and only if $|N(A)|\ge |A|$ for all subsets of $A$ of $V_1$.theorem
  • Any subset of $V_1$ must have more matchable nodes then the number of nodes in $V_1$
• Proof: lecture 14, slide 16