# How are matchings a lower bound for an approximate vertex cover?

I am reading Algorithms by Dasgupta et al and they mention maximal matchings as approximations for vertex cover.

They mention that the 2-approximation ratio is a lower bound. How is a maximal matching a lower bound? Does it mean that it is the lowest approximation value we can get compared to $$\log n$$ of the greedy algorithm that is polynomial?

The images below show the optimal vertex cover = 8 but and a maximal matching of 12.

I decided to find another matching which I later discovered is called a maximum matching from Wikipedia. Since a maximum matching is also a maximal matching, I assume that this the worst that we can get, a maximum matching of 16 vertices.

How can one improve on the edges picked then? My 16 vertices versus the book's 12?

Let $$M$$ be a maximal matching, that is, $$M$$ is a matching which is not contained in a larger matching. Note that $$M$$ need not be a maximum matching, which is a matching of maximal size.
If $$M$$ contains $$m$$ edges, then:
1. Any vertex cover contains at least $$m$$ vertices.
2. There exists a vertex cover containing $$2m$$ vertices, namely, all vertices of the matching.
Indeed, if the vertices of the matching $$M$$ do not form a vertex cover, then there is some edge $$e$$ which is not covered by the vertices of $$M$$, and so $$M$$ is contained in the larger matching $$M \cup \{e\}$$, contradicting the definition of $$M$$.