# How to prove that generating set for $S_n$ contain at least $n -1$ transpositions?

Given a Symmetric group $S_n$, I need to find the smallest generating set for $S_n$. I know it is given by $\langle S_n\rangle$, where

$$\langle S_n \rangle = \{(12),(13), \cdots,(1 n)\}$$ There are $n$ many transpositions in the generating set $\langle S_n \rangle$.

I know there are many generating sets for $S_n$, but I am only interested in those that contains only transpositions. For example $S_n = \langle(1 2),(12\cdots n)\rangle$ is also a generating set for $S_n$ but it is not valid according to my problem.

My Question : How to prove that generating set for $S_n$ contain at least $n - 1$ transpositions ?

• $S_n=\langle(1\,2),(1\,2\,3\,\ldots\,n)\rangle$, so one transposition (and a cyclic premutaion) suffice ... – Hagen von Eitzen Jul 3 '17 at 6:27
• @HagenvonEitzen I believe OP is looking for a generating set of transpositions, but the question is definitely unclear. – diracdeltafunk Jul 3 '17 at 7:07
• @Hagen von Eitzen and diracdeltafunk In the question I have mentioned that transposition not cycle – user275490 Jul 3 '17 at 7:11
• @ diracdeltafunk What is thing that is unclear to you ? – user275490 Jul 3 '17 at 7:12
• Please separate items in a list with commas. Otherwise people are entitled to read them as products. So, for example, $(12)(13)$ is not a list of two transposition, but rather their product $=(132)$. – Jyrki Lahtonen Jul 3 '17 at 7:53

Think of transpositions as edges in a graph with vertex set $\{1,2,\ldots,n\}$. For the transpositions to generate $S_n$, this graph must be connected.