How do I prove that neighbor-swap graphs of permutation have Hamiltonian cycle?

Question

Let $G$ be a graph that each vertex of $G$ is a permutation of numbers from $1$ to $n$. Vertices $u$ and $v$ are connected if and only if permutation of $v$ can be obtained by swapping two neighbors in $u$'s permutation. Prove that this graph has a Hamiltonian cycle.

Answer 1

The Steinhaus–Johnson–Trotter algorithm (aka plain changes on bell towers) generates a Hamiltonian cycle on $G$. Following the description on Wikipedia:

We start with the list of two two-element permutations $12,21$. We then put a $3$ to the right of $12$ and move it right to generate new permutations, then move it back through the $21$ permutation. This generates a Hamiltonian cycle on $3$-element permutations with only adjacent swaps: $123,132,312,321,231,213$. And we can continue this way with higher numbers of elements – the key is to weave the new element back and forth, one direction per smaller permutation, alternating between them.