0
$\begingroup$

Let $G$ and $H$ be isomorphic graphs. Prove that the complements of $G$ and $H$ are isomorphic.

  • 1
    What does "self-complementary both are isomorphism" mean?2012-10-19
  • 2
    This is rather difficult to understand. Can you restate this more clearly?2012-10-19
  • 0
    I edited the question to something that almost makes sense, but am not sure if that resembles the askers intention. Whatever self-complementaries are, they are probably trivially isomorphic for isomorphic inputs.2012-10-19
  • 0
    sorry for bad english.2012-10-20
  • 1
    "prove that the complements of G and H are isomorphic" is true.2012-10-20
  • 0
    I vote to NOT close and I ask any one voting to close to cancel my vote. This is a perfectly acceptable question and it was extremely easy for me to tell what was being asked and the OP has confirmed that what I guessed was correct.2012-10-20
  • 0
    I repeat, any one who wants to close this question should CANCEL my vote, and NOT actually vote to close, because my vote is AGAINST closing. This is such a stupid system. You can't even see my comments.2012-10-20
  • 0
    @Graphth - is it me or does the question say assume $P$ and prove $P$ ? "Let G and H be isomorphic graphs" but we want to prove "Prove that G and H are isomorphic"2012-10-20
  • 0
    @Belgi Yes, that was my bad. Thanks. In the comments, I asked the OP if he meant that the complements were isomorphic. OP responded and said yes. So, I edited the question to add that and somehow I put completely the wrong thing. Now it's fixed. Thanks again.2012-10-20

1 Answers 1

8

I am going to answer the question that I see, which is to "Prove that the complements of $G$ and $H$ are isomorphic." I can't think of any other possible meaning to the question.

You're telling me $G$ and $H$ are isomorphic, so that means there exists a map from the vertices of $G$ to the vertices of $H$ such that $u$ is adjacent to $v$ in $G$ if and only if $f(u)$ is adjacent to $f(v)$ in $H$.

So, now you want to know if the complements of $G$ and $H$ are isomorphic?

Hint 1: If $u$ and $v$ are adjacent in $G$, what is true about $u$ and $v$ in the complement of $G$? Or, if $u$ and $v$ are not adjacent in $G$, what is true about $u$ and $v$ in the complement? Similarly, with $H$.

Hint 2: Use the same $f$ you already know exists since $G$ is isomorphic to $H$.