7
$\begingroup$

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

  • 0
    @joriki: Ok I will do that2011-08-08

3 Answers 3

13

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

  • 0
    @FiniteA: You're quite right -- thanks, I've corrected it.2011-12-11
1

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 hope that studying the above concepts can help you.

  • 0
    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.2011-07-25
0

I got this proof from my professor during office hours:

enter image description here

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):

enter image description here

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

  • 0
    @joriki: $a$wesome, thanks a lot, I have learned a great deal from you !2011-08-10