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?

enter image description here


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.