Hall marriage theorem

A bipartite graph has a matching saturating $X$ exactly when $|N(S)|\ge |S|$ for every $S\subseteq X$.

In a finite bipartite graph, suppose every left vertex has positive degree and each edge joins vertices with $d(x)\ge d(y)$ from left to right. Then $|N(A)|\ge {\sum }_{x\in A}{\sum }_{y\sim x}1/d(y)\ge |A|$, so a matching covers the left side.

For finitely many Lebesgue measurable sets $A_i\subseteq [0,1]$ and nonnegative demands $b_i$, pairwise disjoint measurable subsets $B_i\subseteq A_i$ with $\lambda (B_i)=b_i$ exist exactly when $\lambda ({\bigcup }_{i\in I}{A}_i)\ge {\sum }_{i\in I}{b}_i$ for every index subset $I$. Necessity is additivity and monotonicity of Lebesgue measure. For sufficiency, partition the set union into membership cells $E_J$, send flow from a source through demand vertices $i$ to cells with $i\in J$, then to a sink. Source capacities are $b_i$, cell capacities are $\lambda (E_J)$, and intermediate capacities are $D={\sum }_i{b}_i$. Every cut of a flow network has capacity at least $D$ by the assumed inequalities. The max-flow min-cut theorem provides the allocations, and divisibility of Lebesgue measure turns each cell allocation into disjoint pieces. If $D=0$, all $B_i$ can simply be empty.

For Hall's theorem, either every proper nonempty set has one excess neighbour and one deletes an arbitrary edge's endpoints, or a tight set $S$ with $|N(S)|=|S|$ splits the problem into the induced graph on $S\cup N(S)$ and its complement.

In a $k$-regular bipartite graph, edge counting gives equal vertex-class sizes and $k|S|\le k|N(S)|$. Hall's theorem therefore supplies a perfect matching.