This is the problem 6.9 on I. Martin Isaacs book Algebra: A Graduate Course.
Suppose that $g \in S_n$ is an $m$-cycle (i.e., $g = (a_1, a_2, \cdots, a_m)$) and $g = t_1t_2\cdots t_k$, where the $t_i$ are transpositions. Show that $\{ t_i | 1 \le i \le k \}$ contains at least $m-1$ different permutations.
It's not hard to show that $k \ge m - 1$, and that's indeed a theorem mentioned in the book.
My idea is to use induction by noticing that $tgt = g^t$, and the conjugation of each transposition is also a transposition. This approach works for the case $k = m-1$, but I could not go further.
Thanks in advance!
Suppose that you have $r\le m-2$ transpositions $t_i$ in $S_n$. Consider a graph defined as follows. The vertex set is $\{1,2,\ldots,n\}$ and there is an edge from $a$ to $b$ iff $(a\,b)$ is one of the $t_i$. This graph has $\le m-2$ edges, so each component has at most $m-1$ vertices. If $H$ is the subgroup generated by the $t_i$ then each $t_i$ fixes each component of the graph, and so $H$ does too. Therefore each orbit of $H$ has size at most $m-1$, and so $H$ cannot contain an $m$-cycle.