# Problem with finding perfect matchings in a bipartite graph

I've been given the following problem to solve;

Let $$G(X,Y)$$ be a bipartite graph such that in $$X$$ the degree of each vertex is at least $$r$$ and in $$Y$$ the degree of each vertex is at most $$r$$. Prove that this graph has a perfect matching.

Now after thinking on it I was able to come up with the following:

Let $$X=\{A,B,C\} ,Y=\{D,E,F,G\}$$ for $$r=2$$ we have $$\delta(X)\geq r$$ and $$\Delta(Y)\leq r$$ but clearly this graph does not have a perfect matching. What am I missing here? Am I understanding the question wrong? Or am I misunderstanding perfect matchings? Any help would be appreciated!

• I agree with you. The quoted "theorem" seems to be false, as stated. It seems like the additional condition $|X|=|Y|$ is needed, at the very least. Then the graph would be $r$-regular, and you'd need to prove that an $r$-regular bipartite graph has a perfect matching, and, if I recall correctly, this is true. Nov 11 '20 at 17:29

The general thing we can prove is that under these hypotheses, the graph has an $$X$$-perfect matching: a matching that saturates every vertex of $$X$$. (A perfect matching would require $$|X|=|Y|$$, and this is not guaranteed here.)
To prove this, you should check Hall's condition: prove that for every subset $$S \subseteq X$$, $$N(S)$$ - the set of vertices in $$Y$$ adjacent to a vertex in $$S$$ - satisfies $$|N(S)| \ge |S|$$.