I am reposting it getting insufficient help from the previous post (Although I got some hint)
Prove that for each $\sigma \in Aut(S_n)$ $n \neq 6$.
$\sigma(1,2)=(a,b_2),\sigma(1,3)=(a,b_3), ...., \sigma(1,n)=(a,b_n)$
for some distinct integers $a,b_1,....b_n \in \{1,...,n\}$.
I was trying the action of $\sigma$ in $S_n=<(i,i+1>$ $i=1(1)n$. But can't get any positive result. So need some help to prove it.
I have proved earlier that when $n≠6$, the size of the conjugacy class of $(1,2)$ is different from that of any other conjugacy class of elements of order $2$ in Sn[This is true because conjugacy classes contains elements of same cycle structure]. That proves that $σ(1,2)=(a,b)$ for some $a,b$. But I didn't know that it will be needed (Thanks to Derek holt). Now what can I do? Because the elements $(1,2),(1,3),....,(1,n)$ can go to any transposition. So what to do next? Can anyone please give me any elaborate proof?
Notice that if $\sigma = (a,b)$ and $\tau=(c,d)$, then the order of the permutation $\sigma\tau$ is $1$ if $\{a,b\}=\{c,d\}$, $3$ if $|\{a,b\} \cap \{c,d\}|=1$ and $2$ if $|\{a,b\} \cap \{c,d\}|=0$.
Now the images under $\sigma$ of $(1,2), (1,3), \ldots,(1,n)$ are all single transpositions and, since automorphisms preserve orders, if $\sigma((1,2))=(a,b)$ and $\sigma((1,3)) = (c,d)$, then we must have $|\{a,b\} \cap \{c,d\}|=1$, so we can assume that $\sigma((1,2))=(a,b_2)$ and $\sigma((1,3)=(a,b_3)$.
Now $\sigma((1,4))$ could be $(b_2,b_3)$, but then there would be no possibility for $\sigma((2,3))$, so you must have $\sigma((1,4)) = (a,b_4)$, etc.