Suppose $G$ is a $(X,Y)$ graph with $|X| = |Y| = n \geq 1$. Prove that if $|A(G)| > n(n-1)$ then $G$ has a perfect matching.
I'm looking for a hint on showing that $|N(S)| \geq |S|, \forall S \subset X$. I don't understand how to relate the number of edges to the problem
Based on Greg Martin comment, I'm going to give it a try. I think this proof can get better, my feeling is that it's quite cumbersome with the approach to maximize the number of edges.
Suppose, by contradiction, that $\exists S \subset X$, such that $|S| < |N(S)$.
Let $m = |S|$. Then, the maximum number of edges incident to a vertex on $S$ is $m \times (m - 1)$ and the maximum number of edges not incident to a vertex on $S$ is $(n-m) \times (n-m+1)$. Using some calculus, we can find $m$ that maximizes the total number of edges. I'll skip the details, but we find that $m = \frac{n+1}{2}$.
Therefore:
$$|A(G)| \leq 2\times \frac{(n-1)}{2} \times \frac{(n+1)}{2} = (n-1)\times\frac{(n+1)}{2}$$
For $n \geq 1$, we have that $\frac{(n+1)}{2} \leq n$, therefore we conclude that $|A(G)| \leq n(n-1)$, which is an absurd, because $|A(G)| > n(n-1)$.
Therefore we conclude that $\forall S, S \subset X$ and by Hall Theorem we have that $X$ has a matching with $Y$. Because $|X| = |Y|$, it must be a perfect matching.
