<p>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$). </p>

<p>Then $G$ and $H$ are isomorphic iff $G'$ and $H'$ are isomorphic. 
Note that, in all cases, $G'$ and $H'$ are connected. </p>

CC BY-SA 3.0
2013-11-22T18:28:24.850Z
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
CC BY-SA 3.0
2013-11-22T18:35:50.020Z
Oh, yes, you are right.
user13667
CC BY-SA 3.0
2013-12-01T18:57:37.800Z
We don't answer undergraduate homework level questions on this site.
Kaveh
CC BY-SA 3.0
2013-11-22T18:05:50.920Z
2013-11-22T19:30:42.610Z
2013-11-22T19:30:42.610Z
user13667
<p>Let the <em>Graph Isomorphism Problem</em> be the problem to decide whether there is a one-to-one mapping between the vertices of two graphs that preserves the edge relations.</p>

<p>Let the <em>Graph Isomorphism Problem for Connected Graphs</em> 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.</p>

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

CC BY-SA 3.0
2013-11-22T18:31:15.367Z
This is not a research-level question so is [off-topic](http://cstheory.stackexchange.com/help/on-topic), here. [Computer Science Stack Exchange](http://cs.stackexchange.com) 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
CC BY-SA 3.0
2013-11-22T19:02:09.297Z
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
CC BY-SA 3.0
2013-11-22T19:16:40.810Z
Good point. I've [suggested it on meta](http://meta.cstheory.stackexchange.com/questions/2739/mentioning-research-level-in-how-to-ask).
David Richerby
CC BY-SA 3.0
2013-11-24T09:27:53.820Z
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
<graph-theory><reductions><graph-isomorphism>
Graph Isomorphism: Polynomial time reduction from GI for disconnected graphs to GI for connected graphs?
Nils Wisiol
# Graph Isomorphism: Polynomial time reduction from GI for disconnected graphs to GI for connected graphs?

(Asked by: username_0 on 2013-11-22)

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?

**Tags:** graph-theory, reductions, graph-isomorphism
> **Comments:**
> **username_1**: This is not a research-level question so is [off-topic](http://cstheory.stackexchange.com/help/on-topic), here. [Computer Science Stack Exchange](http://cs.stackexchange.com) would have been a more appropriate place to ask but, since the question has already been answered, there's no need to repost there.  
> **username_0**: 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.  
> **username_1**: Good point. I've [suggested it on meta](http://meta.cstheory.stackexchange.com/questions/2739/mentioning-research-level-in-how-to-ask).  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-11-22. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_1**: Your reduction doesn't require that $G$ and $H$ have no universal vertex (which is good, since you can't actually assume that).  
> **username_2**: Oh, yes, you are right.  
> **username_3**: We don't answer undergraduate homework level questions on this site.  

---

