1
$\begingroup$

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:enter image description here

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!

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – saulspatz
    Nov 11 '20 at 17:29
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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