# Difficult? Bipartite Graph problem

This problem is tagged as difficult in my course notes and I am not sure how to start. How should I start proving it?

Problem:

Let $G$ be a bipartite graph with bi-partition $A$, $B$, where $|A|$ = $|B|$ = $n$, and suppose that every vertex of G has degree at least $\delta$ < n. Prove that $G$ has a matching of size at least the minimum of $n$ and ($q$ - $\delta^2$)/($n$ - $\delta$).

-
What does the variable $q$ represent? –  Austin Mohr Jul 23 '11 at 7:14
@Autstin Oops its edges –  Mark Jul 23 '11 at 14:29
@Mark: Please do not repost this question; we don't want unnecessary duplicates. What you can do instead is make a trivial edit to the body of the question, which will bump the question to the front page again. Note that after 10 edits, the question becomes Community Wiki, which means that you won't get reputation from it. You can also put a bounty on your question to attract potential answerers. –  Zev Chonoles Aug 7 '11 at 12:04
@Zev Chonoles: how do I add a bounty? –  Mark Aug 7 '11 at 12:13
There appears to be some trick to solve this problem... –  Mark Aug 7 '11 at 12:15

Update: There was an error in this proof – sorry about that. I've fixed it, and now the bound comes out as stated in the question. (The erroneous version had claimed a tighter bound.)

Let a bipartite graph $G$ be given. Choose some maximum matching of size $r$ and split $A$ and $B$ as $A_+\cup A_-$ and $B_+\cup B_-$, where $A_+$ contains the vertices in $A$ that partake of the matching and $A_-$ contains those that don't, and likewise for $B$. Let $k_A$ be the number of edges in the matching whose vertices in $A_+$ have edges to $B_-$ and $k_B$ the number of edges in the matching whose vertices in $B_+$ have edges to $A_-$. For any given edge in the matching, it cannot be the case that both its vertex in $A_+$ has an edge to $B_-$ and its vertex in $B_+$ has an edge to $A_-$, since otherwise we could replace the edge by these two edges and obtain a larger matching. Thus $k_A+k_B\le r$. Further, if a vertex $a_1\in A_+$ has an edge to a vertex $b_- \in B_-$, its partner $b_1$ in the matching can't have an edge to the partner $a_2$ of a vertex $b_2\in B_+$ that has an edge to a vertex $a_-\in A_-$, since otherwise we could replace the two edges $(a_1,b_1)$ and $(a_2,b_2)$ in the matching by the three edges $(a_1,b_-)$, $(b_1,a_2)$ and $(b_2,a_-)$ and obtain a larger matching. (If you haven't drawn a diagram yet, now might be a good time.)

We can now count the maximal number $q$ of edges: The $n-r$ edges in $A_-$ can have edges only to $k_B$ vertices in $B_+$, and the $n-r$ edges in $B_-$ can have edges only to $k_A$ vertices in $A_+$. The $r$ vertices in $A_+$ and the $r$ vertices in $B_+$ can have up to $r^2$ edges between them, except for $k_Ak_B$ edges between the partners of the vertices connected to $A_-$ and $B_-$. [This is where the error was; I'd subtracted another $k_Ak_B$ edges between those vertices themselves, not just their partners, but those edges can't be used to enlarge the matching.] Putting it all together, we have

$$\begin{eqnarray} q &\le& (n-r)k_B+(n-r)k_A+r^2-k_Ak_B \\ &=& (n-r)(k_A+k_B)+r^2-k_Ak_B \\ &\le& (n-r)r+r^2-k_Ak_B \\ &=& nr-k_Ak_B\;. \end{eqnarray}$$

Enter $\delta$. All vertices in $A_-$ and $B_-$ must have at least $\delta$ edges, and they can only have edges to the $k_B$ vertices in $B_+$ connected to $A_-$ and the $k_A$ vertices in $A_+$ connected to $B_-$, respectively. Thus, either $A_-$ and $B_-$ are empty, in which case we have a perfect matching of size $n$, or we must have $k_A\ge\delta$ and $k_B\ge\delta$. Under these constraints, together with $k_A+k_B\le r$, we get the least possible value of $k_Ak_B$, and thus the largest possible value of $q$, for $k_A=\delta$ and $k_B=r-\delta$ or vice versa. Thus, unless there is a perfect matching,

$$\begin{eqnarray} q&\le&nr-\delta(r-\delta)\;,\\ r&\ge&\frac{q-\delta^2}{n-\delta}\;. \end{eqnarray}$$

-
thanks for the detailed solution, I am going to need some time to read through this. Also, your tigher bound is the correct one, because the original copy of the question was wrong it should be your tigher bound. –  Mark Aug 8 '11 at 6:49
@Mark: I don't understand. You write that it should be my tighter bound, but in your edit to the question, you've changed the bound to be even less tight than before, by subtracting $\delta^2$ in the numerator instead of just $\delta$. Which one is it? –  joriki Aug 8 '11 at 8:30
So sorry it was $(q - δ^2)/(n - δ)$ according to the corrected version of the question. But isn't your bound $(q−2δ^2)/(n−2δ)$ similar? Should the technique be similar? –  Mark Aug 8 '11 at 8:42
@Mark: No, that corrected bound is even weaker than the original bound, which was weaker than my bound. It's easiest to compare them in the forms with $n-\delta$ in the denominator, since then they differ only in the numerator, which is $q$, $q-\delta$ or $q-\delta^2$. The form you cite has $n-2\delta$ in the denominator and isn't similar to your corrected bound at all; consider what happens as $\delta$ goes to $n/2$. Regarding the technique: are you looking for a proof that "directly" gives your weaker bound? If not, you can just take my proof and then subtract $\delta^2$ to weaken the bound. –  joriki Aug 8 '11 at 8:46
Would it be much easier to prove this even weaker bound ? –  Mark Aug 8 '11 at 8:48

Some discrete mathematics or combinatorics about maximal matchings in bipartite graphs would likely get you started:

• Augmenting path algorithm for bipartite graph. An augmenting path in a bipartite graph can imply a matching.
• Max-flow min-cut theorem
• Perfect matchings in bipartite graphs

-
I know about 2 of the 3 theorems above, however I hit a brick wall when trying to apply them. Do you know how I could use the above to solve my problem? because I think I need to know some more techniques to solve the problem. –  Mark Jul 23 '11 at 16:26
I can't solve the problem either, but I would have searched for matchings with the aforementioned algorithms for matching (if I remember correctly you have a matching if you have an augmenting path, so you need to show the size of the matching) using that the sets A and B have the same cardinality where maybe it's "obvious" that δ < n and minimum matching is n, so we need to find where the number (q - δ)/(n - δ) comes from. I would have inspected the algorithms for matchings and looked at maximal matchings and perfect matchings to get a notion for the minimal matching. –  Programmer 400 Jul 25 '11 at 12:22

I got this proof from my professor during office hours:

Let $C$ be a minimum cover, and let

$$C_1 = |C\cap A|$$

and

$$C_2 = |C\cap B|\;.$$

So since the size of a maximum matching is equal to $|C|$, suppose by contradiction that

$$|C| < \min(n, (q - \delta^2)/(n- \delta))\;.$$

Then

$$C_1 + C_2 < n$$

and

$$C_2 \geq \delta, C_1 \geq \delta\;.$$

As there can't be any edges between $A\setminus C$ and $B\setminus C$, we can bound the number $q$ of edges by adding up all possible edges between $A\cap C$ and $B\setminus C$, between $A\setminus C$ and $B\cap C$ and between $A\cap C$ and $B\cap C$:

$$q \leq C_1(n - C_2) + C_2(n - C_1) + C_1C_2\;.$$

He said this next step is the crucial move with a little wishful thinking. Basically he said he wants to turn

$$q \leq C_1(n - C_2) + C_2(n - C_1) + C_1C_2$$

into

$$q \leq C_1(n - \delta) + C_2(n - \delta) + \delta^2\;.$$

But we can't just replace $C_1C_2$ by $\delta^2$ since $\delta^2\leq C_1C_2$, so he used the fact that

$$(C_1 - \delta)(C_2 - \delta) \geq 0$$

since $C_2 \geq \delta, C_1 \geq \delta$. So

$$\begin{eqnarray} q &\leq& C_1(n - C_2) + C_2(n - C_1) + C_1C_2 \\ &=& C_1n+C_2n-C_1C_2 \\ &=& (C_1 + C_2)n - (C_1 + C_2)\delta + \delta^2 - (C_1C_2 - C_1\delta - C_2\delta + \delta^2) \\ &=& |C| (n - \delta) + \delta^2 - (C_1 - \delta)(C_2 - \delta) \\ &\leq& |C| (n - \delta) + \delta^2\;, \end{eqnarray}$$

and thus

$$|C| \geq (q-\delta^2) / (n - \delta)\;,$$

which contradicts our assumption that $|C| < \min(n, (q - \delta^2)/(n- \delta))$.

(He said this proof is not very constructive but somehow it works)

As for the example,

consider a graph where the first two vertexes in $A$ and $B$ has degree $8$. The rest of the six vertexes from $A$ join the 2 vertexes in $B$ and vice versa (so the minimum degree for each of the six vertexes is $2$). This graph has maximum match of size $4$ because the initial four vertexes from $A$ and $B$ are the minimum cover.

this is roughly the graph (if you don't mind the bad drawing):

So $q$ = $2 \times 6 + 2 \times 8 = 28$ edges.

So applying the bound $(28 - 4) / (8 - 2) = 4$ which holds since $|M| = 4$, but the tighter bound is $(28 - 8) / (8 - 4) = 5$.

-
Where you say "I am not sure how he derived this", he uses the fact that there can't be edges between the lower (non-shaded) parts of the diagram, since then $C$ wouldn't be a cover; the three terms correspond to the possible numbers of edges between the upper/lower, lower/upper and upper/upper parts, respectively. What I don't understand is what happens where you write "so he added this". What did he add to what? And how did this allow him to get around what you rightly pointed out, that $\delta^2\le C_1C_2$ and thus we can't get from the inequality with $C_1C_2$ to the one with $\delta^2$? –  joriki Aug 8 '11 at 18:24
@joriki: I will double check with him again. –  Mark Aug 8 '11 at 18:30
@joriki: I walked by his office and he is busy, I will try to get clarification tomorrow. Sorry for the wait. –  Mark Aug 8 '11 at 19:14
@joriki: I have updated again. Please see if I need more clarifications. –  Mark Aug 8 '11 at 22:56
@joriki: it seems he didn't need to get around it because $q \leq C_1(n - \delta) + C_2(n - \delta) + C_1C_2$ just needed some algebra to prove the bound. –  Mark Aug 9 '11 at 0:22