1
$\begingroup$

Let G be a bipartite graph. Show that G contains a matching of size at least $\frac{e(G)}{∆(G)}$, where e(G) denotes the number of edges of G and ∆(G) denotes its maximum degree.

I tried to do a proof by contradiction and assume that $|M|< \frac{e(G)}{∆(G)}$ but so far I've been unsuccessful.

$\endgroup$
2
  • 2
    $\begingroup$ This is a tough one without using some big theorem. However, if you apply the Konig-Egevary theorem, it should follow fairly quickly. $\endgroup$ – Tyler Seacrest Mar 12 '15 at 15:54
  • $\begingroup$ Please consider accepting an answer if there are any that you like, or indicating what is missing in the current answers, so that we can learn what you're interested in. (meta.stackexchange.com/questions/5234/…) $\endgroup$ – William Macrae Apr 7 '15 at 17:49
1
$\begingroup$

It's well know, and provable without max-flow min-cut that bipartite graphs are Class 1 (that is, $\Delta$-edge-colorable). See, for example Proposition 5.3.1 in Diestel, which predates max-flow min-cut: http://www.flooved.com/reader/3447?no-redirect#140

If we take a $\Delta$-coloring of the edges of $G$, then the average color has $\frac{e(G)}{\Delta(G)}$ edges, thus (for nonempty $G$) at least one color must have at least $\frac{e(G)}{\Delta(G)}$ edges. In proper edge colorings, each color defines a matching, so this provides the existence of the matching directly.

I should also mention that Diestel's proof for 5.3.1 is somewhat coloring-focused, and there's one that is much more relevant to thinking about matchings that I prefer for this context. Starting with the Marriage Theorem (which shouldn't require max-flow min-cut), show that all $k$-regular bipartite graphs have a perfect matching. Then establish by induction on $k$ that all $k$-regular bipartite graphs are $k$-edge-colorable. Finally, given $G$, find a bipartite supergraph $H$ such that $G \subseteq H$ and $H$ is $\Delta(G)$-regular. The $\Delta$-edge-coloring of $H$ induces a $\Delta$-edge-coloring on $G$. For the construction of $H$, and some more detail, see for example these notes (especially the construction of $H$ by cloning, that starts on Page 3): https://www.math.hmc.edu/~kindred/cuc-only/math104/lectures/lect15.pdf

$\endgroup$
0
$\begingroup$

Here is a proof using max-flow min-cut theorem. I hope this is not considered as cheating.

Suppose the partite sets are $U$ and $V$. Add two vertices $s$ and $t$ with $s$ linking to all vertices in $U$ and $t$ to all vertices in $V$.

Assume for the sake of contradiction that the size of maximal matching is less than $e(G)/\Delta(G)$. It amounts to say that the max-flow is less than that. By the max-flow min-cut theorem, the min-cut is less than that.

Consider the minimal cut $S = \{s\}\cup U_1\cup V_1$ and $T = \{t\}\cup U_2 \cup V_2$, where $U_1\sqcup U_2 = U$ and $V_1\sqcup V_2 = V$. We know that the capacity of the cut set $$c(S, T) = |U_2|+|V_1|+e(U_1, V_2)+e(U_2, V_1) < e(G)/\Delta(G).$$ which certainly implies, $$|U_2|\Delta(G)+|V_1|\Delta(G)+e(U_2, V_1)+e(U_2, V_1) < e(G).$$ However, $e(U_2, V_2)\leq |U_2|\Delta(G)$ and $e(U_1, V_1)\leq |V_1|\Delta(G)$, and so $$e(G) = e(U_2, V_2)+ e(U_1, V_1) + e(U_1, V_2)+e(U_2, V_1)< e(G)$$ which yields a contradiction.

$\endgroup$
1
  • $\begingroup$ Whoever down votes this please provide a reason so that I can understand what I have done wrong. Thanks in advance. $\endgroup$ – Zilin J. Mar 21 '15 at 1:12

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.