Here's the full text of the problem I'm having trouble with. This question exists here: Bipartite Matchings Question , but I'm looking for a solution not using colorings, or the max-flow min-cut theorem. I was intrigued by Tyler Seacrest's comment about using the Konig-Egevary theorem, and ideally I'd like a solution using that (or maybe even Hall's theorem, or the explicit construction of such a matching).
Let $G = (V,E)$ be a bipartite graph with $l$ edges. Prove that $G$ has a matching whose size is at least $\frac{l}{\Delta(G)}$.
All graphs here are finite and simple.
Here's what I've tried: induction by $|V|$. Let $(A, B)$ be a bipartition of $V$, $A = \lbrace x_{1},...,x_{m} \rbrace$, $B = \lbrace y_{1},...,y_{n} \rbrace$. Let, for example, $x_{1} \in A$ be a vertex s.t. $d(x_{1}) = \Delta(G)$. If $H = G \setminus x_{1}$ is the graph induced by $V \setminus \lbrace x_{1} \rbrace$, then by the induction hypothesis, we have that there exists a matching in $H$ of size at least $\frac{l-\Delta(G)}{\Delta(H)} \geq \frac{l-\Delta(G)}{\Delta(G)} \geq \frac{l}{\Delta(G)} - 1$. Now, matching $x_{1}$ with some $y_{j}$ would give me the desired matching, but I don't know if there are any unmatched neighbors of $x_{1}$ left.
Is there a way to fix my proof? If not, I'd like to know if there's a solution more elementary than the two solutions offered in the linked question (in the first answer, I don't know how to prove that bipartite graphs are "class 1", as the answerer says, and in the second one, I don't know the max-flow min-cut theorem).
The argument using the Kőnig-Egerváry theorem is simply that a minimum vertex cover has size at least $\frac{l}{\Delta(G)}$, because each vertex can cover at most $\Delta(G)$ edges, so to cover all $l$ edges, you need at least $\frac{l}{\Delta(G)}$ vertices.
The Kőnig-Egerváry theorem tells us that the size of a minimum vertex cover is equal to the size of a maximum matching, so there must be a matching with at least $\frac{l}{\Delta(G)}$ edges.