1
$\begingroup$

Hall's marriage theorem states that given a bipartite graph $G=(X+Y,E)$, if there is no $X$-saturating matching, there there exists $W\subseteq X$ such that $|W|>|N_G(W)|$.

Is the following generalized version true: if there is no matching that covers at least $|X|-k$ vertices of $X$, then there exists $W\subseteq X$ such that $|W|>|N_G(W)|+k$? I believe it is true by a similar proof as Hall's theorem, but it is not mentioned in the Wikipedia page. Is there a reference about this?

$\endgroup$

1 Answer 1

5
$\begingroup$

Yes, it is true, it is sometimes called "generalized Hall theorem". It may be reduced to $k=0$ case by the following trick: add $k$ new vertices to $Y$ and join them with all vertices in $X$. New graph satisfies the conditions of Hall theorem, choose an $X$-saturated matching in it and remove the edges which are incident to added vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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