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

 A: 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}
$$
A: 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.
A: 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$.
