A frequent problem is to order all permutations of a given set in such a way that two subsequent permutations differ by only a transposition. Show that this problem leads to the question whether a certain graph is Hamiltonian. Draw the graph for the case n = 3. The problem of finding Euler tours has complexity Θ(|E|): we have provided an algorithm with this complexity, and obviously each algorithm for this problem has to consider all the edges to be able to put them into a sequence forming an Euler tour.