# Matching in a Bipartite Graph of Specific Degrees

Let $G$ be a bipartite graph such that for all vertices $v\in V(G)$, we have $3\leq\deg(v)\leq k$, where $k\geq3$ is an integer. Show that $G$ contains a matching of size at least $\frac{3|V(G)|}{2k}$.

I'm thinking that since a perfect matching for bipartite graph is of size $\frac{|V(G)|}{2}$, the factor $\frac{3}{k}$ (which is $\leq1$) has to come from somewhere, but so far doesn't have any idea. Am I just plain wrong in my approach? Or am I missing something?

• This is a weird formula: if you take a fixed number of vertices and add at least one edge to every vertex (preserving bipartiteness), you expect the guaranteed size of a matching to increase. In this formula however it increments $k$ so the guaranteed size of a matching becomes smaller! Oct 16 '15 at 14:42

Each vertex can cover at most $k$ edges, so a minimum vertex cover requires at least $\frac mk$ vertices (where $m$ is the number of edges). Since $m\geq\frac{3n}2$ (where $n$ is the number of vertices) by the degree sum formula, it follows that a minimum vertex cover requires at least $\frac{3n}{2k}$ vertices.