 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)|\ge |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$,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)|\ge |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.