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

Question

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 ?

Answer 1

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