# Matchings using Hall's theorem: Why does only 1 of these solutions work?

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$.

• @bof: That graph has a perfect matching, namely $a_i$ with $b_{11-i}$ for each $i$. – hmakholm left over Monica Dec 17 '17 at 20:33
• @bof Aha I think that's exactly right! For some reason I overlooked that fact when applying the theorem. Thank you :) – Alex.F Dec 17 '17 at 20:56
• @bof Would you be able to post that as an answer so I can mark this question as solved? – Alex.F Dec 17 '17 at 20:59
• Solution 1 actually shows that, if you strengthen the assumption to "minimum degree at least $\frac n2-\frac12$", then $G$ contains a matching of size $n-1.$ – bof Dec 17 '17 at 22:03

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.$