TAOCP 2.3.4.1 Exercise 13
Assume first that the graph is connected.
Exercise 13. [**] $$M24$$ Consider a graph with $n$ vertices and $m$ edges, in the notation of exercise 6. Show that it is possible to write any permutation of the integers ${1,2,\ldots,n}$ as a product of transpositions $(a_{k_1}\ b_{k_1})(a_{k_2}\ b_{k_2})\cdots(a_{k_t}\ b_{k_t})$ if and only if the graph is connected. (Hence there are sets of $n-1$ transpositions that generate all permutations on $n$ elements, but no set of $n-2$ will do so.)
Verified: yes
Solve time: 41s
Assume first that the graph is connected. Let $(i,j)$ denote the transposition corresponding to an edge joining vertices $i$ and $j$. Since the graph is connected, for any two vertices $u$ and $v$ there is a path
$$ u=v_0,\ v_1,\ \ldots,\ v_r=v. $$
Then
$$ (v_0,v_1)(v_1,v_2)\cdots(v_{r-1},v_r) (v_{r-2},v_{r-1})\cdots(v_0,v_1) =(u,v), $$
so every transposition $(u,v)$ can be expressed as a product of transpositions corresponding to edges of the graph. Since every permutation of ${1,2,\ldots,n}$ is a product of transpositions, every permutation can therefore be written as a product of the transpositions $(a_k,b_k)$ determined by the edges.
Conversely, suppose the graph is not connected. Let $C$ be a connected component and let $D$ be the set of remaining vertices. Every transposition $(a_k,b_k)$ corresponding to an edge leaves $C$ invariant, because both endpoints of every edge lie in the same connected component. Hence any product of such transpositions also leaves $C$ invariant. A permutation that interchanges a vertex of $C$ with a vertex of $D$ does not leave $C$ invariant, so it cannot be expressed as a product of the given transpositions. Therefore the transpositions associated with the edges generate all permutations if and only if the graph is connected.
A connected graph on $n$ vertices contains a spanning free tree by the argument preceding equation (3). That tree has $n-1$ edges by Theorem A(d), hence $n-1$ transpositions suffice to generate all permutations. Any set of only $n-2$ transpositions corresponds to a graph with $n$ vertices and $n-2$ edges. By Theorem A(e), a connected graph on $n$ vertices must have at least $n-1$ edges; therefore such a graph is disconnected, and the transpositions cannot generate all permutations. ∎