The Orbit-Stabilizer Theorem for Graphs

From Symmetries to Vertex Images

A graph can have many automorphisms, but those automorphisms need not send a chosen vertex to different places. Several symmetries may produce the same image of that vertex. The orbit-stabilizer theorem gives the exact relationship: the number of distinct images is the total number of automorphisms divided by the number that fix the vertex. It therefore converts a count of graph symmetries into a count of possible vertex images.

Throughout, graphs are finite and simple. An automorphism of $G=(V,E)$ is a bijection $\varphi:V\to V$ such that, for every pair of distinct vertices $u,v$, $uv\in E$ if and only if $\varphi(u)\varphi(v)\in E$. The set of all automorphisms, with composition, is the automorphism group $\operatorname{Aut}(G)$. It is finite because its elements are permutations of the finite set $V$. Write $|\operatorname{Aut}(G)|$ for its order, that is, its number of elements.

Definition: For a vertex $v\in V$, its orbit is $\operatorname{Orb}(v)=\{\varphi(v):\varphi\in\operatorname{Aut}(G)\}$. Its stabilizer is $\operatorname{Aut}(G)_v=\{\varphi\in\operatorname{Aut}(G):\varphi(v)=v\}$. The stabilizer consists of the automorphisms that fix $v$, not necessarily the other vertices.

The orbit is a set of distinct vertices, while the automorphism group is a set of permutations. Thus, counting automorphisms does not by itself count orbit elements: multiple automorphisms can have the same effect on $v$. The theorem identifies exactly how many automorphisms correspond to each possible image.

The Orbit-Stabilizer Theorem

Theorem (Orbit-Stabilizer for Graphs): If $G$ is a finite graph and $v\in V(G)$, then $$ |\operatorname{Orb}(v)|=\frac{|\operatorname{Aut}(G)|}{|\operatorname{Aut}(G)_v|}. $$ In particular, the order of the stabilizer divides the order of the automorphism group.

Proof. Put $A=\operatorname{Aut}(G)$ and $H=\operatorname{Aut}(G)_v$. For each $\varphi\in A$, consider the left coset $\varphi H=\{\varphi\circ h:h\in H\}$. Define a map from the set of left cosets of $H$ in $A$ to $\operatorname{Orb}(v)$ by $\varphi H\mapsto\varphi(v)$. This map is well-defined: if $\varphi H=\psi H$, then $\psi^{-1}\circ\varphi\in H$, so $\psi^{-1}(\varphi(v))=v$, and therefore $\varphi(v)=\psi(v)$. It is injective because if $\varphi(v)=\psi(v)$, then $\psi^{-1}\circ\varphi$ fixes $v$, hence belongs to $H$; thus $\varphi H=\psi H$. It is surjective because every element of $\operatorname{Orb}(v)$ has the form $\varphi(v)$ for some $\varphi\in A$. So the number of left cosets equals $|\operatorname{Orb}(v)|$. Each coset has $|H|$ elements, since $h\mapsto\varphi\circ h$ is a bijection from $H$ to $\varphi H$, and the cosets partition $A$. Consequently $|A|=|\operatorname{Orb}(v)|\,|H|$, which gives the formula. $\square$

Corollary: If $w\in\operatorname{Orb}(v)$, then exactly $|\operatorname{Aut}(G)_v|$ automorphisms send $v$ to $w$.

Proof. Choose an automorphism $\varphi_0$ with $\varphi_0(v)=w$, which exists by the definition of the orbit. An automorphism $\varphi$ sends $v$ to $w$ exactly when $\varphi_0^{-1}\circ\varphi$ fixes $v$. Thus all such $\varphi$ are precisely the elements of $\varphi_0\operatorname{Aut}(G)_v$. This coset has the same size as the stabilizer, so the number of automorphisms sending $v$ to $w$ is $|\operatorname{Aut}(G)_v|$. $\square$

The theorem applies to each vertex of a nonempty graph. The empty graph has no vertex $v$, so there is no vertex orbit or vertex stabilizer to which this statement applies. No assumption of connectedness is required.

Worked Applications

Worked Example: The Orbit of a Vertex in a 5-Cycle

Let $G=C_5$ have vertex set $V=\{0,1,2,3,4\}$ and edge set $E=\{01,12,23,34,40\}$, with indices understood modulo $5$. Find the order of its automorphism group, and determine the orbit and stabilizer of vertex $0$.

An automorphism can send $0$ to any of the five vertices. Once its image $a$ is chosen, the image of $1$ must be one of the two neighbors $a+1$ or $a-1$ of $a$. After these first two images are chosen, the rest of the cycle is forced: at each step the next vertex must map to the neighbor of the current image other than the image of the preceding vertex. The resulting maps are exactly $i\mapsto a+i$ and $i\mapsto a-i$ modulo $5$, where $a\in\{0,1,2,3,4\}$. Each map preserves the cycle edges, and the choices give $5\cdot2=10$ distinct automorphisms. Hence $|\operatorname{Aut}(G)|=10$.

Every vertex can be the image of $0$, so $\operatorname{Orb}(0)=\{0,1,2,3,4\}$ and $|\operatorname{Orb}(0)|=5$. To fix $0$, the map must have $a=0$; the two possibilities are $i\mapsto i$ and $i\mapsto-i$ modulo $5$. Thus $|\operatorname{Aut}(G)_0|=2$. The theorem checks the count: $$ \frac{|\operatorname{Aut}(G)|}{|\operatorname{Aut}(G)_0|} =\frac{10}{2}=5 =|\operatorname{Orb}(0)|. $$

Check: For any specified image $a$, there are exactly two maps in the list, $i\mapsto a+i$ and $i\mapsto a-i$. There are five possible images, each occurring twice, giving $5\cdot2=10$ automorphisms in total.

Worked Example: Different Orbits in a Star

Let $G=K_{1,3}$ have vertex set $V=\{c,a,b,d\}$ and edge set $E=\{ca,cb,cd\}$. Find the orbits and stabilizer sizes for the center and for a leaf.

The center $c$ has degree $3$, while each leaf has degree $1$. An automorphism preserves degrees, so it must fix $c$ and may permute the three leaves. Every permutation of the leaves preserves the edge set, so there are $3\cdot2\cdot1=6$ automorphisms. Therefore $|\operatorname{Aut}(G)|=6$.

The center has orbit $\operatorname{Orb}(c)=\{c\}$, of size $1$, and its stabilizer is the whole group, of size $6$. For the leaf $a$, all three leaves can be its image, so $\operatorname{Orb}(a)=\{a,b,d\}$, of size $3$. An automorphism fixing $a$ can either fix or swap $b$ and $d$, giving $|\operatorname{Aut}(G)_a|=2$. The formula verifies both counts: $$ \frac{6}{6}=1=|\operatorname{Orb}(c)|,\qquad \frac{6}{2}=3=|\operatorname{Orb}(a)|. $$

Check: Exactly two automorphisms send $a$ to any specified leaf: after choosing that image, the two remaining leaves can be mapped in either order. This agrees with the stabilizer size $2$.

Worked Example: The Orbits in a 4-Vertex Path

Let $G=P_4$ have vertex set $V=\{1,2,3,4\}$ and edge set $E=\{12,23,34\}$. Determine the automorphism group and the orbit-stabilizer counts for vertices $1$ and $2$.

The degree-$1$ vertices are $1,4$, and the degree-$2$ vertices are $2,3$; degree preservation means an automorphism must map endpoints to endpoints. If $1$ maps to $1$, its neighbor $2$ must map to $2$, then $3$ to $3$, and $4$ to $4$. If $1$ maps to $4$, the successive images are forced to be $3,2,1$. Both resulting maps preserve the edges, so $\operatorname{Aut}(G)$ has order $2$: the identity and the reversal.

Consequently $\operatorname{Orb}(1)=\{1,4\}$, and only the identity fixes $1$, so $|\operatorname{Aut}(G)_1|=1$. Also, $\operatorname{Orb}(2)=\{2,3\}$, and only the identity fixes $2$, so $|\operatorname{Aut}(G)_2|=1$. The formula gives $2/1=2$ for each orbit size. Directly, the identity and reversal give exactly two images for each of these vertices.

Common Counting Pitfall

Do not equate the number of automorphisms with the number of orbit elements. For the 5-cycle above, the incorrect calculation “$|\operatorname{Aut}(C_5)|=10$, so vertex $0$ has 10 images” counts permutations rather than distinct vertices. There are only five vertices in its orbit. The correction is to account for the two automorphisms giving each image: $|\operatorname{Aut}(C_5)_0|=2$, so the orbit has $10/2=5$ elements. More generally, the corollary shows that every image in a given orbit is attained by the same number of automorphisms.

Orbit-stabilizer is useful whenever a symmetry count is easier to obtain than a direct orbit count, or vice versa. The examples show why one must specify the vertex: in the star, the center and a leaf have different orbit sizes and different stabilizer sizes, even though they belong to the same graph. The theorem gives the exact count for each chosen vertex without requiring the graph to be connected or all vertices to have the same kind of symmetry.

Check Your Understanding

Use the definitions and formula above; when counting automorphisms, distinguish them from the distinct images of a vertex.

For $C_5$, how many automorphisms send vertex $0$ to vertex $3$? Explain using the stabilizer.
For the star $K_{1,3}$, verify the orbit-stabilizer formula for a leaf other than $a$.
In $P_4$, which automorphism fixes vertex $3$, and what are its orbit and stabilizer sizes?
Explain why the orbit-stabilizer theorem applies to a disconnected finite graph as long as a vertex $v$ is specified.
If a finite graph has $18$ automorphisms and the stabilizer of $v$ has $3$ elements, what is $|\operatorname{Orb}(v)|$?

The Orbit-Stabilizer Theorem for Graphs

What You'll Learn