-
is transitive on -set if for every , there exists such that -
(Godsil e2.3) If
is a non-trivial transitive permutation group on the set , there is an element of with no fixed points. -
Proof: If
has one orbit (i.e., it is a cycle), then any non-identity element will suffice. Otherwise, by (Fraleigh 9.8) we can construct
with no fixed points. For each , take (which permutes all elements in its orbit) and form by
-
-
(Godsil 3.6.2) Let
be a transitive permutation group on and . and Then
-
Proof: Count the pairs
. For each , there are at least points in so there are at least pairs. Also, the elements of
that map forms a coset of and so there are exactly elements of such that or . Since
is transitive, by the Orbit Stabilizer theorem So
-