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$
    – Leen Droogendijk
    Commented Oct 16, 2015 at 14:42

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .