First of all, suppose . Then for all , so for any particular g, we have zg = gz, that is for every . Well that part was easy.
On the other hand, if z is in EVERY , it commutes with every g in G, so . Done deal.
(one small niggling point remains: one ought to show that the intersection is non-empty, so that it actually defines a group. The identity, however, comes to our rescue, here).
As a practical measure, it is more efficient to find elements that don't commute. For example, with we have that , whereas so the center doesn't contain any transpositions.
This means that can have at most 110 elements, so (by Lagrange) at most 60 elements.
In fact, the centralizers of transpositions are a good place to start. Can you prove that has 12 elements? This would show that the center can have no more than 12 elements, a considerable improvement over 60.
Can you show that has order 4? Together with the first result above this shows the center has at most order 2. Then you just need to find ONE permutation that doesn't commute with (1 2)(4 5)....