Let alpha and beta belong to S_n. Prove that (beta)(alpha)(beta^-1) and alpha are both even or both odd.
Notice that $\displaystyle \beta (a_1,a_2) \beta^{-1} = (\beta(a_1), \beta(a_2))$.
Therefore if $\displaystyle \alpha = \tau_1 \cdot ... \cdot \tau_k$ where $\displaystyle \tau_i$ are transpositions then $\displaystyle \beta \alpha \beta^{-1} = (\beta \tau_1 \beta^{-1})(\beta \tau_2 \beta^{-1}) ... (\beta \tau_k \beta^{-1})$. Thus, we see that $\displaystyle \alpha$ and $\displaystyle \beta \alpha \beta^{-1}$ have the same parity.