# Reduction Vertex cover into Dominating Set

I have a question to the reduction from Vertex Cover into Dominating Set.

So my lecture says if I have a undirected Graph $$G = (V,E)$$ where $$S \subseteq V$$ is a vertex cover. Then we construct a new graph $$G'$$ which has the same vertices of G, except the isolated ones. For each edge $$\{u,v\}$$ in $$G$$, we add a new vertex that is connected with $$u,v$$.

So my question is, why I have to form every edge into triangles? Why is it not enough to only remove the isolated vertices?

Every vertex cover without isloated vertices is a dominating set at the same time

Remember that you also have to care for the reverse direction. In this case, you should see whether every dominating set is also a vertex cover (hint: no, but why?).

• But why not? Do you have an example graph where this construction is false? I think its the size of the VC/DS or not? – Marc Feb 6 at 19:17
• @Marc Try something like a small complete graph or a small path if those would work. – Juho Feb 6 at 20:49