Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 2 / 15H (Graph Theory)

For a finite bipartite graph with left vertex set $L$, Hall marriage theorem says that a matching in a graph covering $L$ exists exactly when $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because distinct matched neighbors of $S$ lie in $N(S)$.

For sufficiency, induct on $|L|$, the empty case being immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, apply the induction hypothesis to the graph on $S,N(S)$. For the remaining graph, every $T\subseteq L\setminus S$ satisfiesso induction matches the remaining vertices too. If there is no such tight subset and $|L|>1$, every nonempty proper subset has at least one extra neighbor. Select an edge and remove its endpoints. Each subset of the remaining left vertices loses at most one neighbor, so it still satisfies the required condition; induction supplies the rest of the matching in a graph. The case $|L|=1$ follows directly from the condition.

For a doubly stochastic matrix $A=(a_{ij})$, make a bipartite graph joining row $i$ to column $j$ when $a_{ij}>0$. For a row subset $S$,Hall marriage theorem therefore gives a perfect matching, or a permutation $\sigma$, with $\boxed{a_{i,\sigma (i)}>0\text{ for every }i}$.