Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / A / 1 / b / Solution

If no complete matching exists, Hall's theorem gives a nonempty $S\subseteq V_1$, of size $k$, with $|N(S)|\le k-1$. The pairs between $S$ and $V_2\setminus N(S)$ must be nonedges, so there are at leastmissing edges. Hence $e(G)\le n^2-n$, contradicting the strict edge bound. Therefore a complete matching exists.

The strictness is necessary: isolate one vertex of $V_1$ and put all edges between the remaining $n-1$ left vertices and all $n$ right vertices. There are exactly $n(n-1)$ edges and no matching can cover the isolated vertex. This also handles $n=1$.