= 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 least
$$
k(n-k+1)=n+(k-1)(n-k)\ge n
$$
missing edges. Hence $e(G)\le n^2-n$, contradicting the strict edge bound. Therefore \b[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$.
Back to article page
