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 Group of Infinite Groups”. 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.