3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @bof: That graph has a perfect matching, namely $a_i$ with $b_{11-i}$ for each $i$. $\endgroup$ – hmakholm left over Monica Dec 17 '17 at 20:33
  • $\begingroup$ @bof Aha I think that's exactly right! For some reason I overlooked that fact when applying the theorem. Thank you :) $\endgroup$ – Alex.F Dec 17 '17 at 20:56
  • $\begingroup$ @bof Would you be able to post that as an answer so I can mark this question as solved? $\endgroup$ – Alex.F Dec 17 '17 at 20:59
  • $\begingroup$ 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.$ $\endgroup$ – bof Dec 17 '17 at 22:03
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.