The Question:

Let $G$ be a graph such that $1≤d_G(v)≤k$ for all vertices $v$. Show that $G$ has a matching with at least $\frac{|V(G)|}{2k}$ edges.

My Attempt:

Unfortunately, I don't know too much about graph theory, and I basically only know the definitions. So it would be great if anyone could point out any theorems that might help.

Looking at the question, I think that we need only consider connected graphs, for otherwise we can consider the connected components individually.

Also, I guess "at least $\dfrac{|V(G)|}{2k}$ edges" is the same as "at least $\dfrac{|V(G)|}{k}$ vertices"?

And from here how should I proceed? Would considering a spanning tree help in any way?

Thanks in advance


1 Answer 1


Consider a maximal matching, and suppose it has $s$ edges, or also said $2s$ vertices. The matching is maximal, so any other vertex is connected to one of the $2s$ vertices, otherwise there would be another edge that can be added to the matching.

This means that the total number of vertices is at most $2ks$ since every vertex can be connected to at most $k$ other vertices. It means $$|V|\le 2ks \implies s\ge \frac{|V|}{2k}$$

  • 1
    $\begingroup$ Your answer shows that and it also shows $s \geq \frac{|E|}{2k}$ too...Nice! $\endgroup$
    – Mike
    Commented May 3, 2018 at 19:40

You must log in to answer this question.

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