A Symmetry of a graph X is a permutation of the vertices that also permutes the edges. The distances between vertices are preserved. Show that the symmetries of a graph are a permutation group,

So that means I need to show that the symmetries of a graph have the following properties:

  1. Closure: if a,b are in the set of S then a.b is in the set of S

  2. Associativity: if a,b,c are in the set S then a.(b.c)=(a.b).c

  3. Identity: there exists i in the set S such that i.a=a.i=a for all a in S

  4. Inverse for all a in S there exists an inverse b in S such that a.b=b.a=i

How do I prove any of these properties for the symmetries of a graph? I am really confused. We haven't seen any examples of how to prove these so far.

  • $\begingroup$ This is remarkably similar to the following question, posted less than an hour before your question: math.stackexchange.com/questions/1712309/… Is this a homework problem? $\endgroup$ – A.Sh Mar 25 '16 at 0:19
  • 1
    $\begingroup$ No it's a textbook exercise and the answer my textbook gives is "composition of symmetries is also a symmetry" which makes no sense to me. I'm not even sure how that answers the question and wouldn't one have to prove that that is true. $\endgroup$ – Rosa Mar 25 '16 at 0:25
  • 2
    $\begingroup$ Possible duplicate of permutation group and cycle index question regarding peterson graph $\endgroup$ – Mike Pierce Mar 25 '16 at 0:41
  • $\begingroup$ Ok, it just felt a tiny bit suspicious, sorry :) Ok, as for help, a symmetry is defined as a permutation with specific properties in your post, so composition of symmetries is simply a composition of mappings, i.e. you apply one permutation after the other. You must show that when performing two successive symmetry permutations, the distances between vertices should be preserved at the end, as that is your criteria for a symmetry here. Associativity is just a general property of composition. The identity symmetry is the identity permutation, and inverses are inverse permutations. Got it? $\endgroup$ – A.Sh Mar 25 '16 at 7:31

Your Answer

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

Browse other questions tagged or ask your own question.