# 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?