= Solution
<Hall's marriage theorem> states that a finite <bipartite graph> with parts $A,B$ has a <matching in a graph> saturating $A$ exactly when $|N(S)|\geq|S|$ for every $S\subseteq A$. Necessity follows because the matched neighbours of $S$ are distinct.
For sufficiency use induction on $|A|$. The empty case is immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, the induced graph on $S,N(S)$ satisfies Hall's condition and has a saturating <matching in a graph> by induction. The remaining graph on $A\setminus S,B\setminus N(S)$ also satisfies it: for $T\subseteq A\setminus S$,
$$
|N(T)\setminus N(S)|=|N(T\cup S)|-|N(S)|\geq|T|.
$$
Apply induction again and unite the two <matchings in a graph>. If there is no such tight proper subset, every nonempty proper $S$ has $|N(S)|\geq|S|+1$. Choose a vertex $a$ and a neighbour $b$, which exists by Hall's condition. Delete both. Every remaining subset loses at most one neighbour and still satisfies Hall's condition. Induction supplies a <matching in a graph> of the remainder; add $ab$. For $|A|=1$ this last step directly proves the assertion.
Back to article page
