Graph theory | "There is no royal road to geometry". Euclid

The following self-contained post relates to definition 1.17, p. 11, of the book “Groups, graphs and trees: an introduction to the geometry of infinite groups” by John H. Meier.

Let $K_n$ be a complete graph and $\mbox{Sym}(K_n)$ its symmetry group. It will be shown that $K_n$ is vertex transitive, i.e. that for any two vertices $v_i\in K_n$ and $v_j\in K_n$ there exists a symmetry $a\in\mbox{Sym}(K_n)$ such that $a(v_i)=v_j$ .

The proof is constructive. Given any two vertices $v_i\in K_n$ and $v_j\in K_n$ , it suffices to provide a symmetry $a_{ij}:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)\in\mbox{Sym}(K_n)$ such that $a_{ij}(v_i)=v_j$ . Although the suggested symmetry is different for every $v_i$ and $v_j$ , the simpler notation $a$ is preferred in place of $a_{ij}$ .

Given $v_i\in K_n$ and $v_j\in K_n$ , a suitable symmetry can be constructed by swapping $v_i$ with $v_j$ , by redirecting all edges with one end in $v_i$ to edges with one end in $v_j$ and vice versa, and by leaving all other vertices and edges intact.

To formalize the construction, given $v_i\in K_n$ and $v_j\in K_n$ , the symmetry $a$ is set to satisfy the following seven properties:

$a(v_i)=v_j$ ,
$a(v_j)=v_i$ ,
$a(v_k)=v_k$ for all vertices $v_k$ other than $v_i,~v_j$ ,
$a(e_{ij})=e_{ij}$ , where $e_{ij}$ denotes the edge connecting $v_i$ with $v_j$ ,
$a(e_{ik})=e_{jk}$ for all $k$ other than $i,~j$ , where $e_{ik}$ denotes the edge connecting $v_i$ with $v_k$ and $e_{jk}$ the edge connecting $v_j$ with $v_k$ ,
$a(e_{jk})=e_{ik}$ for all $k$ other than $i,~j$ , and
$a(e_{kl})=e_{kl}$ for all $k,~l$ other than $i,~j$ , where $e_{kl}$ denotes the edge connecting $v_k$ with $v_l$ .

Note that all edges exist in the above construction since $K_n$ is complete, so the symmetry is well-defined.

It is easy to check that the proposed symmetry maps vertices to vertices, edges to edges, and preserves the connectivity of $\Gamma$ according to the definition of symmetry provided in this blog post. For instance, $\mbox{ends}(e_{ik})=\{v_i,v_k\}$ , $a(e_{ik})=e_{jk}$ , $a(v_i)=v_j$ and $a(v_k)=v_k$ yield $\mbox{ends}(a(e_{ik}))=\mbox{ends}(e_{jk})=\{v_j,v_k\}=\{a(v_i),a(v_k)\}$ , which is an edge in $K_n$ .

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\}$ :

group_symmetry_of_graph_original

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:

group_symmetry_of_graph_reflected

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$ :

group_symmetry_of_graph_wrong

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.

"There is no royal road to geometry". Euclid

A blog on mathematics, statistics and computing

Category Archives: Graph theory

Proof: the symmetry group of a complete graph is vertex transitive

Clarifying the concept of symmetry group of a graph