Let $G$ and $H$ be isomorphic graphs. Prove that the complements of $G$ and $H$ are isomorphic.
Graph Theory, complements of isomorphic graphs are isomorphic
-
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
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$.