# why does the poly-time reduction from dominating set to vertex cover require adding a vertex to every edge?

I'm trying to understand a poly-time reduction proof from dominating set to vertex cover. If I'm understanding correctly, it goes something like this: suppose we have a vertex cover of size $$k$$ in graph $$G$$. Then we construct a new graph $$G^\prime$$ with the same vertices and edges, except for every edge $$(u,v)$$ we add a new vertex $$w_{uv}$$, which has an edge to both $$u$$ and $$v$$.

Then, here's the oddest part: it says that if there's some dominating set in $$G^\prime$$ that includes any of the $$w_{uv}$$, then we can construct another dominating set, that's at least as good, by replacing that $$w_{uv}$$ with either $$u$$ or $$v$$. That is, we end up not including any of the $$w_{uv}$$ at all, and thus the dominating set in $$G^\prime$$ is the vertex cover in $$G$$ plus any remaining isolated vertices not in the cover.

This raises the obvious question: what's the point of $$w_{uv}$$ if we're gonna include them and then argue that the original $$u$$ and $$v$$ can render them obsolete anyway? The proof in the link above conspicuously does not explain this. If the dominating set of $$G^\prime$$ doesn't even include $$w_{uv}$$, and the vertex cover dominates just fine (except for the isolated vertices, which are trivial and have nothing to do with $$w_{uv}$$), why even add the $$w_{uv}$$? Why does the proof fail if we never introduce the $$w_{uv}$$ at all?

The key reason we need $$w_{uv}$$ is because not every dominating set is necessarily a vertex cover, but $$w_{uv}$$ "patches" that up.
In particular, assume isolated vertices can be ignored. Then every vertex cover is a dominating set, but not every dominating set is a vertex cover. Hence, if we tried to do the reduction without adding $$w_{uv}$$, then only one direction would work: we can show that if $$G$$ has a vertex cover of size $$k$$, then $$G$$ also has a dominating set of the same size. However, the converse is not true; only by adding the $$w_{uv}$$ does every dominating set of $$G^\prime$$ necessarily dominate the $$w_{uv}$$ as well, and thus cover all edges in $$G$$.