Matching in Bipartite (A,B) Graph with $|M| \geq 2/5 |A|$

23 Views Asked by At

Let $G$ be a bipartite graph with partitions $(A,B)$. Suppose for all $u \in A$, we have $\deg_G(u) \geq 4$ and for all $v \in B$, $\deg_G(v) \leq 10$. Prove that there exists a matching $M$ of $G$ such that $|M| \geq \frac{2}{5}|A|$.

What I have so far: from the Handshaking Lemma, $$ 10|B| \geq \sum_{v \in B} \deg_G(v) = m = \sum_{u \in A} \deg_G(u) \geq 4|A| \implies |B| \geq \frac{2}{5}|A| $$

From here I'm thinking I need to find a minimum vertex cover $Q$ such that

$$ |Q| \geq \frac{2}{5} |A| $$ Then by Konig's Theorem, $|M| = |Q|$ and we get the required inequality.

My question is, how do I go about finding this lower bound for $|Q|$? I have $|B| \geq \dfrac{2}{5} |A|$ but I don't see $|Q| \geq |B|$.