208 CHAPTER 4 Abstract Algebra
Aut(G). The most important facts related to graph automorphisms is
the following:
Proposition.The composition of two graph automorphisms is a graph
automorphism. Also the inverse of a graph automorphism is a graph
automorphism.
Proof.This is quite simple. Letσandτ be two graph automorphisms,
and letv andw be vertices of the graph. Thenσ◦τ(v) andσ◦τ(w)
form an edge ⇔ τ(v) and τ(w) form an edge ⇔ v andw form an
edge. Next, letσbe a graph automorphism. Sinceσis a permutation,
it is bijective and so the inverse functionσ−^1 exists. Thus we need to
show that verticesvandwform an edge⇔ σ−^1 (v) andσ−^1 (w) forms
an edge. Ifvandwform an edge, this says thatσ(σ−^1 (v)), σ(σ−^1 (w))
form an edge. But sinceσis an automorphism, we see thatσ−^1 (v) and
σ−^1 (w) form and edge. In other words,
vandwform an edge ⇒σ−^1 (v) andσ−^1 (w) form an edge.Conversely, assume thatσ−^1 (v) andσ−^1 (w) form an edge. Then since
σ is an automorphism, we may applyσ to conclude that the vertices
σ(σ−^1 (v)), σ(σ−^1 (w)) form an edge. But this says thatv andwform
an edge, i.e.,
σ−^1 (v) andσ−^1 (w) form an edge⇒vandwform an edge,which proves thatσ−^1 is a graph automorphism.
The above fact will turn out to be hugely important!
Exercises
- Consider the graph shown below.