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

    Office_Shredder

    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

    Office_Shredder

    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 Discussions: Graph theory proof
  1. Graph theory trail proof (Replies: 11)

  2. Graph Theory Proof (Replies: 3)

Loading...