Prove or disprove: The minimum number of transpositions needed to decompose $\sigma$ is $n-S$.

amakelov explains why $n-S$ transpositions are sufficient. To show that $n-S$ transpositions are necessary, one proves that for a permutation $\sigma$ and a transposition $\tau$, $\sigma\tau$ has one more, or one fewer cycle than $\sigma$. As the identity permutation has $n$ cycles, a product of $k$ transpositions has at least $n-k$ cycles. So if $k<n-S$, a product of $k$ transpositions has more than $S$ cycles.

It's true because every cycle of length $k$ can be decomposed as the product of $k-1$ transpositions. The way to see that is to observe that $$(1,2,\ldots,k)= (1,2)(2,3)\ldots(k-1,k)$$ which can be checked directly from the formula (each $i$ goes to $i+1$ modulo $k$)