0
$\begingroup$

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

$\endgroup$

closed as off-topic by Chris Godsil, metamorphy, 1 0, Ernie060, John B Oct 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.

0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.