242 CHAPTER 4 Abstract Algebra
σ≡σ′(modH) ⇐⇒σ−^1 σ′∈H.Recall also from Subsection 4.2.7 that the equivalence classes each have
order|H|; if we can count the number of equivalence classes inG, we’ll
be done! Now define a mapping f : G → X by the rule f(σ) =
σ(x). Since the graph is vertex-transitive, we see that this mapping is
surjective. Note that
f(σ) =f(σ′) ⇔ σ(x) =σ′(x)
⇔ σ−^1 σ(x) =x
⇔ σ−^1 σ∈H
⇔ σ≡σ′(modH).In other words, there are exactly as many equivalence classes modH
as there are vertices ofX! This proves the theorem.
We turn now to the computation of the size of the automorphism
groups of the two graphs introduced at the begining of this section. In
order to compute the order of a stabilizer, we re-draw the graph from
the “point of view” of a particular vertex. Thus, consider the following
graphs, where the second emphasizes the role of the vertex 1: