Question. Assume that $\tau_i$ are transpositions in $S_n$. Prove that if $\langle \tau_1, \dots \tau_k \rangle = S_n $, then $k \geq n-1$.
My attempt. I know that $\langle (1 \; 2), \dots (1 \; n) \rangle = S_n $, and I want to substitute $\tau_i$ by these elements. We now that $(1 \; m) \in \langle \tau_1, \dots \tau_k \rangle$ for each $ 1 \leq m \leq n $. Assume that $m$ is the smallest integer between $2$ and $n$ that $(1 \; m) \notin \{\tau_1, \dots, \tau_k\}$.
$$(1 \; m) = \tau_{i_1} \dots \tau_{i_s} $$
That $\tau_{i_a} \in \{\tau_1, \dots, \tau_k\} $ for all $ 1 \leq a \leq s$. These transpositions should send $1 $ to $m$, so there is the following series between them:
$$(1 \; a_0), (a_0 \; a_1), \dots ,(a_t \; m)$$
In the way that it is the smallest series in the $\{\tau_{i_1}, \dots, \tau_{i_s} \}$. I mean that $a_j \neq m$ for all $1 \le j \le t$.
Moreover, these transpositions in the $\{\tau_{1}, \dots, \tau_{k}\}$ are enough to generate $(1 \; m)$ too.
$$
\begin{equation}
(1 \; m) = (1 \; a_0)(a_0 \; a_1) \dots (a_{t-1} \; a_t)(m \; a_t)(a_t \; a_{t-1}) \dots (a_0 \; 1)
\end{equation}\tag{1}\label{eq1}
$$
By the use of \ref{eq1}, we can substitute $(m \; a_t)$ by $(1 \; m)$. We can continue this method, and substitute some elements of $\tau_i$ by $(1 \; m)$. This means that we should have more than equally $n-1$ elements in $\{\tau_1, \dots, \tau_k\}$.
$$
\begin{equation}
(m \; a_t) = (a_{t-1} \; a_t) \dots (a_0 \; a_1)(1 \; a_0)(1 \; m)(a_0 \; 1) \dots (a_t \; a_{t-1})
\end{equation}\tag{2}\label{eq2}
$$
HINT:
If you join the vertices $1$, $\ldots$, $n$ with the edges corresponding to your transpositions, you get a graph with $n$ vertices and $< n-1$ edges, and so a graph that is not connected.