# Application of Hall's Theorem Perfect Matching

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$?

• $\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)|$. – Koala Mar 2 '18 at 0:02
• 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. – Koala Mar 2 '18 at 0:04
• The number of edges leaving the set $N_G(S)$ is greater than or equal to $\frac n2|N_G(S)|.$ – bof Mar 2 '18 at 0:05
• 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? – bof Mar 2 '18 at 0:06
• 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). – 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.

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