Let’s go over a visual explanation of what graph morphisms are. Consider three different labeled graphs \(G\), \(H\) and \(I\):

Are these labeled graphs the same graph? Intuitively, two graphs are the same if we can reposition the vertices of one so that matches the vertices of the other, and have the vertex connectivity, a.k.a. adjacency, preserved. \(G\), \(H\) and \(I\) might have an identical connectivity, but they might look different because of their labeling and/or drawing. Maybe we can tell if we rearrange their vertices in a given pattern.

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. The following are CanDs of \(G\), \(H\) and \(I\):

and here are their AVLs:

{0:[1,4], 1:[0,2,4], 2:[1,3], 3:[2,4], 4:[0,1,3]} # AVL_g
{0:[1,3,4], 1:[0,2,3], 2:[1,3], 3:[0,1,2,4], 4:[0,3]} # AVL_h
{0:[1,3,4], 1:[0,3], 2:[3,4], 3:[0,1,2], 4:[0,2]} # AVL_i

The appearances of the graphs \(G\), \(H\) and \(I\) are different, their CanDs are different, and their AVLs are different. Still, is there some permutation that maps the vertices of \(G\) onto those of \(H\) or \(I\) in such a way that the adjacency of \(G\) is preserved?

Let’s consider \(H\) first; \(G\) has no vertex of degree 4, while \(v_3\) of \(H\) has degree 4; there is no permutation that can map \(G\) onto \(H\) and preserve the adjacency of \(G\) because there is no vertex in \(G\) that we could map onto \(v_3\) of \(H\).

In contrast, \(G\) and \(I\) are ‘the same’ graph, in some sense. Indeed, we can transform the drawing of \(I\) to match that of \(G\), and verify, by removing their labels, that \(G\) and \(I\) represent the same unlabeled graph; \(G\) and the \(I\) just happened to have a different layout that hid this similarity.

With the two drawings of \(G\) and \(I\) matching, we can find the permutation that maps \(G\) onto \(I\), i.e.,

[1,0,4,2,3] # p(g->i) = [(0,1)(2,4,3)]

We say that the graphs \(G\) and \(I\) are isomorphic because there exists a permutation between them that preserves the adjacency, where isomorphic means ‘equal/same/identical form/shape’. The adjacent vertices of every vertex of \(G\) are the same as those of every corresponding vertex of \(I\), e.g, \(v_0\) of \(G\) is mapped onto is \(v_1\) of \(I\), so since \(v_0\) of \(G\) is adjacent to two vertices of degree 3, so is \(v_1\) of \(I\); indeed, every vertex of \(G\) and its mapped vertex on \(I\) have the same adjacency. By the same token, \(G\) and \(H\) are not isomorphic because there isn’t a permutation that preserves the adjacency of their vertices.

It is challenging to verify that two graphs are isomorphic visually if their diagrams are different. All of the following graphs, regardless of the labeling that we might give to their vertices, are isomorphic to \(G\). Labeling in different ways might lead to the same or different CanDs, AVL and AVMs of \(G\) but, regardless, all of them are the same unlabeled graph, so all of them are isomorphic to \(G\), to \(I\), and to each other.

Now consider the 10-vertex graph \(F_a\) below, found in stackexchange.com, relabeled to follow our practice of using numerical labels instead of lexicographic ones. Are there any permutations that permute \(F_a\) while preserving the adjacency of its labeled vertices? In other words, is there any permutation such that we permute the labels of \(F_a\) to obtain a new graph \(F_x\), then reposition the vertices of \(F_x\) to match those of \(F_a\), and \(F_x\) ends up matching \(F_a\)? Let’s give it a try with a couple of transpositions that turn \(F_a\) into \(F_b\) and \(F_c\), as shown below; we also show their respective CanDs.

Their AVLs are

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

and the permutations that map them are

[0,2,1,3,4,5,6,7,8,9] # p(Fa->Fb) = [(1,2)]
[0,1,2,3,4,5,7,6,8,9] # p(Fa->Fc) = [(6,7)]
[0,2,1,3,4,5,7,6,8,9] # p(Fb->Fc) = [(1,2)(6,7)]

To obtain \(F_b\) we transpose \(v_1\) and \(v_2\) of \(F_a\); to obtain \(F_c\) we transpose \(v_6\) and \(v_7\) of \(F_a\). Now we consider the preservation of adjacency. The vertex \(v_1\) of \(F_a\) has degree 1, while \(v_1\) of \(F_b\) has degree 7, so the permutation \(P_{a\rightarrow b}\) does not preserve adjacency of the labeled vertex. The vertex \(v_6\) of \(F_a\) has degree 3 and is adjacent to a vertex of degree 7, while the vertex \(v_6\) in \(F_c\) has degree 3 but is not adjacent to a vertex of degree 7, so the permutation \(P_{a\rightarrow c}\) does not preserve adjacency of the labeled vertex either. We can spot whether the adjacency of a permuted labeled graph is preserved comparing the CanDs or AVLs before and after the permutation; if they are the same, the adjacencies of the labeled graph are preserved. In this case, the three CanDs and AVLs are different, so the adjacency of the labeled vertices is not preserved.

Now we create the graphs \(F_d\), \(F_e\) and \(F_f\) from \(F_a\). The graph \(F_d\) comes from cycling \(v_0\), \(v_1\) and \(v_9\); \(F_e\) comes from tranposing \(v_3\) with \(v_4\), and \(v_5\) and \(v_6\); finally, in \(F_f\) we transpose \(v_3\) with \(v_5\), \(v_4\) with \(v_6\), and \(v_7\) with \(v_8\).

The permutations that map them are

[1,9,2,3,4,5,6,7,8,0] # p(Fa->Fd) = [(0,1,9)]
[0,1,2,4,3,6,5,7,8,9] # p(Fa->Fe) = [(3,4)(5,6)]
[0,1,2,5,6,3,4,8,7,9] # p(Fb->Ff) = [(3,5)(4,6)(7,8)]

It turns out that \(F_d\), \(F_e\) and \(F_f\) have the same CanD and AVL as \(F_a\). The permutations used to create \(F_d\), \(F_e\) and \(F_f\) preserve the adjacencies of the labeled vertices of \(F_a\). This means that \(v_0\) of \(F_a\) has exactly the same adjacencies as \(v_0\) of \(F_d\), \(F_e\) and \(F_f\), i.e., in each case \(v_0\) is adjacent only to \(v_2\); the same adjacency preservation applies to all the other vertices as well. We say that \(F_d\), \(F_e\) and \(F_f\) are automorphisms of \(F_a\), where automorphic means ‘self form/shape’.

We have arrived to an intuive idea of what it means for two graphs to be isomorphic or for a graph to have automorphisms. Now let’s go ahead with the formal definition and the equivalent intuitive ones.

Two graphs are isomorphic when…

• they are the same unlabeled graph when we remove their labels
• there exist a permutation of the labels of one onto the other that preserves the adjacency
• they are the same graph with, maybe, relabeled vertices and/or different drawing

Two graphs are automorphic of each other when…

• they are the same labeled graph, maybe drawn in a different way
• there exist a permutation onto itself that preserves the adjacency of their labeled vertices
• their CanDs, AVLs and AVMs are equal

Hopefully it is clear, then, that all automorphic pairs of graphs are also isomorphic, but not all isomorphic pairs of graphs are necessarily automorphic. All automorphic graphs have the same CanD, AVL and AVM, but a pair of graphs might be isomorphic and still have different CanDs, AVLs and AVMs.

We have discussed when two graphs are isomorphic and when they are automorphic. Coming up with an algorithm to solve either problem for the general case is an open problem, which is an issue since being able to establish the equality of graphs is important for the field of graph theory. In graph theory, being equal might mean either of two things: that the graphs represent the same unlabeled graph, i.e., the graphs are isomorphic, or that the labeled graphs are the same, i.e., the graphs are automorphic.

First published on Mar. 8/2026