Relation between maximal matching and minimum vertex cover

Question

Let $M$ be any maximal matching of $G(V,E)$ and $S^*$ be the minimum vertex cover of $G(V,E)$, how to show $|S^{*}|\leq 2|M|$ where $G(V,E)$ is any unweighted undirected graph

I know $|M|\leq|M^*|\leq2|M|$ if we take $M$ to be the maximum matching of $G(V,E)$, and I thought if I can show $|S^{*}|\leq |M^*|$ then done, but then I found it actually is $|M^*|\leq|S^{*}|$! Someone can help me? Thank you!

Answer 1

Hint: Let $V_M$ be the set of vertices incident with edges of $M$. Since $M$ is maximal, every edge of the graph must be incident to a vertex of $V_m$.

Full proof (click spoiler):

By the hint above, we see that $V_m$ must be a vertex cover of the graph, and $|V_m| = 2|M|$. So the smallest vertex cover $S^*$ has at most $2|M|$ vertices.