# Minimum size of bipartite graph for existence of perfect matching

I am trying to work through an exercise regarding the minimum size of a bipartite graph to guarantee the existence of a perfect matching. The question is as follows:

Let $G$ be a bipartite graph with bipartition $({A,B})$ such that $|A|=|B|=k$. Let $m$ be the size of $G$. Prove that if $$m\geq k^2-k+1$$ then $G$ has a perfect matching.

The first thing that I noticed was that |$A$|=|$B$| implies that a matching which includes every element in $A$ (or $B$) is a perfect matching. It seems reasonable to me that using König-Hall Theorem would probably be a good thing to try, i.e. trying to show that

$$|N(X)|\geq |X| \hspace{1mm}, \hspace{5mm}\forall \hspace{1mm} X \subseteq A .$$

which would get the required result. Now here, I have been trying to construct a proof by contradiction but haven't been able to get it to work so far.

My intuition for the question is, however, not really anything to do with König-Hall. Essentially, we have the maximum size of $G$ in the case where $G$ is the complete bipartite graph $K_{k,k}$ and $m=k^2$. Then from here we can remove $k-1$ edges without losing the existence of a perfect matching in $G$. Now what I'm finding difficult to understand is why, no matter the configuration of degrees in $A$ after we remove the $k-1$ edges, we still have a perfect matching. Any help would be appreciated!

• The point is that if you remove $k-1$ edges from the complete bipartite graph $K_{k,k}$, the hypothesis of Hall's theorem are still fulfilled. – Jack D'Aurizio Jun 18 '17 at 1:15

If $|X|=1$ then $|N(X)|\geq 1$ since just $k-1$ edges are removed from the complete bipartite graph $K_{k,k}$. If $|X|=2$, is it possible that $|N(X)|\leq 1$? Clearly $N(X)$ is non-empty by the previous point, and assuming $N(X)=\{b\}$ we have that no edges exist between $X$ and $\{1,\ldots,k\}\setminus\{b\}$, but that requires the removal of at least $2(k-1)$ edges from $K_{k,k}$. It is simple to finish the proof from here: if there are $\geq k^2-k+1$ edges, the hypothesis of Hall's theorem are clearly fulfilled.