1
$\begingroup$

I am trying to work through an exercise regarding the minimum size of a bipartite graph to guarantee the existence of a perfect matching. The question is as follows:

Let $G$ be a bipartite graph with bipartition $({A,B})$ such that $|A|=|B|=k$. Let $m$ be the size of $G$. Prove that if \begin{equation} m\geq k^2-k+1 \end{equation} then $G$ has a perfect matching.

The first thing that I noticed was that |$A$|=|$B$| implies that a matching which includes every element in $A$ (or $B$) is a perfect matching. It seems reasonable to me that using König-Hall Theorem would probably be a good thing to try, i.e. trying to show that

\begin{equation} |N(X)|\geq |X| \hspace{1mm}, \hspace{5mm}\forall \hspace{1mm} X \subseteq A . \end{equation}

which would get the required result. Now here, I have been trying to construct a proof by contradiction but haven't been able to get it to work so far.


My intuition for the question is, however, not really anything to do with König-Hall. Essentially, we have the maximum size of $G$ in the case where $G$ is the complete bipartite graph $K_{k,k}$ and $m=k^2$. Then from here we can remove $k-1$ edges without losing the existence of a perfect matching in $G$. Now what I'm finding difficult to understand is why, no matter the configuration of degrees in $A$ after we remove the $k-1$ edges, we still have a perfect matching. Any help would be appreciated!

$\endgroup$
  • $\begingroup$ The point is that if you remove $k-1$ edges from the complete bipartite graph $K_{k,k}$, the hypothesis of Hall's theorem are still fulfilled. $\endgroup$ – Jack D'Aurizio Jun 18 '17 at 1:15
1
$\begingroup$

If $|X|=1$ then $|N(X)|\geq 1$ since just $k-1$ edges are removed from the complete bipartite graph $K_{k,k}$. If $|X|=2$, is it possible that $|N(X)|\leq 1$? Clearly $N(X)$ is non-empty by the previous point, and assuming $N(X)=\{b\}$ we have that no edges exist between $X$ and $\{1,\ldots,k\}\setminus\{b\}$, but that requires the removal of at least $2(k-1)$ edges from $K_{k,k}$. It is simple to finish the proof from here: if there are $\geq k^2-k+1$ edges, the hypothesis of Hall's theorem are clearly fulfilled.

$\endgroup$
  • $\begingroup$ Thank you for your answer! $\endgroup$ – RichoKicked800goals Jun 18 '17 at 1:34

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.