Prove that for \(p\) prime, \(S_p\) is generated by a \(p\)-cycle and a transposition.
Solution
Let \(\sigma\) be a \(p\)-cycle and \(\tau\) a transposition in \(S_p\). We show \[ \langle \sigma,\tau\rangle=S_p. \] After relabeling the underlying set as \(\ZZ/p\ZZ\), we may write \[ \sigma(i)=i+1 \] and \[ \tau=(0\ d) \] for some nonzero \(d\in\ZZ/p\ZZ\).
1. The subgroup \(H=\langle\sigma,\tau\rangle\) contains every transposition\[ (k\ k+d),\qquad k\in\ZZ/p\ZZ. \]
Conjugating \(\tau\) by powers of \(\sigma\) gives \[ \sigma^k\tau\sigma^{-k}=(k\ k+d). \] Since \(\sigma,\tau\in H\), all these conjugates lie in \(H\).
2. The graph on \(\ZZ/p\ZZ\) with edges \(\{k,k+d\}\) is connected.
Starting at \(0\), repeated addition of \(d\) reaches \[ 0,d,2d,\ldots,(p-1)d. \] Because \(p\) is prime and \(d\ne0\), multiplication by \(d\) permutes \(\ZZ/p\ZZ\). Hence these are all \(p\) vertices.
3. Transpositions corresponding to the edges of a connected graph generate the full symmetric group on its vertices.
Fix a root vertex \(v_0\). For any vertex \(v\), choose a path \[ v_0=v_0,v_1,\ldots,v_r=v. \] Then the transposition \((v_0\ v)\) is a product of edge transpositions along the path: \[ (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). \] Thus all transpositions \((v_0\ v)\) lie in the generated subgroup. These star transpositions generate the full symmetric group.
4. Therefore \(H=S_p\).
By 1 and 2, \(H\) contains the edge transpositions of a connected graph. By 3 these generate all of \(S_p\).