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?