Hall theorem with non-saturating matching

Question

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?

Answer 1

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.