In a bipartite graph $G$ with bipartite sets $X$ and $Y$, prove that $\alpha'(G)=|X|-\max_{S \subset X}(|S|-|N(S)|) $

Question

In a bipartite graph $G$ with bipartite sets $X$ and $Y$, prove that $\alpha'(G)=|X|-\max_{S \subset X}(|S|-|N(S)|) $ No idea how to approach this one...any leads please?

Answer 1

You probably have just met the marriage theorem. This is an application of it.

Let $T$ be a subset realizing the maximum $d$ of $\max_{S\subset X}(|S|-|N(S)|)$, so $d=|T|-|N(T)|$. Note that $d$ cannot be negative, since the empty set is also a subset of $X$.

Let $M$ be a matching in $G$. The edges of $M$ that have an endpoint in $T$ have their other endpoint in $N(T)$, so there are at least $d$ unmatched vertices in $T$ (so in $X$), which shows that $\alpha'(G)\leq|X|-d$.

For the other side you use a small "trick": add $d$ vertices to $Y$ and connect the new vertices to all of $X$. The resulting graph satisfies the marriage condition for $X$, so it has a matching of size $|X|$. Now remove the new vertices again and you are left with a matching of size $|X|-d$, which proves that $\alpha'(G)\geq|X|-d$.