# Maximum matching in bipartite graph [closed]

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)|)$$

## closed as off-topic by Chris Godsil, metamorphy, 1 0, Ernie060, John BOct 18 at 10:26

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Chris Godsil, metamorphy, 1 0, Ernie060, John B
If this question can be reworded to fit the rules in the help center, please edit the question.

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$$.