The topic I am dealing with right now is a 2-approximation algorithm for the minimum vertex cover. The proof seems fairly simple but I don't understand one assumption that is made.
It is the assumption that the size of a minimal vertex cover is always greater than or equal to the size of a maximal matching.
Imagine a graph with 6 vertices which represents a path like this:
1 – 2 – 3 – 4 – 5 – 6
Here the minimum vertex cover is 2, you get it by choosing the vertices "2" and "5" but the maximal matching could be {(1,2),(3,4),(5,6)} and so the upper assumption doesn't hold. I miss something…
Best Answer
The vertices $\{2,5\}$ do not cover edge $(3,4)$, so $\{2,5\}$ is not a vertex cover.