= Solution
A matching from $X$ to $Y$ is a set of pairwise vertex-disjoint edges that covers every vertex of $X$. Equivalently, it chooses for each $x\in X$ a distinct neighbour in $Y$.
<Hall marriage theorem> says that such a matching exists if and only if
$$
|N(S)|\geq |S|\qquad\text{for every }S\subseteq X.
$$
Necessity is immediate: the distinct partners of the vertices in $S$ all belong to $N(S)$.
For sufficiency, induct on $|X|$. The claim is clear when $|X|=1$. First suppose every nonempty proper $S\subset X$ satisfies the strict inequality $|N(S)|\geq |S|+1$. Choose an edge $xy$ and delete $x$ and $y$. For $S\subseteq X\setminus\{x\}$, deletion removes at most one neighbour, so
$$
|N_{G-\{x,y\}}(S)|\geq |N_G(S)|-1\geq |S|.
$$
Induction gives a matching of $X\setminus\{x\}$, and adding $xy$ completes it.
Otherwise there is a nonempty proper $S\subset X$ with $|N(S)|=|S|$. Hall's condition holds in the bipartite graph induced by $S\cup N(S)$, so induction matches $S$ onto $N(S)$. For $A\subseteq X\setminus S$,
$$
|N(A\cup S)|\geq |A|+|S|,
$$
and hence $A$ has at least $|A|$ neighbours outside $N(S)$. Induction therefore matches $X\setminus S$ into $Y\setminus N(S)$. The two matchings are disjoint and together cover $X$.
Back to article page
