The following self-contained post clarifies the definition of symmetry group of a graph (definition 1.14, p. 10-11, and example 1.15, p. 11, in the book “Groups, graphs and trees: an introduction to the geometry of infinite groups” by John H. Meier).
The symmetry group of a graph, also referred to as the automorphism group of a graph, is informally the set of all possible rearrangements of the graph that preserve its edge-vertex connectivity.
A practical way of understanding what rearrangements are permitted by the symmetry group of a graph is to assign labels to the vertices and edges of the graph. Consider moving around the vertices and edges of the graph in such way so that each graph resulting from the reconfiguration connects the same labelled vertices via the same labelled edges.
For example, the figure below displays a graph
with labelled vertices
and edges
:

Six symmetries come from permuting the edges
connecting the vertices
and one symmetry comes from reflecting through a horizontal axis. The symmetry arising from a reflection through the horizontal axis is shown below:

On the other hand, the graph below does not belong to the symmetry group of the initial graph
because of connecting
with
through
, which introduces a connection not present in
:

Let’s count the graphs in the symmetry group of
. Six graphs symmetric to
arise from permuting the edges
, and this set of six graphs is isomorphic to the symmetric group
. The original graph
along with its reflection through the horizontal axis gives a set of two graphs isomorphic to
. So the symmetry group of
contains
graphs, and is isomorphic to the direct product
.
The main aim of this blog post is to provide a mathematically rigorous definition of the symmetry group of a graph starting by the concept of graph symmetry. A symmetry of a graph
with vertex set
and edge set
is a permutation
of the vertex set
such that the pair of vertices
form an edge in
if and only if the pair
also form an edge in
.
Unfortunately, there is an error in this first definition. In the previous example, if the edges
and
are permuted, a new distinct graph from the symmetry group of
arises, which is not accounted by the definition due to permuting the edges but not the vertices of
.
A more mathematically accurate definition is provided in John Meier’s book “Groups, graphs and trees: an introduction to the geometry of infinite groups” (definition 1.14, p. 10-11). According to Meier’s definition, a symmetry of a graph
with vertices
and edges
is a bijection
taking vertices to vertices and edges to edges such that if
in
, then
in
, where
denotes the set of two vertices
and
connected by an edge
.
Meier’s definition corrects the issue of the previous definition, but does not tell what is the domain and range of
. In fact, trying to define the domain and range of
does not seem to be obvious due to the dubious notation
and
.
One possible way round this problem is to define graph symmetry to be a set of two separate bijections, one on the vertices and one on the edges of the graph. The third definition would take the following form; a symmetry of a graph
with vertices
and edges
is a set
of bijections
and
such that if
in
, then
in
.
Note that the converse holds in the above definition, i.e.
in
in
. To prove this, assume that
. From the definition,
. Given that
, assume without loss of generality that
and
. Since
is a bijection, it follows that
and
, which is a contradiction since the edge
connects two vertices according to
.
In light of the validity of the inverse, one can define graph symmetry using the equivalence
in
in
.
However, this third definition raises one more question. Having two separate bijections, one for vertices and one for edges, does not allow to define graph symmetry as a single function. The solution is to define a symmetry
of a graph
by
.
So the third definition can now be corrected. A symmetry of a graph
with vertices
and edges
is a bijection
defined by
, where
and
are two bijections such that if
in
, then
in
.
This corrected third definition coincides with Meier’s definition if the latter is clarified formally as follows; a symmetry of a graph
with vertices
and edges
is a bijection
with the following three properties:
Having defined graph symmetry, the symmetry group of a graph becomes simply the collection of all graph symmetries. Formally, the symmetry group
of a graph
is the set of symmetries of
equipped with the operation of composition of graph symmetries.
Note that the composition
of two graph symmetries
and
is essentially a composition of two vertex or edge permutations.