Lower bound for the size of a maximal matching in a general graph Let $G=(V,E)$ be a graph, let $M\subseteq E(G)$ be a maximal matching, and let $M^\star\subseteq E(G)$ be a maximum matching. Prove that $|M|\ge |M^\star|/2$.
Any hints on how to prove this?
 A: As suggested in the comment, try by contradiction.  I'll give an outline and you can fill in the details.
Suppose that $|M|<|M^{\ast}|/2$.  The edges of $M$ are incident on $2\ell$ vertices and the edges of $M^{\ast}$ are incident on $2k$ vertices.  The inequality then asserts that $2\ell < k$.  Now, if you look at every edge in a maximum matching, at most $2\ell$ edges have at least one vertex in $M$.  This means, since $2\ell < k$ that there is at least one edge in $M^{\ast}$ that has no vertex in $M$... hence that edge can be added to $M$ to make a larger matching.  This implies that $M$ is not maximal.  Contradiciton.
A: I'm just a first year student, but this is how I see it. Criticisms are welcome.
Let $|M| =l$ and $|M^*|= k$.
$V(M)$ and $V(M^*)$ are the sets of nodes covered by $M$ and $M^*$ respectively. Therefore,
$|V(M)| = 2l$ and $|V(M^*)| = 2k$.
.
Since M is a maximal matching, each edge in $E$ covers at least 1 node that $M$ covers.
So each edge in $M^* \subseteq E$ covers at least 1 node that $M$ covers. Note: there are k edges in $M^*$.
Hence, there are k nodes covered by both $M$ and $M^*$, or $V(M) \cap V(M^*) = k$.
Therefore, $V(M)=2l \geq k \leftrightarrow l \geq k/2$.
Therefore, $ |M| \geq |M^*|/2$.
