= Hall theorem proof outline
{c}
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.
Back to article page
