Hall theorem proof outline

For sufficiency, take a matching in a graph of maximum size and suppose a left vertex $u$ is unmatched. Follow unused edges from left to right and matching edges back to the left. An unmatched reachable right vertex yields an augmenting path in a matching, contradicting maximal size. Otherwise let $S,T$ be the reachable left and right sets. Every member of $T$ is matched to a distinct member of $S\setminus \{u\}$, and every member of $S\setminus \{u\}$ is reached this way. Since $N(S)=T$, we obtain $|N(S)|=|S|-1$, contradicting the Hall condition. Finiteness ensures that a maximum-size matching in a graph exists.

The alternative Hall induction through a tight set uses mathematical induction: a proper nonempty subset with $|N(S)|=|S|$ splits off a balanced induced subgraph; without such a tight set, deleting one chosen edge's endpoints preserves the Hall condition on the smaller left side.