Application of Hall's Theorem Perfect Matching

Question

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.

Answer 1

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

Answer 2

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.