2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Oct 16 '15 at 14:42
2
$\begingroup$

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.

Now use K\"onig's theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.