From Local Structure to a Search
An automorphism is a permutation of a graph's vertices that preserves adjacency. The earlier material on graph automorphisms establishes the basic test: a bijection \(f:V(G)\to V(G)\) is an automorphism exactly when \(uv\in E(G)\) if and only if \(f(u)f(v)\in E(G)\). The challenge is that trying all \(n!\) permutations is usually wasteful. Degrees and neighbor counts can rule out many proposed images before a full permutation is known.
The procedure here has two parts. Color refinement repeatedly separates vertices whose local neighborhood counts differ. If several vertices remain indistinguishable, individualization temporarily marks a selected vertex, and backtracking tries its possible images in turn. Refinement is a pruning tool, not a complete test of symmetry: a surviving branch must still produce a full adjacency-preserving bijection.
We begin with the degree coloring: two vertices have the same initial color exactly when they have the same degree. Refinement then uses the number of neighbors in each color class. It is repeated until no class splits. A resulting stable coloring is equitable: vertices in the same class have equal numbers of neighbors in every class. The word “stable” does not mean that vertices in a class are interchangeable by automorphisms.
Synchronized Refinement and Backtracking
To test possible automorphisms of \(G\), maintain two copies of its colored vertex set, called the source and target. Initially, both copies have the same degree colors. A proposed pair \(u\mapsto v\) is individualized by giving \(u\) in the source and \(v\) in the target the same fresh color. Refine both copies using one shared naming of signatures. If a signature occurs a different number of times in the two copies, no adjacency-preserving bijection can respect the proposed pairs, so that branch is discarded.
Whenever a color class becomes a singleton in each copy, its unique source vertex must map to its unique target vertex. If every class is a singleton, these pairings define a bijection. Check every unordered pair of vertices: accept the bijection exactly when an edge is present in the source pair if and only if it is present in the target pair.
If a class \(C\) still has at least two vertices, choose a source vertex \(u\in C\). The corresponding target class \(D\) has the same size. Create one branch for each \(v\in D\), individualizing \(u\mapsto v\), and refine again. To enumerate all automorphisms, retain every accepted leaf, rather than stopping at the first one. A reproducible implementation can choose, for example, a smallest nonsingleton class, breaking ties by its color label, and a fixed vertex order within each class.
Proof. First, refinement and branching are finite. Each refinement either leaves all color classes unchanged or splits at least one class into smaller classes. Since \(G\) has finitely many vertices, only finitely many strict splits can occur. Each branch individualizes one previously unresolved vertex, so the depth of the search is at most \(|V(G)|\). Each branch has finitely many choices. Thus the search terminates.
For soundness, any output is a bijection because each leaf pairs all singleton source classes with their corresponding singleton target classes, and refinement has matched their class sizes. The final check tests every unordered vertex pair. It therefore verifies that adjacency is preserved in both directions, so every output is an automorphism.
For completeness, fix any automorphism \(f\) of \(G\). Initially, \(f\) preserves degrees. At every refinement step, if \(f\) maps each current color class to its corresponding class, then it preserves the number of neighbors a vertex has in each class: adjacency and the class membership of every neighbor are preserved by \(f\). Consequently, \(f\) also preserves the signatures and the refined classes. If a pair \(u\mapsto v\) is individualized and \(f(u)=v\), the new color is respected as well. Now follow the search branch that chooses \(f(u)\) whenever it branches on \(u\). That branch is never discarded by unequal class counts, since \(f\) gives a bijection between its corresponding classes. Eventually it reaches a leaf, where the forced pairing is \(f\) and passes the adjacency check. Thus every automorphism is output. \(\square\)
Worked Examples
Worked Example: Refinement and a Two-Branch Search
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23\}\). The degrees are \(\deg(1)=3\), \(\deg(2)=2\), \(\deg(3)=2\), and \(\deg(4)=1\). The initial degree classes are therefore \(\{1\},\{2,3\},\{4\}\). In the class \(\{2,3\}\), each vertex has one neighbor in \(\{1\}\), one in \(\{2,3\}\), and none in \(\{4\}\); refinement does not split the class.
Choose source vertex \(2\). Its corresponding target class is \(\{2,3\}\), so there are two branches:
| Branch | Refinement and forced pairs | Leaf check |
|---|---|---|
| \(2\mapsto2\) | The individualized pair is \(2\mapsto2\). The remaining vertex in the class is forced to map \(3\mapsto3\); the singleton degree classes give \(1\mapsto1\) and \(4\mapsto4\). | Identity map; all four edges are preserved. |
| \(2\mapsto3\) | The individualized pair is \(2\mapsto3\). The remaining vertex is forced to map \(3\mapsto2\); the other pairs are \(1\mapsto1\) and \(4\mapsto4\). | The edge set maps to itself, so accept. |
For the second branch, the images of \(12,13,14,23\) are respectively \(13,12,14,23\), all of which belong to \(E\). Both branches have now been checked, so the output consists of the identity and the permutation that swaps \(2\) and \(3\) while fixing \(1\) and \(4\).
Check: The two accepted maps are distinct, and the proposed swap preserves every edge and nonedge: it exchanges \(12\) with \(13\), leaves \(14\) and \(23\) in place, and exchanges the nonedges \(24\) and \(34\). This independently verifies the output.
Worked Example: Refinement Distinguishes an Asymmetric Tree
Let \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,13,34,15,56,67\}\). The degrees are \(\deg(1)=3\); \(\deg(2)=\deg(4)=\deg(7)=1\); and \(\deg(3)=\deg(5)=\deg(6)=2\). Thus the initial classes are \(A=\{1\}\), \(B=\{2,4,7\}\), and \(C=\{3,5,6\}\).
In the first refinement, vertex \(2\) has one neighbor in \(A\), while vertices \(4\) and \(7\) each have one neighbor in \(C\). Hence \(B\) splits into \(\{2\}\) and \(\{4,7\}\). Among the degree-two vertices, \(3\) has one neighbor in \(A\) and one in \(\{4,7\}\); \(5\) has one neighbor in \(A\) and one in \(C\); and \(6\) has one neighbor in \(C\) and one in \(\{4,7\}\). These three different signatures split \(C\) into \(\{3\},\{5\},\{6\}\).
In the next refinement, \(4\) and \(7\) split: vertex \(4\) is adjacent to \(3\), whereas vertex \(7\) is adjacent to \(6\). Every class is now a singleton. The forced correspondence between the two copies is the identity, so it is the only possible output.
Check: The class calculations used the listed edges: \(2\) is adjacent to \(1\); \(4\) to \(3\); \(7\) to \(6\); \(3\) to \(1,4\); \(5\) to \(1,6\); and \(6\) to \(5,7\). Independently, any automorphism must fix vertex \(1\), the unique degree-three vertex. Its three branches from \(1\) have lengths \(1,2,3\), respectively, so each branch and each vertex on it must be fixed. This verifies that the identity is the full output.
Worked Example: A Branch Pruned by Neighbor Counts
Let \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,23,31,45,56,67,74\}\). This graph has two components: a triangle on \(\{1,2,3\}\) and a four-cycle on \(\{4,5,6,7\}\). Every vertex has degree \(2\), so the initial coloring has just one class, containing all seven vertices.
Choose source vertex \(1\). Consider the branch proposing \(1\mapsto4\). After individualization, the source root \(1\) and target root \(4\) have a fresh shared color. In each copy, the two neighbors of the root form one class of size \(2\), and the four other vertices form a class of size \(4\). Counts still agree, so refine again. In the source, each of \(2,3\) has one neighbor in the root class and one in the class \(\{2,3\}\). In the target, each of \(5,7\) has one neighbor in the root class and one in the class of four nonneighbors of the root. The corresponding signatures have different neighbor counts, so the branch is pruned. In particular, refinement has detected that the proposed root images cannot correspond.
For a complete output description, a component cannot map to one of a different size. On the triangle component there are \(3\cdot2\cdot1=6\) adjacency-preserving bijections: choose the image of vertex \(1\) in \(3\) ways, then the image of \(2\) in \(2\) ways, after which the image of \(3\) is forced. On the four-cycle, choose the image of \(4\) in \(4\) ways and the image of its neighbor \(5\) in \(2\) ways. The images of \(6\) and \(7\) are then forced by adjacency, giving \(4\cdot2=8\) choices. The algorithm therefore returns the \(6\cdot8=48\) combinations of these component-preserving maps.
Check: Each of the six triangle maps preserves all three triangle edges. Each of the eight four-cycle maps sends the successive cycle edges to successive cycle edges, and the two components have no edges between them. Thus all \(48\) combinations preserve adjacency. Conversely, component sizes prevent mixing the components, and the choices just counted exhaust the possible maps on each one.
What Refinement Can and Cannot Do
Refinement is useful because it turns degree and neighborhood information into immediate constraints. A proposed image in a different current color class is impossible, and a mismatch between class sizes proves that a branch cannot extend to an automorphism. Individualization creates new information about distances and neighborhoods relative to selected vertices. Repeating it can separate vertices that were tied at the start.
However, equal signatures do not prove that two vertices can be exchanged. The triangle-and-four-cycle example began with one degree class and only separated the incompatible root proposal after individualization and further neighbor counts. Even a branch that survives all refinement steps may fail the final adjacency test. The correctness guarantee comes from examining every branch that could contain an automorphism and checking each completed bijection—not from treating stable color classes as automorphism classes.
The search can still be large: an edgeless graph, for example, has no degree distinctions to exploit and has many automorphisms to output. Refinement reduces work when local structure is informative, while backtracking supplies completeness when it is not. This distinction is important in practical graph-isomorphism and symmetry software: refinement is a necessary filter, not by itself a certificate of an automorphism.
Check Your Understanding
Use the definitions and search logic above to answer the following.
- Why must an automorphism map every degree class to itself?
- In synchronized refinement, what does a mismatch in the number of vertices with one signature establish?
- Why is checking only the edges, without checking nonedges, not the stated leaf test for a bijection?
- Give a reason that a stable color class need not consist of vertices that can be exchanged by an automorphism.
- For the graph in the first worked example, verify directly that swapping \(2\) and \(3\) preserves both edges and nonedges.