Vertex cover of minimal graph

Question

I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ iff they are vertex cover of $G'$.
I understood that a polynomial algorithm exists, it's mean without finding the vertex cover of $G$, but I found only a non-polynomial one.

Answer 1

The algorithm to compute $G'$ is really easy: just return $G$.

Indeed, given any $G=(V,E)$ the only graph $G'=(V, E')$ such that $U \subseteq V$ is a vertex cover of $G$ iff $U$ is a vertex cover of $G'$ is $G$ itself.

To prove this you can show that we must simultaneously have $E \subseteq E'$ and $E' \subseteq E$.

Proof that $E \subseteq E'$: Suppose towards a contradiction that $E \nsubseteq E'$. Then $\exists (u,v) \in E \setminus E'$. The set $U = V \setminus \{u,v\}$ is a vertex cover for $G'$ but not for $G$.

Proof that $E' \subseteq E$: Suppose towards a contradiction that $E' \nsubseteq E$. Then $\exists (u,v) \in E' \setminus E$. The set $U = V \setminus \{u,v\}$ is a vertex cover for $G$ but not for $G'$.