Graph theory intro

Question

For every graph G, prove that (vertex cover of G) is less than or equal to (twice it's matching). I tried a couple of examples and it works but I can't follow a trend to build my proof. Does anybody know how to prove it?

Answer 1

Given any graph $G$, let $M$ be any maximal matching of size $k$. Now let $C$ be the set of all endpoint vertices for all the edges in $M$ (note that since no two edges share a common vertex, $|C| = 2k$). We claim that $C$ is a vertex cover for $G$.

• Otherwise, suppose instead that there exists some edge $e \in E(G)$ that is not incident with any vertex in $C$ (so that $e \notin M$). Then $M \cup \{e\}$ must also be a matching of $G$, contradicting the maximality of $M$.

Hence, we have found a vertex cover of $G$ of size $2k$. So any minimum vertex cover of $G$ must have size at most $2k$ (twice the size of any maximal matching).