bipartite matching with minimum degree condition Let $G$ be a bipartite graph with parts $A$ and $B$ having $|A|=|B|=n \geq 1$. Let $\alpha \in (0,1/2]$. If the minimum degree $\delta (G) \geq \alpha n$, then show that $G$ has a matching of size at least $2\alpha n$.
I have no idea how to do this. So we are trying to show if we have a matching set $M$, that $|M|\geq 2\alpha n$. Its hard to understand that $\alpha$ can make $\alpha n$ be a non integer.
 A: Here is a sketch of a proof.  Let $M$ be a maximum size matching, and for sake of contradiction suppose $|M| < 2 \alpha n$.  Since $|M| < 2 \alpha n \leq n$, there must be vertices $u \in A$ and $v \in B$ that aren't covered by the matching.  Let $u$'s neighbors in $B$ be $B_u$, and notice that $|B_u| \geq \alpha n$.  Well, all of $B_u$ is covered by the matching, or else there would be an obvious way to make the matching bigger leading to a contradiction.  Thus, each vertex in $B_u$ is matched with a vertex $A$ -- we'll call these vertices $A_u$, and notice $|A_u| \geq \alpha n$. 
We also have $v$ with at least $\alpha n$ neighbors in $A$, which we'll call $A_v$.  
Okay, here is where the proof needs a bit more explanation to fill in:  Notice that $A_u \cap A_v$ is non-empty, and then form an augmenting path from $u$ to $v$ (see the end of page 2 of this for definition of augmenting path).  We're then done by a contradiction.
A: Suppose we have a matching with fewer than $2\alpha n$ edges which can't be extended by adding an edge; it looks like the following (with unimportant edges omitted):

(TL;DR: replace the black edge in the matching with the two dashed orange edges.)
In the above image, the black edges are the matching, the pink blobs contain the used vertices, and blue blobs contain the unused vertices.  There are no edges between the blue blobs, otherwise the matching could be extended by adding an edge.
We pick a vertex from each blue blob, $u$ and $v$, say.  Since they have degree $\geq \alpha n$ and the pink blobs contain $< 2 \alpha n$ vertices, there is an edge $xy$ in the matching for which both $ux$ and $vy$ are edges in the graph (the dashed orange edges in the figure).
So we get a matching with a greater number of edges by removing $xy$ and adding in $ux$ and $vy$.
