The bipartite graph admits a perfect match

Question

Let $G:=(X+Y,E)$ be an finite bipartite graph with $|X|=|Y|=n$. I want to show that if $|E| \geq n^2-n+1$ then $G$ admits a perfect matching. I was thinking to use the Hall Theorem to show it but I have trouble to start the proof. Can somebody help me?

Answer 1

First, you should convince yourself that the given bound is sharp. That is, try to find an example with $|E| = n^2 - n$, but admit no perfect matching. You will see that almost every pair of vertices are joined by an edge in this case.

Now, let's start the main proof. If Hall's condition is not satisfied, then there should be a bad subset $A$ of $X$ such that $|A|>|N(A)|$. To find contradiction, we should expect the number of edges in this case to be smaller than $n^2-n+1$. The motivation is as follows:

There are no edges between $A$ and $Y-N(A)$. So, if $|N(A)|$ is small, there are a lot of non-edges between $A$ and $Y$. This will force the total number of edges to be smaller than $n^2 - n + 1$.

Now, we just need to put our ideas in numbers. I hope this gives you a good head-start.

Hint: it is much cleaner if you focus on bounding non-edges rather than edges.

There is also a really cute proof of this result using probabilistic method. Check out https://web.evanchen.cc/handouts/ProbabilisticMethod/ProbabilisticMethod.pdf#page53 if you are interested.