# Application of Hall's theorem to find a matching of a specific size

Question: Let $G$ be a bipartite graph with vertex classes $A$ and $B$ with $|A| = |B| = n$ and $δ(G) = n/2 − 1$. Show that $G$ contains a matching which covers all but at most $2$ vertices in each vertex class.

Let $G$ be a bipartite graph with vertex classes $A$ and $B$ with $|A| = |B| = n$ and $δ(G) = n/2 − 1$. Also let $M$ be a matching in $G$.

Add $2$ new vertices to each of the classes $A$ and $B$ which are adjacent to all of the vertices of the other class, creating the graph $G'$. This graph has vertex classes $A'$ and $B'$ each of size $n+2$ and each with minimum degree at least $\frac{n-2}{2} + 2 = \frac{n+2}{2}$. So by Hall's Theorem $G'$ has a perfect matching $M'$, which has size at least $n+2$. At most 4 edges of $M$ are incident to the new vertices. When we remove these edges from $M'$ we obtain a matching $M$ for $G$ of size at least $n+2-4=n-2$, as required.

Where I am Confused: I know that if Hall's Theorem holds then the matching is perfect as $|A|=|B|$. But I am confused why Hall's Theorem holds for this new graph $G'$ and not sure how to show that it does.

Let $S$ be a subset of $A'$.
If $|S| \le \frac{n}{2}+1$, then clearly $|N_{G'}(S)| \ge \frac{n}{2} +1 \ge |S|$ since a single vertex of $S$ has at least $\frac{n}{2}+1$ neighbors.
Otherwise $|S| > \frac{n}{2}+1$. Then we claim $N_{G'}(S) = B'$, which would yield $|S| \le n+2 = |N_{G'}(S)|$. To verify this claim, note that if there existed some point of $B'$ not in $N_{G'}(S)$, then it must be connected to $\ge \frac{n}{2}+1$ points of $A'$, all not in $S$. But there are only $n + 2 - |S| < \frac{n}{2} + 1$ points of $A'$ not in $S$, a contradiction.