1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory proof

  1. Mar 6, 2016 #1
    1. The problem statement, all variables and given/known data
    The problem is attached. I don't get this part. Let G = Sn be the group of all permutations of S. S is a set, so how can we permute something in a set?. Neither I know if the 4 power in the S is a typo.

    2. Relevant equations

    3. The attempt at a solution

    Attached Files:

  2. jcsd
  3. Mar 6, 2016 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    A permutation is just a function from S to S which is a bijection. I agree the 4 looks like a typo, or perhaps is referencing a footnote?
  4. Mar 6, 2016 #3
    Yes, I have to prove that it is a bijection, but I don't understand how this function acts on the set because as I said, you can't permute things in a set.
  5. Mar 8, 2016 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You have to prove that [itex]\sigma[/itex] acts as a bijection on the vertices of G. I am telling you that the definition of a permutation on a finite set (how [itex]\sigma[/itex] acts on S, not V) is a function that is a bijection.

    For example, suppose that the set is {1,2,3}. Then one permutation f(n) might be f(1) = 2, f(2) = 3, f(3) = 1. Another might be f(1) = 1, f(2) = 3, f(3) = 2.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Threads - Graph theory proof Date
Automorphism proof (graph theory) Mar 5, 2016
Graph Theory Proof Jan 5, 2015
Graph Theory - connection proof Sep 24, 2013
Graph theory trail proof Aug 29, 2013
Graph Theory Proof Sep 19, 2011