For any set $X$, let $[X]^2=\{\{a,b\}:a\neq b \in X\}$. If $n\in\mathbb{N}$ is a positive integer, let $S\_n$ denote the collection of bijections $\varphi:\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$. Let $E\_n\subseteq [S\_n]^2$ be given by $$E\_n = \{\{\varphi, \psi\}: \varphi, \psi \in S\_n\text{ and } (\exists a\neq b\in \{0,\ldots,n-1\}) \varphi = (a\, b)\circ \psi\},$$ where $(a\,b)$ denotes the transposition of the elements $a$ and $b$.


Does $(S\_n,E\_n)$ contain a Hamiltonian cycle for every $n\in\mathbb{N}$? If not, does it contain a Hamiltonian path?



Hamiltonian cycle in $S_n$ with transpositions
Yes, $(S\_n, E\_n)$ contains a Hamiltonian cycle for every $n \geq 3$. This follows by the [Steinhaus–Johnson–Trotter algorithm](https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm). The transpositions can even be chosen to be consecutive elements in the previous permutation.


