# a proof of Hall's theorem (for bipirtite graph matching)

Theorem: Let $$G=(A\cup B,E)$$ be a bipartite graph and for each $$S\subseteq A$$ let $$N(S)=\{v\in B\ :\ \exists u\in S\text{ such that}\{u,v\}\in E\}$$

Then, $$G$$ has a matching of size $$|A|$$ if and only if $$|N(S)|\geq|S|$$ for all $$S\subseteq A$$

I know that matching of size $$|A|\implies|N(S)|\geq|S|\ \forall S\subseteq A$$ is easy:

Proof: since there is a matching of size $$|A|$$ by looking at $$G$$ as the matching to which we added some edges we see the result right away.

But I was wondering about this proof that uses König's theorem ("In a bipartite graph the number of edges of a maximal cardinality matching is the same as the number of vertices in a minimum vertex cover"):

Proof 2: Let $$M$$ be the matching of size $$|A|$$. It is a maximal cardinality matching because it contains every vertex of $$A$$. By König's theorem any minimal vertex cover $$U$$ has $$|U|=|A|$$ vertices. If there was an $$S\subseteq A$$ such that $$|N(S)|<|S|$$ then by definition of neighborhood, $$N(S)$$ would touch the same edges as $$S$$ but with fewer vertices so $$U'=[U\backslash S]\cup N(S)$$ is of strictly smaller cardinality than $$U$$ and is also a vertex cover of $$G$$, which is impossible.