Vertex cover curiosity

31 Views Asked by At

Suppose we have a graph $G = (V, E)$ and a vertex cover $S$ of size $k$ for the graph. Let $\Gamma(v)$ denote the neighborhood of $v$. Is it true that $$S = \bigcup_{v \in V \setminus S} \Gamma(v)$$

In other words, is $S$ the union of the neighborhoods of vertices not in the vertex cover?

1

There are 1 best solutions below

0
On

Not necessarily, for instance for $S=V$.