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!
Best Answer
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|$.
If you've seen the proof that a regular bipartite graph has a perfect matching, this will be similar.