Graph Matching

Hall’s Theorem

Hall’s Theorem, Theorem 8.4.1

A bipartite graph $G$ with bipartition $(A,B)$ has a matching saturating every vertex in $A$ if and only if every subset $D\subseteq A$ satisfies $|N(D)|\ge |D|$. (This is called “Hall’s condition”.)