Composition and Inverses of Graph Automorphisms

From Graph Symmetries to Algebra

A graph symmetry can be viewed as a relabelling of vertices that leaves adjacency unchanged. Performing one symmetry and then another produces a new relabelling. Reversing a symmetry also gives a relabelling, but it is important to prove that both operations still preserve the graph’s edges. These facts allow all the symmetries of a fixed graph to be treated together as an algebraic object: a group.

Throughout, \(G=(V,E)\) is a finite simple graph unless stated otherwise. Thus each edge is an unordered pair of distinct vertices, and there are no multiple edges. A permutation of \(V\) is a bijection from \(V\) to itself. We use the usual function-composition convention: \((f\circ g)(v)=f(g(v))\), so \(g\) acts first.

The “if and only if” matters. An automorphism preserves both edges and nonedges: it does not turn an edge into a nonedge or a nonedge into an edge. Equivalently, the edge set obtained by applying \(f\) to both endpoints of every edge is exactly \(E\). Since \(f\) is a bijection, its action on unordered pairs is also a bijection.

Composition and Inversion

Proof. First, \(\operatorname{id}_V\) is a bijection. For any \(u,v\in V\), \(uv\in E\) if and only if \(\operatorname{id}_V(u)\operatorname{id}_V(v)=uv\in E\). Hence it is an automorphism.

Now let \(f,g\in\operatorname{Aut}(G)\). Their composition is a bijection because the composition of bijections is a bijection. For any \(u,v\in V\), the defining property of \(g\), followed by that of \(f\), gives \(uv\in E\) if and only if \(g(u)g(v)\in E\), if and only if \(f(g(u))f(g(v))\in E\). Since \(f(g(u))=(f\circ g)(u)\) and likewise for \(v\), the composition preserves adjacency in both directions. Thus \(f\circ g\in\operatorname{Aut}(G)\).

Finally, \(f^{-1}\) is a bijection. Given \(x,y\in V\), put \(u=f^{-1}(x)\) and \(v=f^{-1}(y)\). Then \(xy\in E\) if and only if \(f(u)f(v)\in E\), which, because \(f\) is an automorphism, holds if and only if \(uv\in E\). Since \(u=f^{-1}(x)\) and \(v=f^{-1}(y)\), this proves that \(f^{-1}\) preserves adjacency in both directions. Therefore \(f^{-1}\in\operatorname{Aut}(G)\). \(\square\)

There is also a useful order-reversal rule for inverses. For automorphisms \(f,g\), the inverse of \(f\circ g\) is \(g^{-1}\circ f^{-1}\), not \(f^{-1}\circ g^{-1}\). The reason is that undoing the action of \(g\) followed by \(f\) requires first undoing \(f\), then undoing \(g\).

Proof. For each \(v\in V\), \((\operatorname{id}_V\circ f)(v)=\operatorname{id}_V(f(v))=f(v)\) and \((f\circ\operatorname{id}_V)(v)=f(\operatorname{id}_V(v))=f(v)\). Thus both compositions equal \(f\). \(\square\)

The Automorphisms Form a Group

Proof. A group is a set with an associative binary operation, an identity element, and an inverse for every element. The operation here is composition. The closure theorem above shows that composing two elements of \(\operatorname{Aut}(G)\) gives another element, so composition is a binary operation on this set. Function composition is associative: for any maps \(f,g,h\) and vertex \(v\), both \(((f\circ g)\circ h)(v)\) and \((f\circ(g\circ h))(v)\) equal \(f(g(h(v)))\). The identity map is an automorphism and is an identity for composition. The inverse theorem shows that each automorphism has an inverse in \(\operatorname{Aut}(G)\). All group axioms therefore hold. If \(V=\varnothing\), there is one map from \(V\) to itself, the empty identity map; it is bijective, and the same axioms hold. \(\square\)

In particular, the group operation is not required to commute: \(f\circ g\) and \(g\circ f\) can be different. The group statement concerns closure, associativity, identity and inverses; it does not assert that composition can be reordered.

A Useful Inverse Rule and a Common Pitfall

Proof. By associativity and the inverse identities, \((g^{-1}\circ f^{-1})\circ(f\circ g)=g^{-1}\circ(f^{-1}\circ f)\circ g=g^{-1}\circ\operatorname{id}_V\circ g=\operatorname{id}_V\). In the other order, \((f\circ g)\circ(g^{-1}\circ f^{-1})=f\circ(g\circ g^{-1})\circ f^{-1}=f\circ\operatorname{id}_V\circ f^{-1}=\operatorname{id}_V\). Thus \(g^{-1}\circ f^{-1}\) is the inverse of \(f\circ g\). \(\square\)

A frequent error is to compose vertex images correctly but then calculate an edge image by applying the two maps in the wrong order, or by changing only one endpoint. In the four-cycle example, the edge \(bd\) under \(f\circ g\) must be computed as \(b\mapsto a\) and \(d\mapsto c\), giving \(ac\). It is not \(cd\): that would be the image of \(bd\) under \(g\), before applying \(f\), and it is also not valid to infer the edge image from just one endpoint. Because edges are unordered pairs, the correct result is the pair formed from both final vertex images.

When checking a proposed automorphism on a finite graph, two checks are useful: verify that the vertex map is a bijection, then verify that the images of the edges form exactly the original edge set. Merely showing that each edge maps to some edge establishes edge preservation, but checking the whole edge-image set also helps catch omissions or accidental repetitions. The definition’s “if and only if” is guaranteed here by bijectivity and the equality of the edge sets.