Clarifying the concept of symmetry group of a graph

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 $\Gamma$ with labelled vertices $\{v_1, v_2, v_3, v_4\}$ and edges $\{e_1, e_2, e_3, e_4, e_5, e_6\}$:

Six symmetries come from permuting the edges $\{e_4, e_5, e_6\}$ connecting the vertices $\{v_1, v_4\}$ 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 $\Gamma$ because of connecting $v_2$ with $v_4$ through $e_2$, which introduces a connection not present in $\Gamma$:

Let’s count the graphs in the symmetry group of $\Gamma$. Six graphs symmetric to $\Gamma$ arise from permuting the edges $\{e_4, e_5, e_6\}$, and this set of six graphs is isomorphic to the symmetric group $\mbox{Sym}_3$. The original graph $\Gamma$ along with its reflection through the horizontal axis gives a set of two graphs isomorphic to $\mbox{Sym}_2$. So the symmetry group of $\Gamma$ contains $6\times 2 =12$ graphs, and is isomorphic to the direct product $\mbox{Sym}_3\bigoplus\mbox{Sym}_2$.

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 $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$ is a permutation $f$ of the vertex set $V$ such that the pair of vertices $\{v_1,v_2\}$ form an edge in $\Gamma$ if and only if the pair $\{f(v_1), f(v_2)\}$ also form an edge in $\Gamma$.

Unfortunately, there is an error in this first definition. In the previous example, if the edges $e_4$ and $e_5$ are permuted, a new distinct graph from the symmetry group of $\Gamma$ arises, which is not accounted by the definition due to permuting the edges but not the vertices of $\Gamma$.

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 $\Gamma$ with vertices $V(\Gamma)$ and edges $E(\Gamma)$ is a bijection $f$ taking vertices to vertices and edges to edges such that if $\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma$, then $\mbox{ends}(f(e))=\{f(v_1),f(v_2)\}$ in $\Gamma$, where $\mbox{ends}(e)=\{v_1,v_2\}$ denotes the set of two vertices $v_1$ and $v_2$ connected by an edge $e$.

Meier’s definition corrects the issue of the previous definition, but does not tell what is the domain and range of $f$. In fact, trying to define the domain and range of $f$ does not seem to be obvious due to the dubious notation $f(e)$ and $f(v_1)$.

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 $\Gamma$ with vertices $V(\Gamma)$ and edges $E(\Gamma)$ is a set $\{f_1,f_2\}$ of bijections $f_1:V(\Gamma)\rightarrow V(\Gamma)$ and $f_2:E(\Gamma)\rightarrow E(\Gamma)$ such that if $\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma$, then $\mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\}$ in $\Gamma$.

Note that the converse holds in the above definition, i.e. $\mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\}$ in $\Gamma\Rightarrow\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma$. To prove this, assume that $\mbox{ends}(e)=\{q,r\}\ne \{v_1,v_2\}$. From the definition, $\mbox{ends}(e)=\{q,r\}\Rightarrow\mbox{ends}(f_2(e))=\{f_1(q),f_1(r)\}$. Given that $\{q,r\}\ne \{v_1,v_2\}$, assume without loss of generality that $q\ne v_1$ and $q\ne v_2$. Since $f_1$ is a bijection, it follows that $f_1(q)\ne f_1(v_1)$ and $f_1(q)\ne f_1(v_2)$, which is a contradiction since the edge $f_2(e)$ connects two vertices according to $\{f_1(v_1),f_1(v_2)\}=\mbox{ends}(f_2(e))=\{f_1(q),f_1(r)\}$.

In light of the validity of the inverse, one can define graph symmetry using the equivalence $\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma\iff \mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\}$ in $\Gamma$.

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 $f$ of a graph $\Gamma$ by $f(x)= \begin{cases} f_1(x) \mbox{ if } x\in V(\Gamma)\\ f_2(x)\mbox{ if } x\in E(\Gamma)\end{cases}$.

So the third definition can now be corrected. A symmetry of a graph $\Gamma$ with vertices $V(\Gamma)$ and edges $E(\Gamma)$ is a bijection $f:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)$ defined by$f(x)= \begin{cases} f_1(x) \mbox{ if } x\in V(\Gamma)\\ f_2(x)\mbox{ if } x\in E(\Gamma)\end{cases}$, where $f_1:V(\Gamma)\rightarrow V(\Gamma)$ and $f_2:E(\Gamma)\rightarrow E(\Gamma)$ are two bijections such that if $\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma$, then $\mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\}$ in $\Gamma$.

This corrected third definition coincides with Meier’s definition if the latter is clarified formally as follows; a symmetry of a graph $\Gamma$ with vertices $V(\Gamma)$ and edges $E(\Gamma)$ is a bijection $f:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)$ with the following three properties:

• $v\in V(\Gamma)\Rightarrow f(v)\in V(\Gamma)$,
• $e\in E(\Gamma)\Rightarrow f(e)\in E(\Gamma)$,
• $\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma\Rightarrow\mbox{ends}(f(e))=\{f(v_1),f(v_2)\}$ in $\Gamma$.

Having defined graph symmetry, the symmetry group of a graph becomes simply the collection of all graph symmetries. Formally, the symmetry group $\mbox{Sym}(\Gamma)$ of a graph $\Gamma$ is the set of symmetries of $\Gamma$ equipped with the operation of composition of graph symmetries.

Note that the composition $f\circ g$ of two graph symmetries$f:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)$ and$g:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)$ is essentially a composition of two vertex or edge permutations.