Every labeled graph has a permutation – the identity – that leaves the graph unchanged; the interesting question is whether there are permutations other than the identify that leave the labeled graph unchanged and, if so, how many, or which ones.

There is no particular feature, or set of features, that guarantees that a relabeling of a labeled graph preserves the adjacency; if the relabeling of a graph \(G\) happens to preserve its adjacency, though, the relabeled graph \(H\) is an automorphism of \(G\). The number of automorphisms of \(G\) depends on its symmetries; it is at least 1, if \(G\) only has the trivial automorphism, and at most \(n!\), if every possible relabeling of \(G\) is an automorphism; and then there is the case in between. The number of isomorphisms of a graph \(G\) of order \(n\) is always \(n!\); the automorphisms of a graph \(G\) are always a subset of the set of isomorphisms; we refer to this set as \(Aut(G)\), and to its order as \(|Aut(G)|\). Hence, \(1 \le |Aut(G)| \leq n!\); let’s see some illustrative cases with graphs of order 4.

|Aut(G)| = n!

Case a.

For any graph \(G\) of order \(n\), any of the \(n!\) permutations of its labels is an isomorphism. If \(G\) is symmetric then all of its \(n!\) permutations are also automorphisms, because all the permutations preserve the adjacency. This is the one case where the order of the automorphism set is \(n!\).

Symmetric graphs include the seven Generalized Petersen symmetric graphs and the Johnson \(J(n,1)\) graphs, a.k.a. the complete graphs of order \(n\), or \(K_n\). Let’s consider the complete graphs, for which every vertex is connected to every other vertex, as examples:

Notice that our drawings above of \(K_3\), \(K_4\) and \(K_5\) are CanDs already.

The AVLs of these complete graphs are

{0:[1,2], 1:[0,2], 2:[0,1]}                                    # K_3
{0:[1,2,3], 1:[0,2,3], 2:[0,1,3], 3:[0,1,2]}                   # K_4
{0:[1,2,3,4],1:[0,2,3,4],2:[0,1,3,4],3:[0,1,2,4],4:[0,1,2,3]}  # K_5

For the example case of \(K_4\), the following figure shows all the graphs obtained from permuting the labels of the graph at the top-left corner, i.e., \(G_{A0}\):

Every possible permutation corresponds to an automorphism of the graph \(G_{A0}\), a.k.a. \(K_4\), as we can verify because all of them share the same \(AVL\) and CanD; indeed, \(K_3\) has \(3!=6\) automorphisms, \(K_4\) has \(n!=24\), \(K_5\) has \(5!=120\), and so on. Thus, the number of isomorphisms is the same as the number of automorphisms when the graph is symmetric.

1 < |Aut(G)| < n!

Case b.

Now, let’s redefine the graph \(G_{A0}\) to the top-left graph shown below, together with all its relabelings.

We are going to focus on two relabelings of \(G_{A0}\). The first one is \(G_{A2}\); if we try to reposition the vertices of \(G_{A0}\) to match the positions of the vertices of \(G_{A2}\), which amounts to transposing \(v_1\) and \(v_2\), we end up with a graph with edges that cross each other; such graph doesn’t match \(G_{A2}\); since the graphs don’t overlap, we have graphically verified that \(G_{A2}\) is not an automorphism of \(G_{A0}\).

The second relabeling that we will consider is that of \(G_{C4}\); to reposition the vertices of \(G_{A0}\) to match those of \(G_{C4}\), we rotate \(G_{A0}\) 180°; the repositioned version of \(G_{A0}\) matches \(G_{C4}\) so we have verified graphically that \(G_{C4}\) is an automorphism of \(G_{A0}\).

Some of the permutations of \(G_{A0}\) are automorphisms and some are not. The number of automorphisms of a graph depends on its symmetries. In the case of \(G_{A0}\), we can rotate it counterclockwise by 0°, 90°, 180° and 270° and end up with a graph that overlaps itself, so each of these four permutations is an automorphism; likewise, we can reflect it about any of four axis to get four more automorphisms. In the end, of the \(n!=24\) permutations that lead to different labelings, those 8 are the only automorphisms of \(G_{A0}\). These permutations are:

The graphs resulting from applying these permutations to \(G_{A0}\) have a red background; these include \(G_{C4}\) but not \(G_{A2}\). We can compose any of these eight permutations and the result will always be one of the same eight red permutations, e.g., start with \(G_{B1}\), rotate 90°, and then reflect about 45° axis, and we end up with \(G_{C2}\), which is also a red-background graph, so the red graphs are closed under composition, where composition is a succesive application of a function, which in this case means a succession of permutations. Likewise, they are associative, and the identity permutation [0,1,2,3] is in the set of red graphs. Finally, each of the red graphs has an inverse that is also a red graph:

Since, the set of permutations associated with the red graphs satisfy closure, associativity, identity and invertibility, we say that they form a group under composition; more specifically, the automorphisms of \(G_{A0}\) form the \(Aut(G_{A0})\) group. To identify computationally which graphs are automorphisms, we obtain the AVLs of all the 24 relabelings and place them in colored groups:

{0:[1,3],1:[0,2],2:[1,3],3:[0,2]} # A0,A4,B1,B5,C2,C4,D0,D5 (red)
{0:[1,2],1:[0,3],2:[0,3],3:[1,2]} # A1,A3,B0,B3,C0,C5,D2,D4 (blue)
{0:[2,3],1:[2,3],2:[0,1],3:[0,1]} # A2,A5,B2,B4,C1,C3,D1,D3 (green)

The AVLs tells us that all the possible labeled graphs of \(G_{A0}\) are divided in three sets; any graph of the grid has exactly 8 automorphisms. The red set is special because our graph \(G_{A0}\) is in it, meaning that we can use the identity permutation to permute into it. The green set contains graphs that are the automorphisms of each other, and so does the blue set, but unlike the red set, they are just sets, while the red graph is a group.

Case c.

Let’s look at another example; again, we redifine \(G_{A0}\) to the top-left graph below, also with four vertices, but with less symmetries than the square. The square has 8 symmetries – rotations by 0°, 90°, 180° and 270° plus reflections about the vertical, horizontal and the two diagonal axes; in contrast, the graph \(G_{A0}\) below has only four symmetries: it can rotate by 0° or 180°, and it can reflect about the vertical or horizontal axes.

Now there are six sets of automorphisms compared with the three sets of the square, i.e., following the colors of the graphs of the first row we have red, blue, green, purple, orange, and yellow sets, each a set of four elements. Again, the red sets satisfies closure, associativity, identity, and invertibility, so it forms a group under composition. The AVLs of the graphs are

{0:[1,3,3], 1:[0,2,2], 2:[1,1,3], 3:[0,0,2]} # A0,B1,C4,D5 (red)
{0:[1,2,2], 1:[0,3,3], 2:[0,0,3], 3:[1,1,2]} # A1,B0,C5,D4 (blue)

{0:[2,3,3], 1:[2,2,3], 2:[0,1,1], 3:[0,0,1]} # A2,B2,C1,D3 (green)
{0:[1,1,2], 1:[0,0,3], 2:[0,3,3], 3:[1,2,2]} # A3,B3,C0,D2 (purple)

{0:[1,1,3], 1:[0,0,2], 2:[1,3,3], 3:[0,2,2]} # A4,B5,C2,D0 (orange)
{0:[2,2,3], 1:[2,3,3], 2:[0,0,1], 3:[0,1,1]} # A5,B4,C3,D1 (yellow)

Case d.

Let’s reduce the symmetry even more. We redifine the graph \(G_{A0}\) to the one below, which has a single symmetry, namely, reflection about the horizontal axis.

In this case, the only automorphism of \(G_{A0}\) is \(G_{D5}\). Every graph in the table has a single automorphism which is the other graph of a matching color. In this case we have 12 sets of automorphic graphs, each set with 2 elements. The AVLs of the graphs are

{0:[1,3,3], 1:[0,2], 2:[1,3], 3:[0,0,2]} # A0,D5 (light red)
{0:[1,2,2], 1:[0,3], 2:[0,0,3], 3:[1,2]} # A1,C5 (light blue)

{0:[2,3,3], 1:[2,3], 2:[0,1], 3:[0,0,1]} # A2,D3 (light green)
{0:[1,1,2], 1:[0,0,3], 2:[0,3], 3:[1,2]} # A3,B3 (light purple)

{0:[1,1,3], 1:[0,0,2], 2:[1,3], 3:[0,2]} # A4,B5 (light orange)
{0:[2,2,3], 1:[2,3], 2:[0,0,1], 3:[0,1]} # A5,C3 (light yellow)

{0:[1,2], 1:[0,3,3], 2:[0,3], 3:[1,1,2]} # B0,D4 (dark blue)
{0:[1,3], 1:[0,2,2], 2:[1,1,3], 3:[0,2]} # B1,C4 (dark red)

{0:[2,3], 1:[2,2,3], 2:[0,1,1], 3:[0,1]} # B2,C1 (dark green)
{0:[2,3], 1:[2,3,3], 2:[0,1], 3:[0,1,1]} # B4,D1 (yellow)

{0:[1,2], 1:[0,3], 2:[0,3,3], 3:[1,2,2]} # C0,D2 (dark purple)
{0:[1,3], 1:[0,2], 2:[1,3,3], 3:[0,2,2]} # C2,D0 (dark orange)

As always, the graphs with a light red background are automorphic to \(G_{A0}\) and form a group; the graphs with backgrounds other than light red are automorphic to all graphs with the same background.

|Aut(G)| = 1

Case e.

In the next example, we redifine \(G_{A0}\) and remove all its symmetries by adding a loop to a vertex; there is no transformation other than the identity that preserves the graph adjacencies. A graph with no symmetries is a rigid graph, a.k.a. an asymmetric or an identity graph; in this case, each vertex of the graph has different characteristics from the other vertices of the graph. The following graphs are rigid:

In this case we have 24 sets, each containing one element that only has the trivial automorphism. Their AVLs are

{0:[0,1,3,3], 1:[0,2], 2:[1,3], 3:[0,0,2]} # A0 (light red)
{0:[0,1,2,2], 1:[0,3], 2:[0,0,3], 3:[1,2]} # A1

{0:[0,2,3,3], 1:[2,3], 2:[0,1], 3:[0,0,1]} # A2
{0:[0,1,1,2], 1:[0,0,3], 2:[0,3], 3:[1,2]} # A3

{0:[0,1,1,3], 1:[0,0,2], 2:[1,3], 3:[0,2]} # A4
{0:[0,2,2,3], 1:[2,3], 2:[0,0,1], 3:[0,1]} # A5

{0:[1,2], 1:[0,1,3,3], 2:[0,3], 3:[1,1,2]} # B0
{0:[1,3], 1:[0,1,2,2], 2:[1,1,3], 3:[0,2]} # B1

{0:[2,3], 1:[1,2,2,3], 2:[0,1,1], 3:[0,1]} # B2
{0:[1,1,2], 1:[0,0,1,3], 2:[0,3], 3:[1,2]} # B3

{0:[2,3], 1:[1,2,3,3], 2:[0,1], 3:[0,1,1]} # B4
{0:[1,1,3], 1:[0,0,1,2], 2:[1,3], 3:[0,2]} # B5

{0:[1,2], 1:[0,3], 2:[0,2,3,3], 3:[1,2,2]} # C0
{0:[2,3], 1:[2,2,3], 2:[0,1,1,2], 3:[0,1]} # C1

{0:[1,3], 1:[0,2], 2:[1,2,3,3], 3:[0,2,2]} # C2
{0:[2,2,3], 1:[2,3], 2:[0,0,1,2], 3:[0,1]} # C3

{0:[1,3], 1:[0,2,2], 2:[1,1,2,3], 3:[0,2]} # C4
{0:[1,2,2], 1:[0,3], 2:[0,0,2,3], 3:[1,2]} # C5

{0:[1,3], 1:[0,2], 2:[1,3,3], 3:[0,2,2,3]} # D0
{0:[2,3], 1:[2,3,3], 2:[0,1], 3:[0,1,1,3]} # D1

{0:[1,2], 1:[0,3], 2:[0,3,3], 3:[1,2,2,3]} # D2
{0:[2,3,3], 1:[2,3], 2:[0,1], 3:[0,0,1,3]} # D3

{0:[1,2], 1:[0,3,3], 2:[0,3], 3:[1,1,2,3]} # D4
{0:[1,3,3], 1:[0,2], 2:[1,3], 3:[0,0,2,3]} # D5

---

Let’s consider the answers to several versions of the Graph Automorphism (GA) problem, i.e.,:

Given a graph \(G\)…

• Decision problem (GA): Does it have an automorphism other than the trivial?
• Unique GA problem (uniqueGA): Does it have exactly only 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?

For our example cases we have:

version/case	A – symmetric	B	C	D	E – rigid
Decision	yes	yes	yes	yes	no
uniqueGA	no	no	no	yes	no
|Aut(G)|	n! = 24	8	4	2	1
Aut(G)	all isomorphisms	A0,A4,B1,B5,C2,C4,D0,D5	A0,B1,C4,D5	A0,D5	A0

Example

Let’s consider a final example graph from stackexchange, relabeled to our convention:

The AVL is

{0:[2], 1:[2], 2:[0,1,5,9], 3:[2,4,7], 4:[2,3,7], 5:[2,6,8], 6:[2,5,8], 7:[3,4,8], 8:[5,6,7], 9:[2]}

The question in StackExchange was to identify its automorphisms that was answered with the post of the output of the Sage public package. The discussion below derives the automorphisms and provides the same published answer.

Let’s consider the constraints and symmetries of this graph. First, \(v_2\) is a fixed point because its the only vertex of degree 7, so we cannot transpose it with any other vertex. In other words, since \(v_2\) is a fixed point, it does not appear in any of the cycle notation of the permutations that lead to any of the automorphisms.

Next, vertices \(v_0\), \(v_1\) and \(v_9\) to the left of \(v_2\) are symmetric and can only exchange places among themselves because they are all vertices of degree 1 adjacent to \(v_2\). Since there are 3 such vertices, we can permute them in 3! = 6 ways, as follows:

The six vertices on the right of \(v_2\) have some symmetries too. First, we can transpose \(v_3\) and \(v_4\) at will, same as \(v_5\) and \(v_6\). Then, we can permute \(v_3\), \(v_4\) and \(v_7\), with \(v_5\), \(v_6\) and \(v_8\). The following are the resulting 8 permutations:

The possible permutations that lead to automorphisms are any of the 6 permutations of \(v_0\), \(v_1\), and \(v_9\), together with any of the 8 permutations of \(v_3\), \(v_4\), \(v_5\), \(v_6\), \(v_7\), and \(v_8\); hence, the total number of permutations that lead to automorphisms is \(6 \times 8 = 48.\) These permutations are:

()	(0,9)	(1,9)	(0,1)	(0,1,9)	(0,9,1)
(3,4)	(0,9)(3,4)	(1,9)(3,4)	(0,1)(3,4)	(0,1,9)(3,4)	(0,9,1)(3,4)
(5,6)	(0,9)(5,6)	(1,9)(5,6)	(0,1)(5,6)	(0,1,9)(5,6)	(0,9,1)(5,6)
(3,4)(5,6)	(0,9)(3,4)(5,6)	(1,9)(3,4)(5,6)	(0,1)(3,4)(5,6)	(0,1,9)(3,4)(5,6)	(0,9,1)(3,4)(5,6)
(3,5)(4,6)(7,8)	(0,9)(3,5)(4,6)(7,8)	(1,9)(3,5)(4,6)(7,8)	(0,1)(3,5)(4,6)(7,8)	(0,1,9)(3,5)(4,6)(7,8)	(0,9,1)(3,5)(4,6)(7,8)
(3,5,4,6)(7,8)	(0,9)(3,5,4,6)(7,8)	(1,9)(3,5,4,6)(7,8)	(0,1)(3,5,4,6)(7,8)	(0,1,9)(3,5,4,6)(7,8)	(0,9,1)(3,5,4,6)(7,8)
(3,6,4,5)(7,8)	(0,9)(3,6,4,5)(7,8)	(1,9)(3,6,4,5)(7,8)	(0,1)(3,6,4,5)(7,8)	(0,1,9)(3,6,4,5)(7,8)	(0,9,1)(3,6,4,5)(7,8)
(3,6)(4,5)(7,8)	(0,9)(3,6)(4,5)(7,8)	(1,9)(3,6)(4,5)(7,8)	(0,1)(3,6)(4,5)(7,8)	(0,1,9)(3,6)(4,5)(7,8)	(0,9,1)(3,6)(4,5)(7,8)

The graph has an order of \(n=10\) so it has 10! = 3628800 isomorphisms, of which 48 are automorphisms; hence, the set of isomorphisms is divided in 75600 sets, with all the graphs of each such set automorphic to each other, each set of size 48.

---

First published on May 20/2026