# Vertex cover of minimal graph

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.

• I thought about edge cover, maybe this is the solution? Feb 25, 2021 at 7:49
• No, I checked it and it looks like not related to edge cover Feb 25, 2021 at 9:04

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

• I'm not sure that you're right, a basic example, cube with one additional vertex. G={V,E}, V={1,2,3,4,5}, E={{1,2},{2,3},{3,4}.{4,5}, {5,2}}, have only one vertex cover U={2,4} same as E'={{1,2},{2,3},{3,4},{4,5}}. Feb 25, 2021 at 23:54
• The are many vertex covers of your example graph. A trivial one different from $\{2,4\}$ is $V$ itself. Feb 25, 2021 at 23:56
• Thanks, I'll check how the original question was defined but only tomorrow. Are solution right but too trivial. Feb 26, 2021 at 0:02
• Thank you @Steven, but I think you wrong. $G=\{V,E\}, V=\{1,2,3,4\}, E=\{ \{1,2\},\{2,3\},\{3,4\},\{4,1\},\{1,3\},\{2,4\}\}$ have same vertex cover as $E'=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$ or I missed something Feb 26, 2021 at 10:46
• @ChaosPredictor. It's never stated in your question that $G'$ must be a subgraph of $G$, so I didn't assume it. Feb 27, 2021 at 21:15