Question: Suppose that $G$ is bipartite with vertex classes $A$ and $B$ so that $|A|=|B|=n$. Suppose that $δ(G) ≥ n/2$. Use Hall’s theorem to show that G has a perfect matching.

My Answer: Let $G$ be a bipartite graph with vertex classes $A$ and $B$ such that $|A|=|B|=n$. Consider any set $S$ in $A$. Let $t$ be the number of edges from $S$ to $N_G(S)$. Since the minimum degree of every vertex is at least $\frac{n}{2}$ we have that $t \geq \frac{n}{2}|S|$. We also have that $\frac{n}{2}|N_G(S)| \geq t$ as the set $N_G(S)$ may have other neighbors in $A$ which are outside of $S$. Combining these inequalities gives $\frac{n}{2}|N_G(S)| \geq \frac{n}{2}|S|$, hence $|N_G(S)| \geq |S|$. So by Hall's Theorem there is a matching covering all of $A$, or equivalently every maximum matching covers $A$. Using a similar argument we have that every maximum matching covers $B$. Thus, $G$ contains a perfect matching.

I just wanted to check that what I have done here is correct as I was initially confused with the $δ(G) ≥ n/2$ part.


Your argument is incorrect. You have not justified your claim that $\frac n2|N_G(S)|\ge t.$ You have not really used the assumption that $\delta(G)\ge n/2$; why doesn't the same argument work with $n/2$ replaced by any other nonzero quantity? What happens if you try the same argument assuming $\delta(G)\ge1$ instead of $\delta(G)\ge n/2$?

  • $\begingroup$ $\frac{n}{2}|N_G(S)| \geq t$ as the minimum degree of every vertex is $\frac{n}{2}$ so the number of edges leaving the set $|N_G(S)|$ is equal to $\frac{n}{2}|N_G(S)|$. This is greater than or equal to $t$ as the vertices in $|N_G(S)|$ could have neighbours in $A$ outside $S$. But $|N_G(S)|$ must have at least $t$ edges leaving it since this is the number of edges from $S$ to $|N_G(S)|$. $\endgroup$ – Koala Mar 2 '18 at 0:02
  • $\begingroup$ Is the $δ(G)≥n/2$ part important as if the minimum degree was any smaller then some vertices would not be included in the matching? I am not sure how I would show this. $\endgroup$ – Koala Mar 2 '18 at 0:04
  • $\begingroup$ The number of edges leaving the set $N_G(S)$ is greater than or equal to $\frac n2|N_G(S)|.$ $\endgroup$ – bof Mar 2 '18 at 0:05
  • $\begingroup$ Does your argument work just as well if you replace the assumption $\delta(G)\ge n/2$ with $\delta(G)\ge n/10$? If not, why not? $\endgroup$ – bof Mar 2 '18 at 0:06
  • 1
    $\begingroup$ If $t'$ is the number of edges leaving the set $N_G(S)$ then $$t'\ge\frac n2|N_G(S)|\tag1$$ and $$t'\ge t\tag2.$$ The inequality $$\frac n2|N_G(S)|\ge t\tag3$$ DOES NOT FOLLOW from (1) and (2). $\endgroup$ – bof Mar 2 '18 at 0:11

I don't understand why you are counting edges there, and $\frac{n}{2}|N_G(S)| \geq t$ is suspect because some vertices may have contributed more than $n/2$ edges to the set of $t$ edges.

It's a little easier to see that all the vertices in one part must all connect to a sufficiently large subset of the other part. Here's how I would do it:

We already know that every vertex is linked to at least $n/2$ in the other part, so consider a set $S$ of vertices in $A$ with $|S|>n/2$. Then every vertex in $B$ must be linked to at least one vertex in $S$ since there are not enough vertices in $A$ outside of $S$ to satisfy the degree of any vertex in $B$; thus every such $S$ connects to all $n$ vertices of $B$.

Clearly the same argument applies to large subsets of $B$. Hall's theorem thus applies.

  • $\begingroup$ The question was not "how do I prove this"; the question was "is my proof correct". $\endgroup$ – bof Mar 2 '18 at 0:02
  • $\begingroup$ True; implicitly I thought the proof was fragile but I should have been clearer. Updated. $\endgroup$ – Joffan Mar 2 '18 at 1:22

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.