Unable to get to all permutations after $n-1$ transpositions Problem: Give an example of a permutation of the first $n$ natural numbers from which it is impossible to get to the standard permutation $1,2,\ldots,n$ after less than $n-1$ transposition operations (i.e switching the place of two elements).
My attempt
Suppose we have a permutation $T$ and we perform one transposition on $T$ to get $T'$. That would mean $T(i) = j, T(i') = j'$ and $T'(i) = j' , T'(i') = j$ for some $i,j,i',j'$. It is easy to see that the permutation T contains 2 cycles (may be the same): $(i,j,...)$ and $(i',j',\ldots)$. The transposition operation would affect only these two cycles but keep all other cycles intact. Therefore, the number of cycles, if decreased, will not decrease more than $1$.
Now the permutation $[1,2,\ldots,n]$ has n cycles and the permutation $[2,3,\ldots,n,1]$ has 1 cycle only. So it is impossible to use less than $n-1$ operations to get $[2,3,\ldots,n,1]$ from $[1,2,\ldots,n]$. Keeping in mind that getting from permutation A to B is the same as getting from B to A, problem solved.
My question
Is my approach correct and are there any better solutions? Thank you.
 A: Yes, this is correct.  As you observed, the key fact is that hitting a permutation with a transposition $(ij)$ always either decreases or increases the number of cycles by exactly 1.  If the original permutation had $i$ and $j$ in the same cycle, then it splits them (hence increases the number of cycles by 1); if they were in different cycles, it joins them (hence decreases the number of cycles by 1).
This observation about cycles can also be used to prove that the signature of a permutation is well-defined.
A: There is a quantifiable sense in which permutations with more motion require more transpositions to achieve.
For a sequence of transpositions of pairs in a set $S$, build an undirected graph, with vertices $S$ and an edge between every pair that is exchanged at some time in the sequence. 
The vertex sets of the connected components of this transposition graph are permuted within themselves.  To reach all permutations the entire graph must be a single component.  This requires at least $n-1$ edges for $n$ vertices (at minimum, a tree).
This assumes that the transpositions can be chosen to fit the permutation one wants to achieve.   If there are $n-1$ transpositions given, then although any permutation can be reached using a chain of those transpositions, the length of the chain can be as high as $n(n-1)/2$, the number of exchanges of adjacent elements needed to reverse the order of an array of $n$ distinct objects.
Same argument shows that $\frac{n-1}{k-1}$ cycles of length $k$ are needed to sort arrays of length $n$. 
