Advanced High-School Mathematics

SECTION 4.2 Basics of Group Theory 241

for any two vertices, call themx 1 andx 2 , there is always an automor-
phismσwhich carries one to the other. This is certainly a property of
the graph—such graphs are calledvertex-transitivegraphs. A simple
example of a non vertex-transitive graph is as follows:

@ @ @ @ @ @ @

v v@@

v v

4

1

3

2

Graph A

Since vertex 1 is contained in three
edges, and since vertex 2 is contained
in only two, it is obviously impossible
to construct an automorphism which
will map vertex 1 to vertex 2.

@

@

@

@@

v v

v

v

@

@

@

@@

v v

v

v

6

1

5

(^23)

4

7 8

Graph B

The graph to the right doesn’t
have the same deficiency as the
above graph, and yet a moment’s
thought will reveal that there
cannot exist an automorphism
which carries vertex 1 to vertex
2.

The following result is fundamental to the computation of the order
of the automorphism group of a vertex-transitive graph.^14 Its usefulness
is that it reduces the computation of the size of the automorphism group
of a vertex-transitive graph to the computation of a stabilizer (which
is often much easier).

Theorem. Let G be the automorphism group of a vertex-transitive
graph having vertex setX. Fixx∈X and letGxbe the stabilizer in
Gofx. Then|G|=|X|·|Gx|.

Proof. LetH be the stabilizer inG of the fixed vertexx: H={σ∈
G| σ(x) = x}. Recall the equivalence relation on G introducted in
Subsection 4.2.7, namely

(^14) I have used this result many times in my own research!