= Solution
Represent the two sides of the marriage problem as the parts $L,R$ of a <bipartite graph>, with an <edge> for each allowed pairing. A <matching> is a set of edges with no common endpoint; a complete <matching> of $L$ covers every <vertex> in $L$. When the two parts have equal size it also covers $R$, giving a <perfect matching>.
<Hall's marriage theorem> gives the exact finite-<graph> criterion:
$$
\boxed{|N(S)|\geq|S|\quad\text{for every }S\subseteq L.}
$$
Here $N(S)$ is the set of right-side neighbours of $S$. Necessity follows because distinct matched vertices of $S$ need distinct neighbours; Hall's theorem supplies sufficiency.
Back to article page
