= Solution
A matching from $X$ to $Y$ consists of disjoint edges saturating every vertex of $X$. The criterion is <Hall marriage theorem>.
For sufficiency, induct on $|X|$. If a nonempty proper $S\subset X$ is tight, $|N(S)|=|S|$, apply induction to $S,N(S)$ and to the graph left after deleting them. If no proper set is tight, choose any edge $xy$, delete its endpoints, and Hall still holds because every nonempty proper subset formerly had at least one spare neighbour. Induction completes the matching. Necessity is immediate.
Back to article page
