Automorphism Groups of Paths, Cycles, and Complete Graphs

Why These Three Families Are Special

An automorphism is a symmetry of a graph expressed as a permutation of its vertices. For paths, the endpoints sharply limit where a symmetry can send the graph. A cycle has no endpoints, so it allows rotations as well as reflections. In a complete graph, every pair of distinct vertices is adjacent, leaving no adjacency restriction on a permutation. These contrasts make paths, cycles and complete graphs useful first examples of automorphism groups.

All graphs in this tutorial are finite and simple. For a graph \(G=(V,E)\), a permutation \(\varphi:V\to V\) is an automorphism if, for all distinct \(u,v\in V\), \(uv\in E\) if and only if \(\varphi(u)\varphi(v)\in E\). The set of all automorphisms, with composition as its operation, is the automorphism group \(\operatorname{Aut}(G)\). Composition means applying the rightmost map first. The identity map is an automorphism; the composition of two automorphisms preserves adjacency; and the inverse of an automorphism preserves adjacency as well. Thus these permutations form a group.

One useful consequence of the definition is that automorphisms preserve degrees. Indeed, the neighbors of \(v\) are carried bijectively to the neighbors of \(\varphi(v)\): adjacency is preserved in both directions, and \(\varphi\) is a bijection. Hence \(\deg(v)=\deg(\varphi(v))\). Automorphisms also preserve distances, since they carry paths to paths of the same length, and their inverses give the reverse distance inequality.

Automorphisms of Paths

Proof. For \(n=1\), there is just one vertex and just one permutation of the vertex set, so only the identity is possible. Now let \(n\ge2\), and label the vertices of \(P_n\) in order as \(1,2,\ldots,n\), with edges \(i(i+1)\) for \(1\le i<n\). Its endpoints are \(1\) and \(n\). If \(n\ge3\), these are exactly the vertices of degree \(1\), so any automorphism must send endpoint \(1\) to either \(1\) or \(n\). If \(n=2\), both vertices are endpoints, and the same two possibilities apply to the image of \(1\).

Distances from an endpoint determine every vertex: the vertex at distance \(i-1\) from endpoint \(1\) is \(i\), and the vertex at distance \(i-1\) from endpoint \(n\) is \(n+1-i\). Since an automorphism preserves distances, if it sends \(1\) to \(1\), it must send every \(i\) to \(i\); if it sends \(1\) to \(n\), it must send every \(i\) to \(n+1-i\). Both resulting maps preserve the listed edges: the identity fixes each edge, and reversal sends \(i(i+1)\) to \((n-i)(n+1-i)\), also an edge of the path. For \(n\ge2\) the two maps differ at vertex \(1\). Thus there are exactly two. \(\square\)

Automorphisms of Cycles

For \(n\ge3\), label the vertices of \(C_n\) by the residues \(0,1,\ldots,n-1\), with addition interpreted modulo \(n\). Its edge set consists of \(i(i+1)\) for all residues \(i\). Define \(r(i)=i+1\) and \(s(i)=-i\), with values taken modulo \(n\). The map \(r\) rotates the cycle by one place, and \(s\) reflects it.

Proof. Let \(\varphi\) be an automorphism. Vertex \(0\) can map to any residue \(a\), giving \(n\) choices. After \(a=\varphi(0)\) is chosen, vertex \(1\) must map to one of the two neighbors of \(a\), namely \(a+1\) or \(a-1\). Once these images are chosen, the rest of the images are forced in sequence: for \(1\le i\le n-2\), vertex \(i+1\) is adjacent to \(i\), and its image must be the neighbor of \(\varphi(i)\) other than \(\varphi(i-1)\). The two neighbors are distinct, and injectivity prevents \(\varphi(i+1)=\varphi(i-1)\). This gives either \(\varphi(i)=a+i\) throughout or \(\varphi(i)=a-i\) throughout.

Each displayed form really is an automorphism. An edge with endpoints \(i,i+1\) maps under the first form to the pair \(a+i,a+i+1\), and under the second to \(a-i,a-i-1\); in both cases the images are consecutive residues and hence adjacent. There are \(n\) maps of each form. They are all distinct: maps with different \(a\) have different images of \(0\), and the two forms with the same \(a\) differ at \(1\), since \(a+1\not\equiv a-1\pmod n\) for \(n\ge3\). Therefore there are exactly \(2n\) automorphisms.

In group notation, the maps \(r\) and \(s\) generate all these automorphisms: the rotations are \(r^a\), and the reflections are \(r^a s\). They satisfy \(r^n=\mathrm{id}\), \(s^2=\mathrm{id}\), and \(srs=r^{-1}\). For example, \(srs(i)=i-1=r^{-1}(i)\). These relations describe the dihedral symmetries; here the convention is that the dihedral group of an \(n\)-cycle has order \(2n\). \(\square\)

Automorphisms of Complete Graphs

Proof. In \(K_n\), every pair of distinct vertices is an edge. Let \(\varphi\) be any permutation of the vertices. Distinct vertices \(u,v\) have distinct images \(\varphi(u),\varphi(v)\), so their images are adjacent in \(K_n\). Thus every permutation is an automorphism. Conversely, an automorphism is a permutation by definition, so there are no other maps. This argument also covers \(K_1\), whose sole permutation is the identity. Therefore the automorphism group is \(S_n\); the number of permutations is \(n!\), since their images can be selected successively in \(n,n-1,\ldots,1\) ways. \(\square\)

Comparing the Three Families

The classifications reflect what adjacency allows. In a path with at least two vertices, choosing the image of one endpoint determines the entire map. In a cycle, choosing the image of one vertex and then choosing which of its two neighbors receives the next vertex determines the entire map. In a complete graph, there is no special adjacency pattern to constrain the permutation, so every permutation works.

Some graphs belong to more than one family: \(C_3\) is also \(K_3\). The two descriptions agree. The cycle formula gives \(2\cdot3=6\) automorphisms, while \(S_3\) has \(3\cdot2\cdot1=6\) permutations. This agreement is a useful check, not an exception to either classification.

Common Pitfalls

Not every vertex permutation preserves a path. For \(P_4\) with vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34\}\), consider the tempting but incorrect claim that swapping \(2\) and \(3\) while fixing \(1\) and \(4\) is an automorphism. That permutation sends edge \(12\) to \(13\), but \(13\notin E\). The correction is to use structural constraints: an automorphism must send endpoints to endpoints, and the image of one endpoint determines all vertices by their distances from it.

Do not count only rotations of a cycle. A cycle has reflections as well as rotations. For \(C_4\), counting only the four rotations misses the four reflections listed above. The correction is to choose both the image of a starting vertex and which of its two neighbors is the image of a chosen adjacent vertex. Those choices yield \(n\cdot2\) automorphisms.