Perfect Matching

A perfect matching pairs every vertex in the smaller set. If $|L| = 5$ and $|R| = 10$, a perfect matching would pair all $5$ left vertices.

Perfect matching exists if and only if max matching size equals $\min(|L|, |R|)$. If matching size is smaller, some vertices remain unmatched.

Hall's theorem gives a condition: perfect matching exists iff for every subset $S$ of $L$, the neighborhood $N(S)$ has at least $|S|$ vertices. This is useful for proving existence without computing the matching.