If $d_G(v)≤k \; \forall \; v \in V(G)$, then there exists a matching with $≥\frac{|V(G)|}{2k}$ edges

Question

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

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}$$