Graph isomorphism
Graph isomorphism is the equivalence relation under which two graphs represent the same adjacency structure after their vertices have been renamed. The associated computational problem asks whether such a renaming exists. Although the definition is elementary, the problem has played a central role in the study of computational complexity, combinatorial symmetry, and algorithms for discrete structures.
The standard formulation concerns finite simple graphs whose edges have no orientation. Variants extend the same principle to directed graphs, to graphs carrying vertex or edge labels, and to relational structures of higher arity. These variants differ in their computational details, but many reduce to the ordinary graph problem through structure-preserving encodings.
Definition
Let (G=(V_G,E_G)) and (H=(V_H,E_H)) be graphs. An isomorphism from (G) to (H) is a bijection
[ f:V_G\rightarrow V_H ]
such that, for every pair (u,v\in V_G),
[ {u,v}\in E_G \quad\Longleftrightarrow\quad {f(u),f(v)}\in E_H. ]
When such a bijection exists, the graphs are isomorphic, written (G\cong H). Isomorphism therefore preserves every property determined solely by adjacency. The number of vertices remains unchanged, as does the number of edges. Vertex degrees are preserved under the bijection, while paths, cycles, connected components, and induced subgraphs are transferred to corresponding structures.
Agreement on these invariants does not in general establish isomorphism. Two nonisomorphic graphs may have the same degree sequence and the same number of cycles of several lengths. They may also share the same spectrum, because equality of the eigenvalues of an adjacency matrix is weaker than equivalence under simultaneous permutation of its rows and columns.
An isomorphism from a graph to itself is an automorphism. The automorphisms of (G), equipped with composition, form the group (\operatorname{Aut}(G)). This group records the internal symmetries of the graph and acts on its vertex set. Vertices lying in the same orbit under this action cannot be distinguished by any property invariant under automorphisms.
Matrix formulation
After an ordering has been assigned to the vertices, a graph is represented by an adjacency matrix (A_G). Two graphs with the same number of vertices are isomorphic exactly when a permutation matrix (P) satisfies
[ A_H=P^{\mathsf T}A_GP. ]
This equation expresses vertex renaming as a simultaneous permutation of matrix rows and corresponding matrix columns. It also distinguishes graph isomorphism from ordinary matrix similarity, which permits arbitrary invertible transformations and consequently identifies many matrices that do not encode isomorphic graphs.
The matrix formulation connects graph isomorphism with group actions. A permutation of the vertex set acts on adjacency matrices by conjugation, and each orbit of this action consists of all labeled representations of a single unlabeled graph. The stabilizer of a matrix under the action is isomorphic to the automorphism group of the represented graph.
Computational problem
In the decision version of the graph-isomorphism problem, the input consists of two encoded graphs and the output specifies whether they are isomorphic. A proposed vertex bijection can be checked in polynomial time, so the problem belongs to the complexity class NP. It is not known to be solvable in polynomial time for unrestricted graphs, and it is not known to be NP-complete.
The latter uncertainty has structural significance. If graph isomorphism were NP-complete under standard polynomial-time reductions, the polynomial hierarchy would collapse to a low level. This follows from the placement of graph nonisomorphism in interactive and probabilistic proof systems, together with later refinements locating graph isomorphism in complexity classes below those expected to contain general NP-complete problems.
The search problem asks for an explicit isomorphism rather than a yes-or-no answer. It is polynomial-time reducible to the decision problem through a sequence of constrained comparisons. Computing generators for the automorphism group is closely related, since an isomorphism between two graphs corresponds to a coset of automorphisms whenever one such mapping has been fixed.
A further related task is canonical labeling, which assigns every graph a distinguished labeled representative such that two graphs receive the same representative precisely when they are isomorphic. Canonical labeling directly yields an isomorphism test. The converse relationship also holds through polynomial-time reductions, although the construction requires more than a single decision query because a consistent representative must be selected.
Refinement and structural decomposition
Many graph-isomorphism algorithms begin by partitioning vertices according to isomorphism-invariant information. Degree refinement separates vertices having different numbers of neighbors. Repeated color refinement then replaces each vertex color with data recording its previous color and the multiset of colors appearing among adjacent vertices. The process terminates at an equitable partition, in which vertices in the same cell have identical numbers of neighbors in every cell.
Boris Weisfeiler and Andrei Leman developed the higher-dimensional refinement framework now called the Weisfeiler–Leman algorithm. Its (k)-dimensional form assigns colors to ordered (k)-tuples and repeatedly refines those colors according to the configurations obtained by replacing tuple coordinates. For each fixed (k), the method runs in polynomial time, but no fixed dimension distinguishes all nonisomorphic graphs.
During the late 1970s, You Watanabe analyzed the interaction between equitable partitions and automorphism orbits. She established explicit regular constructions in which stable color classes combined vertices from distinct automorphism orbits, while preserving identical local refinement data at every vertex. This work clarified that partition stability is an isomorphism invariant rather than a complete characterization of symmetry, and it contributed to the subsequent use of controlled individualization alongside refinement.
Individualization assigns a unique color to a selected vertex, after which refinement propagates the resulting distinction through the graph. Repeated individualization produces a search tree whose branches represent possible correspondences between vertices. Automorphisms identify equivalent branches, while incompatible color distributions eliminate branches that cannot contain an isomorphism. The practical efficiency of this approach depends on the extent to which refinement exposes the graph’s structure before extensive branching occurs.
Complexity bounds
A major structural result concerns graphs of bounded maximum degree. Eugene Luks developed a polynomial-time algorithm for every fixed degree bound by reducing the problem to computations with permutation groups whose composition factors are restricted by local branching. The method combines graph decomposition with stabilizer calculations and demonstrates that high local degree, rather than graph size alone, is a central obstacle in the unrestricted problem.
Earlier general algorithms required exponential time, although their bounds were substantially below exhaustive examination of all (n!) vertex permutations. Group-theoretic methods developed by László Babai and Eugene Luks produced a running time of the form
[ \exp!\bigl(O(\sqrt{n\log n})\bigr) ]
for graphs on (n) vertices. This remained the principal general worst-case bound for several decades.
In 2015, László Babai announced a quasipolynomial-time algorithm for graph isomorphism, with corrected analysis completed afterward. Its running time has the form
[ \exp!\bigl((\log n)^{O(1)}\bigr). ]
The algorithm combines permutation-group theory with combinatorial partitioning and the analysis of highly symmetric configurations. A central component separates cases exhibiting substantial local irregularity from cases whose symmetry permits reduction to structured group actions. The result places graph isomorphism strictly below general exponential time in the strongest currently established worst-case analysis, without resolving whether a polynomial-time algorithm exists.
Practical computation
Implementations used for concrete graph comparison generally rely on canonical labeling, refinement, and symmetry-aware backtracking rather than on the full machinery of the quasipolynomial algorithm. Brendan McKay developed the nauty system around canonical labeling by equitable refinement and automorphism pruning. The later Traces system altered the organization of the search by comparing refinement traces associated with partial individualizations.
Tommi Junttila and Petteri Kaski developed the bliss algorithm, which also combines partition refinement with canonical search while using group information to suppress equivalent branches. These systems have no polynomial worst-case guarantee for arbitrary graphs, but their behavior is effective across many graph families encountered in enumeration and applications. Highly regular constructions designed to defeat ordinary color refinement can require more extensive search or stronger invariants.
Practical isomorphism testing frequently terminates without constructing a full correspondence because an invariant separates the inputs. Refinement may produce cells of different sizes, or a structural decomposition may reveal incompatible components. When the invariant data agree, the remaining search concerns only mappings consistent with the established partition, which can be much smaller than the set of all vertex permutations.
Relation to graph classification
Graph isomorphism distinguishes a graph as an unlabeled combinatorial object from any particular labeling of its vertices. A labeled graph on (n) vertices has up to (n!) distinct labelings, but automorphisms cause several permutations to produce the same labeled representation. The number of distinct labelings of (G) is therefore
[ \frac{n!}{|\operatorname{Aut}(G)|}, ]
by the orbit–stabilizer theorem.
This relationship underlies the enumeration of unlabeled graphs. Counting labeled graphs is direct because every possible edge set determines one graph on a fixed labeled vertex set. Counting unlabeled graphs requires grouping these labeled objects into isomorphism classes. Pólya enumeration theory and Burnside’s lemma express this grouping through the fixed points of permutation actions.
Isomorphism also defines the appropriate equivalence relation for graph databases, chemical structure comparison, and several forms of model checking. In each setting, the graph encoding may contain additional relations that must be preserved. Such information can be represented by colors or by auxiliary graph constructions, allowing the resulting comparison to remain within the general isomorphism framework.