0
$\begingroup$

Show that the inverse of an isomorphism of graphs is also an isomorphism of graphs.

So I just started a graph theory course and am having a little trouble with one of the problems on the homework. I know that a graph is isomorphic if there are bijections Θ:V(G)→V(H) and Φ:E(G)→E(H) such that Ϯ_G(e)=uv if and only if Ϯ_H(Φ(e))=Θ(u)Θ(v). That is, they have the same structure, but differ only in the names of the vertices and edges. I just don't know how to find the inverse of an isomorphic graph. Any help would be great thanks.

$\endgroup$
  • 3
    $\begingroup$ Hint: Since $\Theta$ and $\Phi$ are bijections, thus they have inverses $\Theta^{-1}$ and $\Phi^{-1}$. So you just have to show that $I_H(e) = uv$ iff $I_G(\Phi^{-1}(e)) = \Theta^{-1}(u)\Theta^{-1}(v).$ Also, you're not trying to find the inverse of an "isomorphic graph," so much as an inverse of a graph isomorphism. $\endgroup$ – goblin Jan 13 '14 at 21:19
  • $\begingroup$ So since Θ and Φ are bijections, they have inverses Θ^(−1) and Φ^(−1). But how do I show that I_H(e)=uv iff I_G(Φ^(−1)(e))=Θ^(−1)(u)Θ^(−1)(v)? This is my first homework so if you could just explain it to me, I would really appreciate that. Thanks $\endgroup$ – Brian Jan 13 '14 at 22:05
  • $\begingroup$ Sure, I just wrote up an answer. Its not especially well-written though, so I suggest you put it into your own (probably better) words before handing it in. $\endgroup$ – goblin Jan 13 '14 at 22:19
  • $\begingroup$ Thank you, that helped a lot. $\endgroup$ – Brian Jan 13 '14 at 23:03
1
$\begingroup$

Since $\Theta$ and $\Phi$ are bijections, thus they have inverses $\Theta^{-1}$ and $\Phi^{-1}$.

Now let $e$ denote an edge of $H$ and $u,v$ denote vertexes. All that remains is to show the following equivalence. $$I_H(e)=uv \iff I_G(\Phi^{−1}e)=(\Theta^{-1}u)(\Theta^{-1}v).$$

We proceed by a sequence of equivalences.

  1. $I_H(e)=uv$
  2. $I_H(\Phi \Phi^{-1}e) = (\Theta\Theta^{-1}u)(\Theta\Theta^{-1}v)$
  3. $I_G(\Phi^{-1}e) = (\Theta^{-1}u)(\Theta^{-1}v)$

A bit of explanation: we got from Line 1 to Line 2 by using the very definition of inverse functions, whereas we got from 2 to 3 by using the equivalence (the iff) given in the question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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