Automorphisms of the Petersen graph

I am trying to find out the automorphism group of the Petersen graph. My book carries the hint: "Show that the $\tbinom{5}{2}$ pairs from {1, . . . , 5} can be used to label the vertices in such a way that a simple rule determines when there is an edge. To find the full automorphism group, consider the subgroup that fixes a vertex and its three neighbors."

Accordingly the rule is that there is an edge if 2-sets are disjoint. What I am not getting is to how to use the second sentence of the hint to find the automorphism group. Its not at all clear what the order of such a subgroup will be and how such a subgroup will be the requisite automorphism group.

Also I am not really proficient with group action, so if that is involved I would appreciate a detailed explanation.

Solution 1:

Since each vertex is labeled with a subset with two elements of $\{1,2,3,4,5\}$, then any permutation of $\{1,2,3,4,5\}$ is going to induce a permutation of the vertices. Moreover, if $\{a,b\}\cap\{c,d\}=\emptyset$, and $\sigma$ is a permutation of $\{1,2,3,4,5\}$, then $\{\sigma(a),\sigma(b)\}\cap\{\sigma(c),\sigma(d)\} = \emptyset$. That is: this permutation of the vertices sends adjacent vertices to adjacent vertices (and non-adjacent vertices to non-adjacent vertices).

Also, two permutations induce the same permutation of the vertices if and only if they are identical permutations (you should prove this). That means that every element of $S_5$ induces a distinct automorphism of the graph.

Are these all the automorphisms, or are there more? If $\tau$ is any automorphism, then by composing with an appropriate permutation of $\{1,2,3,4,5\}$ you may assume that the map fixes $\{1,2\}$; that means that the vertices adjacent to $\{1,2\}$, $\{3,4\}$, $\{3,5\}$, and $\{4,5\}$, must map to each other. Composing with an appropriate permutation (that fixes $1$ and $2$) you may assume that the permutation also fixes $\{3,4\}$; and composing again by a suitable permutation, you can make it fix also $\{3,5\}$ $\{4,5\}$ (again, you need to prove this). So then you are left with an automorphism that fixes $\{1,2\}$ and its three neighbors. If you can show that this is also given by a permutation of $\{1,2,3,4,5\}$, then you will have shown that every automorphism "comes" from an element of $S_5$ (since composing with suitable automorphism that do give you the identity).

Solution 2:

Prof. Ravi Vakil has given lecture notes on Complex Algebraic Surfaces, and you can find the proof of your result in the second page.