Homework Help: Graph theory proof

1. Mar 6, 2016

TheMathNoob

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

File size:
39.3 KB
Views:
108
2. Mar 6, 2016

Office_Shredder

Staff Emeritus
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?

3. Mar 6, 2016

TheMathNoob

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.

4. Mar 8, 2016

Office_Shredder

Staff Emeritus
You have to prove that $\sigma$ acts as a bijection on the vertices of G. I am telling you that the definition of a permutation on a finite set (how $\sigma$ 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.