It really all boils down it being true for $n=2$. The rest follows by induction: assume it's true for $S_{n-1}$, which fixes $n$. Let $\sigma \in S_n$, and let $i = \sigma(n)$. If you could write $\sigma$ as a product of both an odd and an even number of transpositions, you could then write $(i \ n) \cdot \sigma$ as a product of both an even and an odd number of transpositions. But $\sigma$ takes $n$ to $i$ and $(i \ n)$ takes it back to $n$, so $(i \ n) \cdot \sigma$ lies in $S_{n-1}$, and must be a product of even or odd numbers of transpositions but not both.

First, let's show it for the identity. Suppose it's not true, and we can write the identity as a product of an odd number of transpositions in some $S_n$. Pick the smallest such $n$, and let the number of transpositions used be minimal. Represent the product as a (singular) braid diagram, with the strings ordered left to right as $1, \ldots , n$, and with each transposition represented by a singular crossing. String $n$ begins to the right of every other string, and, since our product is the identity, it ends to the right of every other string too. This means, for any other string $i$, that $n$ begins and ends on the same (right) side of $i$, and hence (key point!) crosses $i$ an even number of times. Now just pull the $n$-th string out of the braid. This reduces the number of crossings (transpositions in the product) but keeps it even, contradicting the minimality above.

In general, if $\sigma$ is a product of both an odd and an even number of transpositions, we get that $\mbox{id} = \sigma \cdot \sigma^{-1}$ is a product of an odd + even = odd number of transpositions, reducing to the previous case.

My first thought was to do it by induction and trace what happens to $n$. So (first draft) assume it's true for $S_{n-1}$, which fixes $n$. Let $\sigma \in S_n$, and let $i = \sigma(n)$. If you could write $\sigma$ as a product of both an odd and an even number of transpositions, you could then write $(i \ n) \cdot \sigma$ as a product of both an even and an odd number of transpositions. But $\sigma$ takes $n$ to $i$ and $(i \ n)$ takes it back to $n$, so $(i \ n) \cdot \sigma$ lies in $S_{n-1}$, and must be a product of even or odd numbers of transpositions but not both.

As the first commenter below pointed out in like a minute :-) this doesn't get at the main issue, which is that you could have $\sigma \in S_n$ that you can write as both an odd product and an even product in some larger ambient $S_n$. It's really about the base case in the induction, which is the identity: if you can prove that this can't happen for the identity, you've really done it for any $\sigma \in S_n$. (If $\sigma$ is a product of both an odd and an even number of transpositions, we get that $\mbox{id} = \sigma \cdot \sigma^{-1}$ is a product of an odd + even = odd number of transpositions.)

If we stick to looking at the identity, it's clear in principle what happens to $n$: it starts as the last element, and ends there too. So we should be able to pull it out! To help picture this, make one more reduction, which is that it's equivalent to look at odd vs. even products of adjacent transpositions. This is because any transposition is conjugate by a series of adjacent transpositions to an adjacent transposition, and conjugation preserves parity.

All that said, suppose we can write the identity as a product of an odd number of adjacent transpositions in some $S_n$. Pick the smallest such $n$, and let the number of adjacent transpositions used be minimal for that $n$. Represent the product as a (singular) braid diagram, with the strings ordered left to right as $1, \ldots , n$, and with each adjacent transposition represented by a singular crossing. String $n$ begins to the right of every other string, and, since our product is the identity, it ends to the right of every other string too. This means, for any other string $i$, that $n$ begins and ends on the same (right) side of $i$, and hence (here's the whole point!) crosses $i$ an even number of times. Now I hope you see the punch line: pull the string! I.e., pulling the $n$-th string all the way to the right, out of the braid, reduces the number of crossings (adjacent transpositions in the product) if there were any, but keeps it even, contradicting the minimality above.

It really all boils down it being true for $n=2$. The rest follows by induction: assume it's true for $S_{n-1}$, which fixes $n$. Let $\sigma \in S_n$, and let $i = \sigma(n)$. If you could write $\sigma$ as a product of both an odd and an even number of transpositions, you could then write $(i \ n) \cdot \sigma$ as a product of both an even and an odd number of transpositions. But $\sigma$ takes $n$ to $i$ and $(i \ n)$ takes it back to $n$, so $(i \ n) \cdot \sigma$ lies in $S_{n-1}$, and must be a product of even or odd numbers of transpositions but not both.

It really all boils down it being true for $n=2$. The rest follows by induction: assume it's true for $S_{n-1}$, which fixes $n$. Let $\sigma \in S_n$, and let $i = \sigma(n)$. If you could write $\sigma$ as a product of both an odd and an even number of transpositions, you could then write $(i \ n) \cdot \sigma$ as a product of both an even and an odd number of transpositions. But $\sigma$ takes $n$ to $i$ and $(i \ n)$ takes it back to $n$, so $(i \ n) \cdot \sigma$ lies in $S_{n-1}$, and must be a product of even or odd numbers of transpositions but not both.

First, let's show it for the identity. Suppose it's not true, and we can write the identity as a product of an odd number of transpositions in some $S_n$. Pick the smallest such $n$, and let the number of transpositions used be minimal. Represent the product as a (singular) braid diagram, with the strings ordered left to right as $1, \ldots , n$, and with each transposition represented by a singular crossing. String $n$ begins to the right of every other string, and, since our product is the identity, it ends to the right of every other string too. This means, for any other string $i$, that $n$ begins and ends on the same (right) side of $i$, and hence (key point!) crosses $i$ an even number of times. Now just pull the $n$-th string out of the braid. This reduces the number of crossings (transpositions in the product) but keeps it even, contradicting the minimality above.

In general, if $\sigma$ is a product of both an odd and an even number of transpositions, we get that $\mbox{id} = \sigma \cdot \sigma^{-1}$ is a product of an odd + even = odd number of transpositions, reducing to the previous case.