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.

  • $\begingroup$ Hey, I am learning from the same book. What did you think? I have not done any group theory or abstract algebra, but so far, it seems like it would be helpful. $\endgroup$ – user170141 Sep 1 '14 at 5:02
  • $\begingroup$ @user170141: I found another proof and have written it here if you are interested: notesonmathematics.wordpress.com/2013/10/09/graph-automorphisms $\endgroup$ – Shahab Sep 2 '14 at 16:05

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).

  • $\begingroup$ I am having trouble understanding what you mean by the last sentence. Do you mean to say that the automorphism that fixes {1,2} and its three neighbors is the identity automorphism? If so, why? Also, if you mean that the automorphism we are left with is non-identity then I dont see any way to determine it uniquely from a permutation of $S_5$. (Eg both (1) and (12) work upto fixing 12 and its neighbors, that doesnt mean the automorphism we are left with is induced by them though.) $\endgroup$ – Shahab May 18 '11 at 11:43
  • $\begingroup$ @Shahab: I did not (mean to) say that an identity that fixes $\{1,2\}$ and its three neighbors must be the identity. What I tried to say was that if you take an automorphism $\phi$, and you can find an automorphism $\psi$ that "comes from" a permutation of $\{1,2,3,4,5\}$ and is such that $\psi\circ\phi$ is the identity, then that means that $\phi=\psi^{-1}$, so $\phi$ also "comes from" a permutation. We do this by first composing with a suitable automorphism from $S_5$ so that $\sigma_1\phi$ fixes $\{1,2\}$; then (cont...) $\endgroup$ – Arturo Magidin May 18 '11 at 15:22
  • $\begingroup$ @Shahab: (cont) compose with some other suitable automorphism so that $\sigma_2\sigma_1\phi$ fixes $\{1,2\}$ and $\{3,4\}$; then another one so that $\sigma_3\sigma_2\sigma_1\phi$ fixes $\{1,2\}$ and its three neighbors. And keep doing that until you get a composition that fixes everything. Sorry if that wasn't clear. $\endgroup$ – Arturo Magidin May 18 '11 at 15:23
  • $\begingroup$ @Arturo Magidin: Yes, I had guessed by now thats what you had meant. But now I have a further doubt. It seems to me that we have initially a monomorphism from $S_5$ to Aut(Petersen graph) and we are using that in the last stages. That the map is an injection is clear from your post but why will it be a homomorphism? $\endgroup$ – Shahab May 18 '11 at 17:07
  • 1
    $\begingroup$ @Shahab: We actually started by giving a homomorphism from $S_5$ to the permutation group of the vertices; that this is a homomorphism is, I hope, clear. Then we saw that in fact the permutation of the vertices that we obtain is an automorphism of the Petersen graph (note that the automorphism group of the Petersen graph is a subgroup of the group of permutations of the vertices). So the image of $S_5$ inside the group of permutations of the vertices is contained in the automorphism group of the Petersen graph; so we have a homomorphism from $S_5$ to the automorphism group. $\endgroup$ – Arturo Magidin May 18 '11 at 17:12

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

  • $\begingroup$ I think he is looking for the proof sketched on page one. $\endgroup$ – Listing May 18 '11 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.