Suppose $G$ is a bipartite Graph with vertex classes A and B with $|A| = |B| = n$ and minimum degree of any vertex is $\frac{n}{2} -1$.
Show that $G$ contains a matching which covers all but at most 2 vertices in each vertex class. ( I have done this part)
The part I need help with is:
For each $n$ describe a Graph that shows the bound of 2 on the number of unmatched vertices cannot be improved.
This is a homework question.
In order to answer that part, for each $k\ge 0$ you need to find bipartite graphs $G_{2k+2}$ and $G_{2k+3}$, with parts of size $2k+2$ and $2k+3$, respectively, and minimal degree at least $k$, such that every matching misses at least $2$ vertices in at least one part.
For $G_{2k+2}$ let the parts be $A=\{a_1,\ldots,a_{2k+2}\}$ and $B=\{b_1,\ldots,b_{2k+2}\}$. Let the set of edges of $G_{2k+2}$ be
$$\big\{\{a_i,b_j\}:i\in\{1,\ldots,k\}\text{ or }j\in\{1,\ldots,k\}\big\}\;.$$
In other words, the vertices $a_1,\ldots,a_k$ are adjacent to each vertex in $B$, the vertices $b_1,\ldots,b_k$ are adjacent to each vertex in $A$, and these are the only adjacencies. Clearly $\deg a_i=\deg b_i=2k+2$ if $1\le i\le k$, and $\deg a_i=\deg b_i=k$ if $k<i\le 2k+2$, so the minimum degree condition is satisfied. Let $A_0=\{a_1,\ldots,a_k\}$ and $B_0=\{b_1,\ldots,b_k\}$. Every edge of $G_{2k+2}$ has at least one endpoint in $A_0$ or $B_0$, so no matching can contain more than $2k$ edges. Thus, there must be at least two vertices in $A$ and two in $B$ that are not covered.
I’ll leave it to you to check that the same technique takes care of $G_{2k+3}$.