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

Question

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?

Answer 1

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