Let $G = (A,B)$ be a bipartite graph. Hall's theorem implies that $G$ has a perfect matching if and only if $|A| = |B|$ and for each $X \subseteq A$, $|X| \leq |\Gamma(X)|$, where $\Gamma(X)$ is the neighborhood of $X$ in $B$.
Posted: Aug 12 '12
Seen: 70 times
Last updated: Aug 13 '12
