To show: There exists a matching of size at least $|E(G)|/\Delta(G)$ for any bipartite graph $G$. ($\Delta(G)$ is the maximum degree)
Approach. : If say $|E(G)|/\Delta(G)= k+\epsilon, 0\le\epsilon<1 $ So we need to prove there exists a matching of size at least k. (Since size of matching is an integer).
I was trying induction on $[|E(G)|/\Delta(G)]$ ($[\cdot]$ is the greatest integer function). For base case 1, we can just take an edge between the vertex with highest degree and one of its neighbours to get a matching of size 1.
Induction hypothesis: this is true for all $k'<k$. To prove that this is true for $k$.
Proof: This is where I am not able to move further.
My attempt: I'm trying to extend the matching when $k$ increases. Comparing to when $k'=k-1$, we now have $\Delta(G)$ more edges to choose from i.e. $2\Delta(G)$ total vertices to choose from. $2k'(<2(k-1))$ vertices are chosen in the matching of size $k'$ so we can pick two vertices not already present in that matching.
Problem: What if all the $2\Delta(G)$ vertices to choose from are already chosen in the previous matching? I know we don't really have to extend the matching. I am also open to any new way of proving this.
Hint: Use Koning's theorem to conclude that the maximum size of the matching in a bipartite graph is equal to the minimum size of the vertex cover. Let $\beta(G)$ be the size of the min vertex cover.
The inequality you want to prove becomes $$ \beta(G) \Delta(G) \geq E(G). $$ Can you finish it now?