Automorphism verification

There are \(n!\) permutations of the \(n\) labels of a labeled graph \(G\) of order \(n\). Of those permutations, there are some special ones that preserve the adjacency of the labeled graph, i.e., the relationship between its labeled vertices and edges; in such a case, we say that the graph and the permuted graph are automorphisms. In other words, if graph \(H\) is an automorphism of graph \(G\) then each vertex \(v_i\) of \(H\) has the same neighbors as the vertex \(v_i\) of \(G\), e.g., if vertex \(v_3\) of \(G\) has degree 2 and is adjacent to \(v_2\) and \(v_7\), then vertex \(v_3\) of \(H\) has degree 2 and is adjacent to \(v_2\) and \(v_7\). A labeled graph its identical to its automorphism, i.e., they are the same labeled graph.

A Canonical Drawing, a.k.a. a CanD, is a drawing of a labeled graph with the labels ordered in a circular fashion, at equal angles between them. Consider the following labelings of a graph \(G\) and their CanDs:

Their AVLs are:

{0:[1,4], 1:[0,2,4], 2:[1,3], 3:[2,4], 4:[0,1,3]} # G_a
{0:[1,4], 1:[0,2], 2:[1,3,4], 3:[2,4], 4:[0,2,3]} # G_b
{0:[1,4], 1:[0,2,4], 2:[1,3], 3:[2,4], 4:[0,1,3]} # G_c

and the permutations that map them are

[3,2,1,0,4] # p(a->b) = [[0,3],[1,2]]
[0,4,3,2,1] # p(a->c) = [[1,4],[2,3]]
[2,3,4,0,1] # p(b->c) = [[0,2,4,1,3]]

We will consider \(G_a\) as our starting graph. First, we permute the labels of \(G_a\) using the identity permutation, a.k.a. the trivial permutation, i.e., \(P_{id} = [0,1,2,3,4]\). Since this permutation keeps the vertices in place, the permuted labeled graph is the original labeled graph and thus, the original adjacency is preserved, trivially, since we changed nothing; graphically, we can overlap \(G_a\) over \(G_a\) and it matches exactly; likewise, their CanDs and AVLs are one and the same.

Indeed, all labeled graphs are identical to themselves and thus, all labeled graphs have at least one automorphism via the trivial permutation; such automorphism is aptly called the trivial automorphism. Trivial automorphisms are not very interesting since we know all graphs have them, and we know that it is the trivial permutation that generates them. Hence, when we search for automorphisms we mean to search for automorphisms other than the trivial. So let’s look whether \(G_b\) or \(G_c\) could be an automorphism of \(G_a\).

We permute the labels of \(G_a\) using \(P_{a \rightarrow b} = [3,2,1,0,4]\) to obtain the \(G_b\) labeling. First, let’s compare the degrees of the vertices of \(G_a\) against those of \(G_b\); if a permutation does not preserve the vertex degree, it has no hope to have preserved the adjacency, plus vertex degree is computationally inexpensive to check, i.e., the degree of a vertex is simply the length of its list of adjacent vertices in the AVL. The vertices 0, 1, 2, 3, and 4 of \(G_a\) have degrees of 2, 3, 2, 2 and 3, respectively; the vertices 0, 1, 2, 3, and 4 of all automorphisms of \(G_a\) must have those same degrees.

It turns out that \(v_0\), \(v_3\) and \(v_4\) of both \(G_a\) and \(G_b\) have the same degrees – 2, 2, and 3 – but \(v_1\) and \(v_2\) do not, so we don’t even need to check for adjacencies: \(G_b\) is not an automorphism of \(G_a\). The effect of the \(P_{a \rightarrow b} = [3,2,1,0,4]\) permutation is clear when we write it in cycle notation: \(P_{a \rightarrow b} = (0,3)(1,2)\), which is two transpositions. Graphically, when we reposition the vertices of \(G_a\) to match the positions of the vertices of \(G_b\), the repositioned drawing of \(G_a\) and the drawing of \(G_b\) don’t match:

The conclusion is that the \(G_b\) is not simply the labeled \(G_a\) drawn in a different way implying, again, that \(G_b\) is not an automorphism of \(G_a\). Likewise, the CanDs and AVLs of \(G_a\) and \(G_b\) are different.

Finally, let’s permute the labels of \(G_a\) using the \(P_{a \rightarrow c} = [0,4,3,2,1]\) permutation to obtain the \(G_c\) labeling, and compare the degrees of the vertices of \(G_a\) against those of \(G_c\). In this case all the vertices of \(G_a\) have the same degrees as those of \(G_c\), e.g., the degree of \(v_i\), for all \(i\), is the same in both graphs. As for the vertex adjacency, it has been preserved as well because the AVLs and CanDs of \(G_a\) and \(G_c\) are equal. Indeed, when we reposition the vertices of \(G_a\) to match those of \(G_c\), the drawings of the permuted \(G_a\) and \(G_c\) do match, so \(G_c\) is an automorphism of \(G_a\).

Now let’s compare the drawings. This permutation in cycle notation is \(P_{a \rightarrow c} = (1,4)(2,3)\) – again, two transpositions:

And… the redrawn \(G_a\) and \(G_c\) drawings match indicating the \(G_a\) and \(G_c\) are actually the same graph simply drawn in different ways: \(G_c\) is an automorphism of \(G_a\). Likewise, CanDs and AVLs of \(G_a\) and \(G_c\) are the same.

The question arises: why do some premutations lead to automorphisms and some do not? The \(P_{a \rightarrow b}\) permutation had two transpositions and so did \(P_{a \rightarrow c}\). As a hypothesis, it might be the case that some transpositions preserve the adjacency of the graph while some do not. If this is the case, either of the transpositions that permute \(G_a\) onto \(G_c\), i.e, (1,4) and (2,3), by itself, would also preserve the adjacency. The following are the results of permuting \(G_a\) by the transposition (1,4) into \(G_d\), and then by the transposition (2,3) into \(G_e\), with their respectives CanDs:

Their AVLs are:

{0:[1,4], 1:[0,2,4], 2:[1,3], 3:[2,4], 4:[0,1,3]} # G_a
{0:[1,4], 1:[0,3,4], 2:[3,4], 3:[1,2], 4:[0,1,2]} # G_d
{0:[1,4], 1:[0,3,4], 2:[3,4], 3:[1,2], 4:[0,1,2]} # G_e

and the permutations that map them are

[0,4,2,3,1] # p(a->d) = [[1,4]]
[0,1,3,2,4] # p(a->e) = [[2,3]]
[0,4,3,2,1] # p(d->e) = [[1,4],[2,3]]

In this case, the degree of the vertices is preserved, e.g., for all \(i\) we have that \(v_i\) has the same degree in \(G_a\), \(G_d\) and \(G_e\). However, in spite of this, the adjacency is not preserved; for example, \(v_1\) of \(G_a\) is adjacent to \(v_2\) but neither the \(v_1\) of \(G_d\) or \(G_e\) is adjacent to \(v_2\). Hence, neither \(G_d\) nor \(G_e\) are automorphisms of \(G_a\); we can also verify this noticing that the AVLs and CanDs of \(G_d\) and \(G_e\) are different from those of \(G_a\); hence, the preservation of adjacency in a particular graph is not a consequence of a transposition; instead, we need both transpositions to get \(G_c\), which is an automorphism of \(G_a\). Interestingly, though, it turns out that \(G_d\) and \(G_e\) are automorphisms of each other, as their CanDs and AVLs are equal.

As we might have already guessed, what is at play in automorphisms is the preservation of adjacency via permutations that preserve the symmetry of the graph. We can reflect either \(G_a\) or \(G_d\) about their vertical axis, and end up with the same drawing, albeit labeled in a different way.

Given this information, we can surmise a permutation that would lead to an automorphism of \(G_b\) and, indeed, we would be correct, i.e., (0,1)(2,4):

Their AVLs are:

{0:[1,4], 1:[0,2], 2:[1,3,4], 3:[2,4], 4:[0,2,3]} # G_b
{0:[1,4], 1:[0,2], 2:[1,3,4], 3:[2,4], 4:[0,2,3]} # G_f

and the permutation that maps them are

[1,0,4,3,2] # p(b->f) = [[0,1],[2,4]]

Now that we have related graph automorphisms to the symmetries of the graphs, we can describe the graph automorphism problem that, actually, is a general term for various closely related problems, related enough that solving any of them in an efficient manner, i.e., in polynomial time, would solve all the others in an efficient manner as well. Here are some of these closely related problems:

The Graph Automorphism (GA) problem: Consider a graph \(G\).

• Decision problem (GA): Does it have an automorphism other than the trivial?
• Unique GA problem (uniqueGA): Does it have exactly one non-trivial automorphism
• Counting problem (|Aut(G)|): How many automorphisms (including the trivial) does it have?
• Search problem (Aut(G)): What are its automorphisms?

Learning whether a particular permutation leads to an automorphism is not a version of the GA problem; instead, we can answer this directly and efficiently and, actually, the program at the top of this page does exactly that: we give it the AVL of a graph \(G\) and a permutation \(P\), and it determines whether the permuted graph \(H\) is an automorphism of \(G\) by comparing their AVLs:

def GA_verify (G_avl, P_g_to_h):
    H_avl = AVL_permute (G_avl, P_g_to_h)
    return G_avl == H_avl

It is in this type of comparisons that canonizing or standarizing an object shows its value. We can write an AVL in multiple ways, but if we standarize the AVLs, their comparisons are straightforward. Graphically, we verify the automorphism of graphs by comparing their CanDs, which are also canonical representations of the graph. We could also find out whether two graphs are automorphic comparing their AVMs directly, or indirectly, comparing codes created from the AVMs, e.g., appending the rows of the AVMs into a string of numbers.

First published on Apr. 2/2026