Vertex-Transitivity as a Symmetry Condition
A graph may have many symmetries, but vertex-transitivity asks for a specific kind: every vertex can be carried to every other vertex without changing which pairs are adjacent. This property is useful when a question about a graph appears to depend on the vertex chosen. If an automorphism carries one vertex to another, then any structure preserved by adjacency is transported along with it.
Throughout, graphs are finite and simple. For a graph \(G=(V,E)\), an automorphism is a bijection \(\varphi:V\to V\) such that for every pair of vertices \(x,y\), \(xy\in E\) if and only if \(\varphi(x)\varphi(y)\in E\). The “if and only if” matters: an automorphism preserves both edges and nonedges.
Equivalently, the vertices form one orbit under the automorphisms: the orbit of \(u\) is the set of all vertices \(\varphi(u)\) as \(\varphi\) ranges over the automorphisms. Indeed, if every vertex can be carried to \(u\), this orbit is all of \(V\); if the orbit is all of \(V\), then for any \(u,v\) there is an automorphism carrying \(u\) to \(v\). Thus the definition concerns the action of symmetries on vertices, not whether every permutation of vertices is allowed.
Cycles and Complete Graphs
Worked Example: Rotations Make Every Cycle Vertex-Transitive
For \(n\ge 3\), define \(C_n=(V,E)\) by \(V=\{0,1,\ldots,n-1\}\) and \(E=\{i(i+1):0\le i<n-1\}\cup\{(n-1)0\}\). Indices around the cycle can be read modulo \(n\). Choose any two vertices \(a,b\), and define \(\varphi(i)=i+(b-a)\pmod n\).
This is a bijection: its inverse is \(i\mapsto i-(b-a)\pmod n\). It sends \(a\) to \(b\). If \(ij\) is an edge of \(C_n\), then \(j=i+1\) or \(i=j+1\) modulo \(n\). Adding the same number to both endpoints preserves that relation, so \(\varphi(i)\varphi(j)\) is also an edge. The inverse has the same property, so edges and nonedges are both preserved. Hence \(\varphi\) is an automorphism, and \(C_n\) is vertex-transitive.
Check: in \(C_5\), take \(a=1\) and \(b=4\). The map is \(\varphi(i)=i+3\pmod 5\), so \(0,1,2,3,4\) map to \(3,4,0,1,2\), respectively. The cycle edges \(01,12,23,34,40\) map to \(34,40,01,12,23\), which are exactly the cycle edges.
Worked Example: Every Complete Graph Is Vertex-Transitive
Define \(K_n=(V,E)\) by \(V=\{1,\ldots,n\}\) and \(E=\{xy:x,y\in V,\ x\ne y\}\), for \(n\ge1\). For any chosen \(a,b\in V\), choose a permutation \(\varphi\) of \(V\) with \(\varphi(a)=b\); for example, use the transposition that swaps \(a\) and \(b\) if they differ, and the identity if they agree.
For distinct \(x,y\), their images \(\varphi(x),\varphi(y)\) are distinct because \(\varphi\) is injective. Every pair of distinct vertices in \(K_n\) is an edge, so \(xy\) is an edge exactly when \(\varphi(x)\varphi(y)\) is an edge. Thus \(\varphi\) is an automorphism taking \(a\) to \(b\). This also handles \(n=1\): the only vertex maps to itself under the identity, so \(K_1\) is vertex-transitive.
Check: in \(K_4\), take \(a=2\), \(b=4\), and swap 2 with 4 while fixing 1 and 3. The six edges \(12,13,14,23,24,34\) map to \(14,13,12,34,23,24\); this is the same set of six edges.
The Hypercube: Coordinate Symmetry
Worked Example: Coordinatewise Addition Maps Any Cube Vertex to Any Other
For \(d\ge1\), define the \(d\)-dimensional cube \(Q_d=(V,E)\) by \(V=\{0,1\}^d\), the binary strings of length \(d\), and by taking \(xy\in E\) exactly when \(x\) and \(y\) differ in one coordinate. For binary strings, write \(x\oplus y\) for coordinatewise addition modulo two.
Given any \(a,b\in V\), set \(c=a\oplus b\) and define \(\varphi(x)=x\oplus c\). Since adding \(c\) twice returns the original string, \(\varphi(\varphi(x))=x\); thus \(\varphi\) is a bijection. Also, \(\varphi(a)=a\oplus(a\oplus b)=b\). For each coordinate, \(x\) and \(y\) differ there exactly when \(x\oplus c\) and \(y\oplus c\) differ there: adding the same binary coordinate to both entries either changes both or changes neither. Therefore the number of differing coordinates is preserved, and in particular adjacency is preserved in both directions. So \(\varphi\) is an automorphism, proving that \(Q_d\) is vertex-transitive.
For a numerical check, take \(Q_3\), \(a=101\), and \(b=011\). Then \(c=101\oplus011=110\), so \(\varphi(x)=x\oplus110\) and \(\varphi(101)=011\). The edge \(000\,100\) maps to \(110\,010\). These images differ in just the first coordinate, so the image is still an edge.
Check: \(\varphi\) is its own inverse, since \((x\oplus110)\oplus110=x\) for every \(x\). Consequently, the map cannot identify two distinct cube vertices, and the adjacency-preservation check applies in both directions.
The Petersen Graph: Relabeling the Underlying Set
Worked Example: Two-Element Subsets Give a Transitive Petersen Graph
Let the underlying set be \(S=\{1,2,3,4,5\}\). Define a graph \(P=(V,E)\) whose vertices are the two-element subsets of \(S\), with two vertices adjacent exactly when the subsets are disjoint. In set notation, \(V=\{U\subseteq S:|U|=2\}\) and \(E=\{UW:U,W\in V,\ U\cap W=\varnothing\}\). This is the standard two-subset representation of the Petersen graph.
Take any two vertices \(U,W\), so \(|U|=|W|=2\). Choose a bijection from \(U\) to \(W\) and a bijection from \(S\setminus U\) to \(S\setminus W\). Together these define a permutation \(\pi:S\to S\) with \(\pi(U)=W\). Define \(\Phi\) on graph vertices by \(\Phi(A)=\{\pi(x):x\in A\}\). This is a bijection on the two-element subsets, with inverse induced by \(\pi^{-1}\). Moreover, \(A\cap B=\varnothing\) exactly when \(\pi(A)\cap\pi(B)=\varnothing\), because \(\pi\) is a bijection. Hence \(\Phi\) preserves adjacency in both directions and is an automorphism of \(P\) carrying \(U\) to \(W\). Since \(U,W\) were arbitrary, the Petersen graph is vertex-transitive.
For a specific map, take \(U=\{1,2\}\) and \(W=\{4,5\}\), and let \(\pi\) swap 1 with 4 and 2 with 5 while fixing 3. Then \(\Phi(\{1,2\})=\{4,5\}\). The vertex \(\{1,3\}\) is adjacent to \(\{2,4\}\), because those two subsets are disjoint. Their images are \(\{3,4\}\) and \(\{1,5\}\), which are also disjoint, confirming this adjacency is preserved.
Check: both displayed pairs of subsets are disjoint: \(\{1,3\}\cap\{2,4\}=\varnothing\) and \(\{3,4\}\cap\{1,5\}=\varnothing\). The same argument works for every pair of vertices, not just the displayed pair, because any underlying permutation preserves whether two subsets intersect.
Why the Automorphism Check Matters
In each example, the proof has two parts: construct a bijection sending the selected vertex to the target, then verify that adjacency is preserved. The first part alone is not enough. A permutation of the vertex set may move the desired vertex but fail to preserve the graph.
Common mistake: suppose one argues that every permutation of the vertices of a cycle is an automorphism. In \(C_5\), with edges \(01,12,23,34,40\), consider the permutation swapping 1 and 2 and fixing the other vertices. The edge \(01\) is sent to \(02\), but \(02\notin E(C_5)\). So that permutation is not an automorphism. The correction is to use a permutation with a verified adjacency rule, such as the rotation \(i\mapsto i+k\pmod 5\). In general, vertex-transitivity requires a suitable automorphism for each chosen pair; it does not license arbitrary rearrangements.
The examples use different mechanisms—rotation, unrestricted relabeling of a complete graph, coordinate translation, and relabeling an underlying set—but each gives a direct symmetry proof. Once an automorphism taking \(u\) to \(v\) is known, any adjacency-defined feature at \(u\) is carried to the corresponding feature at \(v\). This is why vertex-transitivity lets us study one representative vertex when analyzing a property that is preserved by automorphisms.
Check Your Understanding
For each question, justify your answer by specifying the relevant vertex map and checking what it does to adjacency.
- In \(C_7\), give a rotation that maps vertex 2 to vertex 6, using labels modulo 7.
- Why does any permutation of the vertices of \(K_n\) preserve adjacency?
- In \(Q_3\), find the coordinatewise addition map carrying \(001\) to \(110\), and state its inverse.
- In the two-subset representation of the Petersen graph, explain why a permutation of \(\{1,2,3,4,5\}\) induces an automorphism.
- Give a permutation of the vertices of \(C_5\) that is not an automorphism, and identify an edge whose image is not an edge.