How to prove a permutation group of degree n can be generated by (at most) n-1 elements?

Given a subgroup G of $S_n$. I want to prove that G can be generated by (at most) n-1 elements.

All my ideas so far seem irrelevant. A hint would be greatly appreciated.

My attempts so far: n-1 reminds me of the number of transpositions required to generate $S_n$, so I'm trying to generalize that, but with no success.

-
 What have you tried? – Graphth Apr 9 '11 at 13:56

You might be interested to know that Peter M. Neumann proved that, with the exception of the symmetric group of degree 3 (which requires 2 generators), every subgroup of $S_n$ can be generated by at most $n/2$ elements. This result is sharp, because (for $n$ even), the group generated by the $n/2$ transpositions $(1,2), (3,4), \ldots, (n-1,n)$ cannot be generated by fewer elements.
I don't think Neumann ever published his proof, but there is a sketch of it in Section 4 of the paper Chains of subgroups in symmetric groups" by P. Cameron, R. Solomon and A. Turull, J. Algebra 127, 340-352, 1989.