Let $G$ be a (simple) bipartite graph with parts $A,B$ such that $|A|=|B|=n$ and with minimum degree at least $n/2-1$. Prove that $G$ contains a matching which covers all but at most $2$ vertices in each part.
Solution 1: Add $1$ vertex to each part $A$ and $B$ and connect it to all vertices in the opposite part. The resulting graph $G'$ has minimum degree at least $n/2-1+1=n/2$, so by Hall's theorem $G'$ has a perfect matching $M'$ with $n+1$ edges. At most $2$ of these edges are adjacent to the new vertices we added, so removing these edges we obtain a matching $M$ for $G$ of size at least $n-1$.
Solution 2: Add $2$ vertices to each part $A$ and $B$ and connect each to all vertices in the opposite part. The resulting graph $G'$ has min degree at least $n/2-1+2=n/2+1$, so by Hall's theorem $G'$ has a perfect matching $M'$ with $n+2$ edges. At most $4$ of these edges are adjacent to the new vertices, so removing these edges we obtain a matching $M$ for $G$ of size at least $n-2$.
The second gives the desired result but why does the first one suggest a better bound?
Edit: In the above I am using the following theorem: "If $G$ is bipartite with parts $|A|=|B|=n$ and minimum degree at least $n/2$ then $G$ has a perfect matching." This can be shown from the usual Hall's theorem: "If $G$ is bipartite with parts $A$, $B$, then $G$ has a matching covering all of $A$ if and only if $|N(S)|\geq |S|$ for all $S\subseteq A$.
In Solution 1 you need $G'$ to have minimum degree at least $(n+1)/2.$ If $n$ is odd this works because $\delta(G)\ge\lceil n/2-1\rceil=(n-1)/2$ in that case, but for even $n$ it fails.
The argument in Solution 1 actually shows that, if $G$ is a bipartite graph with parts $A,B$ such that $|A|=|B|=n,$ and with minimum degree at least $(n-1)/2,$ then $G$ contains a matching of size $n-1.$