On proof of upper bound on vertex cover of a connected graph

211 Views Asked by At

Allo, consider the following proof, enter image description here I don't understand the claim that if $X$ is a vertex cover for $G'$, then $X\cup \{w\}$ is a vertex cover for $G$.

Consider the following example, let $G$ be: enter image description here

Here is one of its spanning tree: enter image description here

Let $w$ be vertex $3$. Then vertex set $\{0\}$ is a vertex cover for $G'$, but $\{0,3\}$ is not a vertex cover for $G$. Is the proof correct? How do you prove it?

1

There are 1 best solutions below

0
On

You don't hit that case in your example. Both nodes 2 and 5 have degree 2 in $G$.