-1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Nov 22, 2013 at 18:31
  • 2
    $\begingroup$ 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. $\endgroup$
    – Nils Wisiol
    Nov 22, 2013 at 19:02
  • 2
    $\begingroup$ Good point. I've suggested it on meta. $\endgroup$
    – David Richerby
    Nov 22, 2013 at 19:16
  • $\begingroup$ 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. $\endgroup$
    – David Richerby
    Nov 24, 2013 at 9:27

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your reduction doesn't require that $G$ and $H$ have no universal vertex (which is good, since you can't actually assume that). $\endgroup$
    – David Richerby
    Nov 22, 2013 at 18:28
  • $\begingroup$ Oh, yes, you are right. $\endgroup$
    – user13667
    Nov 22, 2013 at 18:35
  • $\begingroup$ We don't answer undergraduate homework level questions on this site. $\endgroup$
    – Kaveh
    Dec 1, 2013 at 18:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.