From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , on page 22-

Theorem 4

Let $X$ and $X'$ be two isomorphic graphs with vertex set $V = \{1 ..... n\}$ , Then the set of isomorphisms from $X$ to $X'$ is a right coset of the automorphism group $Aut(X)$ in $S_n$.

Proof: Let$ X = (V,E)$ and $X' = (V,E')$. Let $\tau$ and $\kappa$ be isomorphisms from $X$ to $X'$, and note that they are permutations in $S_n$. Recall that

$(v,w) \in E$ iff $(v^{\tau},w^{\tau}) \in E'$ iff $(v^{\kappa},w^{\kappa}) \in E'$.

Therefore, $\tau \kappa^{-1}$ is an automorphism of $X$. Thus, $\tau$ and $\kappa$ are in the same right coset of$Aut(X)$.

Conversely, let $\tau $ be an isomorphism from $X$ to $X'$, and $\alpha$ an automorphism of $X$. Then $\alpha \tau$ is again an isomorphism from $X$ to $X'$. So, the right coset $Aut(X)$ is theset of all isomorphisms from $X$ to $X'$.

My questions are-

  1. Why $X'$ has $E'$ which is not $E$. Like vertex set$V$, $X'$ should have same edge set $E$,isn't it? if $X'$ has $E'$ then it should have $V'$ because permutation acts on vertices too.
  2. How $\tau \kappa^{-1}$ is an automorphism of $X$
  3. Is there an alternative proof of the theorem?


Let $X = (V,E)$ be a graph with vertices $V = \{ 1,..... 5 \} $,

and edges $E = \{(1,2), (1,4), (2,3), (3,4), (3,5) \}$ .

$X$' the graph $(V,E')$, where $V =\{ 1 ..... 5\}$,

and edges $E' = \{(1,4), (1,5), (2,3), (3,4), (3,5)\}$.

There are two isomorphisms from $X$ to $ X'$, namely $(2,4,5)$ and $(2,5)$.

How $(2,4,5)$$(2,5)^{-1}$ is an automorphism ?

  1. If they had the same edge set, they would be the same graph. We could have $E=E'$, but in general this is not the case. The edge set consists of pairs of vertices, and there's no reason for $E$ and $E'$ to have the same pairs.

  2. $\tau:X\to X'$ is an isomorphism and $\kappa^{-1}:X'\to X$ is an isomorphism. Composing them gives an isomorphism $X\to X$, which is an automorphism of $X$.

I know of no better way to prove something is a right coset than using the definition of a right coset. That doesn't mean there aren't alternative proofs, but this is the simplest one I can see.

For $\tau$ and $\kappa$ to be in the same right coset we need $\kappa^{-1}\tau$ to be an automorphism, not $\tau\kappa^{-1}$. This is an error in the proof above which is probably the source of your confusion. For your example $(2,5)^{-1}(2,4,5)=(2,5)(5,2,4)=(2,5)(2,5)(2,4)=(2,4)$ is indeed an automorphism of $X$.

| cite | improve this answer | |
  • $\begingroup$ What if $\tau \neq \kappa$, for example, $\tau =(123)$ and $\kappa=(456)$, $n >6$, I understand your answer when $\tau = \kappa$. $\endgroup$ – Michael Feb 6 '16 at 19:11
  • $\begingroup$ @Mike if they're equal it's boring and you get the identity. If they're not equal you get a nontrivial automorphism. $\endgroup$ – Matt Samuel Feb 6 '16 at 19:13
  • $\begingroup$ @Mike by the way the point of an isomorphism is that it preserves edges. $\endgroup$ – Matt Samuel Feb 6 '16 at 20:12
  • $\begingroup$ Matt,I have added an example to my question, would you explain a little elaborately a little based on that. Thanks. $\endgroup$ – Michael Feb 7 '16 at 20:42
  • 1
    $\begingroup$ @MikeSQ Please see my edit. $\endgroup$ – Matt Samuel Feb 7 '16 at 21:17

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.