# Does a Vertex Cover exist?

This should be a simple question, but I am a little bit confused.

A proof on page 556 of Algorithm Design says:

"Let $$e=(u, v)$$ be any edge of $$G$$. The graph $$G$$ has a vertex cover of size at most $$k$$ if and only if at least one of the graphs $$G-\{u\}$$ and $$G-\{v\}$$ has a vertex cover of size at most $$k-1$$."

But when I try the following example where the black ball shows a vertex cover, it seems to be faulty statement. Because $$k$$ remains as $$k$$ (not $$k-1$$) even after deletion of vertex $$u$$. Moreover, if I delete the vertex $$v$$, there would be no vertex cover left.

What is wrong about my deduction and example?

## 1 Answer

If you delete the vertex $$v$$, then there are no edges left at all, and so there is a vertex cover of size $$0 \leq k-1$$.

Why is the statement true in the first place? Suppose that $$G$$ has a vertex cover $$C$$ of size $$k$$. Since $$(u,v)$$ is an edge, $$C$$ must contain at least one of $$u,v$$, say $$v$$. I claim that $$C \setminus v$$ is a vertex cover of $$G \setminus v$$, from which the statement immediately follows. Indeed, let $$(a,b)$$ be any edge of $$G \setminus v$$. Then $$(a,b) \in G$$, and so $$C$$ contains one of $$a,b$$, say $$a$$. By construction, $$a \neq v$$, and so $$a \in C \setminus v$$.