# Graph Isomorphism: Polynomial time reduction from GI for disconnected graphs to GI for connected graphs? [closed]

Let the Graph Isomorphism Problem be the problem to decide whether there is a one-to-one mapping between the vertices of two graphs that preserves the edge relations.

Let the Graph Isomorphism Problem for Connected Graphs be the problem to decide whether there is a one-to-one mapping between the vertices of two connected graphs that preserves the edge relations.

Is there a polynomial time reduction from the Graph Isomorphism Problem to the Graph Isomorphism Problem for connected graphs? How can I prove it?

• This is not a research-level question so is off-topic, here. Computer Science Stack Exchange would have been a more appropriate place to ask but, since the question has already been answered, there's no need to repost there. – David Richerby Nov 22 '13 at 18:31
• Sorry. The research-level criterion for questions should be put into the "How to ask" box on the ask page to avoid this from happening. – Nils Wisiol Nov 22 '13 at 19:02
• Good point. I've suggested it on meta. – David Richerby Nov 22 '13 at 19:16
• The "research-level" requirement is now mentioned both in the "How to ask" box and the greyed out text that sits in the subject line before it's edited. – David Richerby Nov 24 '13 at 9:27

What about the following simple reduction: given graphs $G$ and $H$, let $G' = G * g$ and $H' = H * h$, where $X * x$ is obtained from $X$ by adding a new vertex $x$ and all edges between $x$ and all vertices in $X$ (so, $x$ is universal in $X * x$).
Then $G$ and $H$ are isomorphic iff $G'$ and $H'$ are isomorphic. Note that, in all cases, $G'$ and $H'$ are connected.
• Your reduction doesn't require that $G$ and $H$ have no universal vertex (which is good, since you can't actually assume that). – David Richerby Nov 22 '13 at 18:28