# The set of isomorphisms from a right coset of the automorphism group $Aut(X)$ in $S_n$.

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?

Example:-

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$.

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