= Solution
A <matching in a graph> from $X$ to $Y$ chooses one distinct neighbour in $Y$ for each vertex of $X$. For a finite <bipartite graph>, the <Hall marriage theorem> states that such a matching exists if and only if $|\Gamma(A)|\geq|A|$ for every $A\subseteq X$. Necessity follows because the matched neighbours of $A$ are distinct members of $\Gamma(A)$.
For sufficiency use induction on $|X|$, with the empty and one-vertex cases immediate. If some nonempty proper $A$ satisfies $|\Gamma(A)|=|A|$, the induced graph on $A,\Gamma(A)$ satisfies Hall's condition. The remaining graph on $X\setminus A,Y\setminus\Gamma(A)$ does too: for $B\subseteq X\setminus A$,
$$
|\Gamma(B)\setminus\Gamma(A)|=|\Gamma(A\cup B)|-|\Gamma(A)|\geq|B|.
$$
Inductively match both pieces and combine them. If no nonempty proper subset is tight, choose an edge $xy$ and remove its endpoints. Every nonempty subset $B$ of the remaining $X$ is proper in the original $X$, so $|\Gamma(B)|\geq|B|+1$; removing $y$ preserves Hall's condition. Match the remainder inductively and add $xy$. This proves the theorem without a flow or disjoint-path theorem.
Back to article page
