Automorphisms as Adjacency-Preserving Permutations

Automorphisms as Permutations of the Vertices

A graph may have symmetries: relabeling its vertices can leave every adjacency relation unchanged. To describe such a symmetry precisely, we use a permutation of the vertex set. The key is that adjacency must be preserved in both directions: an edge must map to an edge, and a nonedge must remain a nonedge. This condition lets us test a proposed symmetry using the graph's edge list.

Throughout, graphs are finite and simple, undirected, and have no loops or multiple edges. A permutation of a set $V$ is a bijection from $V$ to itself. For a permutation $\varphi$, the notation $\varphi(u)$ means the image of vertex $u$. We write $uv$ for the unordered pair $\{u,v\}$.

Definition: An automorphism of $G=(V,E)$ is a permutation $\varphi:V\to V$ such that, for every pair of distinct vertices $u,v\in V$, $$ uv\in E \quad\Longleftrightarrow\quad \varphi(u)\varphi(v)\in E. $$ The condition says that $\varphi$ preserves both adjacency and nonadjacency.

For example, cycle notation $(1\ 2\ 3\ 4)$ specifies the permutation sending $1$ to $2$, $2$ to $3$, $3$ to $4$, and $4$ to $1$. Vertices not appearing in a cycle of this notation are fixed. A permutation is only a candidate symmetry: it is an automorphism only if it satisfies the adjacency condition.

The Edge-Set Test

Theorem: Let $G=(V,E)$ be a finite simple graph and let $\varphi$ be a permutation of $V$. Then $\varphi$ is an automorphism if and only if $$ \{\varphi(u)\varphi(v):uv\in E\}=E. $$

Proof. Suppose first that $\varphi$ is an automorphism. For every edge $uv\in E$, the defining condition gives $\varphi(u)\varphi(v)\in E$. Thus the set on the left is contained in $E$. The map on unordered vertex pairs that sends $uv$ to $\varphi(u)\varphi(v)$ is a bijection, because $\varphi$ is a bijection. Its restriction to the finite edge set therefore has $|E|$ distinct images. Those images lie in $E$, which also has $|E|$ elements, so the image set equals $E$.

Conversely, suppose the image edge set equals $E$. If $uv\in E$, its image $\varphi(u)\varphi(v)$ belongs to $E$. Now suppose $\varphi(u)\varphi(v)\in E$. Since the image edge set equals $E$, there is an edge $xy\in E$ with $\varphi(x)\varphi(y)=\varphi(u)\varphi(v)$. Because $\varphi$ is a bijection, its action on unordered pairs is injective, so $xy=uv$. Hence $uv\in E$. Both directions of the adjacency condition hold, and $\varphi$ is an automorphism. $\square$

This theorem makes an edge-list test possible: list the image of each edge, then compare the resulting set with the original edge set. A bijection is essential. Mapping some edges into $E$ is not by itself enough to establish an automorphism if the map is not a permutation.

Worked Example: A Rotation of a 4-Cycle

Let $G=(V,E)$, where $V=\{1,2,3,4\}$ and $E=\{12,23,34,14\}$. Consider $\varphi=(1\ 2\ 3\ 4)$, so that $1\mapsto2$, $2\mapsto3$, $3\mapsto4$, and $4\mapsto1$. This is a permutation because every vertex appears exactly once among the images.

Map each edge, one at a time: $12\mapsto23$, $23\mapsto34$, $34\mapsto41=14$, and $14\mapsto21=12$. Thus the image edge set is $\{23,34,14,12\}$, which equals $E=\{12,23,34,14\}$. The edge-set test proves that $\varphi$ is an automorphism.

Check: The nonedges are $13$ and $24$. Their images are $24$ and $31=13$, respectively, so both remain nonedges. This directly checks the other direction of adjacency preservation as well.

Worked Example: Swapping Two Vertices While Fixing the Others

Let $G=(V,E)$, where $V=\{1,2,3,4\}$ and $E=\{12,13,14,23\}$. Consider $\varphi=(2\ 3)$, which exchanges $2$ and $3$ and fixes $1$ and $4$.

The edge images are $12\mapsto13$, $13\mapsto12$, $14\mapsto14$, and $23\mapsto32=23$. Therefore the image edge set is $\{13,12,14,23\}$, the same set as $E$, so $\varphi$ is an automorphism.

Check: There are six unordered pairs of distinct vertices. Four are edges, as listed in $E$; the remaining pairs are $24$ and $34$. Under $\varphi$, $24\mapsto34$ and $34\mapsto24$, so these nonedges are exchanged. Every pair is accounted for, in agreement with the edge-set test.

Consequences for Neighborhoods and Degrees

For a vertex $v$, its neighborhood $N(v)$ is the set of vertices adjacent to $v$, and its degree is $\deg(v)=|N(v)|$. Automorphisms preserve these local quantities, but this preservation is a consequence of the full adjacency condition, not a replacement for it.

Proposition: If $\varphi$ is an automorphism of a finite simple graph $G$, then $$ \varphi(N(v))=N(\varphi(v)) \quad\text{and}\quad \deg(v)=\deg(\varphi(v)) $$ for every $v\in V(G)$.

Proof. If $x\in N(v)$, then $vx\in E$. Since $\varphi$ preserves adjacency, $\varphi(v)\varphi(x)\in E$, so $\varphi(x)\in N(\varphi(v))$. This proves $\varphi(N(v))\subseteq N(\varphi(v))$. Conversely, let $y\in N(\varphi(v))$. Since $\varphi$ is a permutation, there is a vertex $x$ with $y=\varphi(x)$. The edge $\varphi(v)\varphi(x)$ implies $vx\in E$ by the reverse direction of the automorphism condition. Thus $x\in N(v)$, and $y\in\varphi(N(v))$. The neighborhood sets are equal. Since $\varphi$ is a bijection, their sizes are equal, giving $\deg(v)=\deg(\varphi(v))$. $\square$

A useful necessary test follows: if a proposed permutation sends a vertex to one of a different degree, it cannot be an automorphism. The converse is false. Preserving every vertex's degree does not guarantee that the permutation preserves which pairs are adjacent.

An Adjacency-Matrix Criterion

The same condition can be expressed with matrices. Choose an ordering of $V$, and let $\mathbf{A}(G)$ be the adjacency matrix: its entry in row $u$, column $v$ is $1$ if $uv\in E$ and $0$ otherwise. Define the permutation matrix $\mathbf{Q}$ by setting $\mathbf{Q}_{x,u}=1$ when $x=\varphi(u)$, and setting all its other entries to $0$. Thus column $u$ of $\mathbf{Q}$ has its $1$ in row $\varphi(u)$.

Theorem: With this convention for $\mathbf{Q}$, a permutation $\varphi$ is an automorphism of $G$ if and only if $$ \mathbf{Q}^{T}\mathbf{A}(G)\mathbf{Q}=\mathbf{A}(G). $$

Proof. For any vertices $u,v$, the $(u,v)$ entry of the matrix on the left is $\mathbf{A}(G)_{\varphi(u),\varphi(v)}$: multiplication by $\mathbf{Q}$ selects the rows and columns indexed by the images of $u$ and $v$. That entry is $1$ exactly when $\varphi(u)\varphi(v)\in E$. The $(u,v)$ entry of $\mathbf{A}(G)$ is $1$ exactly when $uv\in E$. Therefore equality of the matrices holds exactly when these two adjacency indicators agree for every $u,v$. For $u\ne v$, this is the defining condition for an automorphism. For $u=v$, both entries are $0$, since the graph is simple and the diagonal of its adjacency matrix is zero. Hence the matrix equality is equivalent to the automorphism condition. $\square$

The matrix criterion packages all pairwise checks into one equality. For small graphs, the edge-set test is often quicker by hand; the matrix form is useful when studying symmetries through algebraic representations of a graph.

Worked Example: Degree Preservation Is Not Sufficient

Let $G=(V,E)$, where $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$. Consider the permutation $\varphi=(1\ 4)$, which exchanges $1$ and $4$ and fixes $2$ and $3$.

The degrees are $\deg(1)=1$, $\deg(2)=2$, $\deg(3)=2$, and $\deg(4)=1$. The permutation sends the degree-$1$ vertices to degree-$1$ vertices and fixes both degree-$2$ vertices, so $\deg(\varphi(v))=\deg(v)$ for each vertex. Now map the edges: $12\mapsto42=24$, $23\mapsto23$, and $34\mapsto31=13$. The image edge set is $\{24,23,13\}$, which differs from $E=\{12,23,34\}$. Therefore $\varphi$ is not an automorphism.

Check: The pair $12$ is an edge, but its image $24$ is not in $E$. This single pair already violates adjacency preservation. The degree check was valid, but it was only a necessary condition, not a sufficient one.

Degenerate Cases and a Reliable Test

The definition also covers graphs with very few vertices. On the empty graph, the unique map from the empty vertex set to itself is a permutation, and the adjacency condition has no vertex pairs to check; it is an automorphism. On a graph with one vertex and no edges, the only permutation fixes that vertex and is an automorphism. These cases also satisfy the edge-set test: both the original and image edge sets are empty.

For a nonempty graph, a practical test is to verify first that the proposed map is a permutation, then compute every edge image. Equality of the image edge set and $E$ proves the full if-and-only-if adjacency condition. Degree preservation can quickly reject some candidates, but it cannot certify one. Automorphisms are useful because they identify vertices and edges that play structurally identical roles; the edge and matrix tests give precise ways to establish that a proposed relabeling really has this property.

Common Pitfall

Do not replace adjacency checks with degree checks. In the last example, every vertex keeps its degree under the proposed permutation, but the edge $12$ maps to the nonedge $24$. The correction is to check adjacency itself, either pair by pair or by proving that the image edge set equals the original edge set. Conversely, do not check only that each original edge maps to some edge unless the map is known to be a permutation on a finite vertex set; the edge-set theorem relies on bijectivity.

Check Your Understanding

For each question, state the graph and permutation precisely, and justify any claim that a map is or is not an automorphism.

For $V=\{1,2,3\}$ and $E=\{12,23,13\}$, test the permutation $(1\ 2\ 3)$ using the edge-set criterion.
Give the adjacency-matrix condition for a permutation to be an automorphism, using the convention for the permutation matrix defined above.
Prove that an automorphism maps the set of vertices of degree $k$ onto itself for every nonnegative integer $k$.
Explain why equal degrees at the images of all vertices are necessary for an automorphism but are not sufficient, using the path on four vertices as an example.