# Hall theorem with non-saturating matching

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?

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.