Given a graph $G(V, E)$, consider the following algorithm:
- Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$)
- Let $v$ be one of the vertices with degree equal to $d$
- Remove all vertices adjacent to $v$ and add them to the proposed vertex cover
- Repeat from step 1. until in $G$ there are only vertices with degree $0$ (no edges in the graph)
At the end the removed vertices are a vertex cover of the given $G(V, E)$, but is it a minimum vertex cover? Is there an example where the algorithm does not find a minimum vertex cover?