Bipartite Matchings Question 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. 
 A: 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.
A: 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
