Maximum matching in bipartite graph

Question

Prove that for every bipartite graph G with bipartition {A, B}, the size of the maximum matching in G equals |A| − δ where

$$ δ = max_{S⊆A} (|S| − |N_G(S)|) $$

Answer 1

It is trivial that the size of a maximum matching cannot be greather than $|A| − δ$. We will then construct a matching of size $|A| − δ$ to complete the proof. let $S\subseteq A$ be a set of maximum size satisfiying $|S| - |N(S)| = δ$, let $T=N(S)$ and $G' = S \cup T$. $T$ has a saturating matching in $G'$ otherwise due to hall's condition there exists a subset of T with less neighbors than its size, then omitting its neighbors from A would lead to a subset of A with less neighbors than $δ$ allows.

all that is left is to show $G-G'$ has a matching saturating its A part. if for some $S' \subseteq (G-G')\cap A: |N(S')| \leq |S'|$, then $S \cup S'$ form a set satisfiying $|S \cup S'| - N(S \cup S') \leq δ$, contradicting our choice of $S$. thus $(G-G')\cap A$ satisfies hall's condition of a saturating matching. this matching combined with our matching saturating $T$ is a matching of size $|A| − δ$ in $G$.