Understanding Graph Isomorphism Algorithm: Theory and Implementation

Introduction and Core Concepts

Graph isomorphism is one of the most fascinating and enduring problems in theoretical computer science. At its core, the graph isomorphism algorithm seeks to answer a deceptively simple question: are two graphs structurally identical, even if their vertices are labeled differently? Formally, two graphs G1 = (V1, E1) and G2 = (V2, E2) are said to be isomorphic if there exists a bijection f: V1 → V2 such that any two vertices u and v in V1 are adjacent in G1 if and only if f(u) and f(v) are adjacent in G2. This bijection, called an isomorphism, is essentially a relabeling of vertices that preserves adjacency.

Understanding this concept requires distinguishing isomorphism from related notions. Equality of graphs means they have the same vertex set and edge set exactly, while isomorphism allows for permutation of vertex labels. For example, a triangle graph with vertices {1,2,3} and edges {(1,2),(2,3),(3,1)} is isomorphic to a triangle with vertices {A,B,C} and edges {(A,B),(B,C),(C,A)}, even though the labels differ. The structure — three vertices each connected to the other two — is invariant. This structural equivalence is what the graph isomorphism algorithm attempts to detect efficiently.

The importance of the graph isomorphism algorithm extends far beyond a theoretical curiosity. It lies in a unique complexity class: it is not known to be solvable in polynomial time, nor is it known to be NP-complete. This status made it a famous candidate for an NP-intermediate problem until László Babai's breakthrough in 2015, which showed it can be solved in quasi-polynomial time. For practitioners, the problem underpins critical tasks in pattern recognition, cheminformatics, network analysis, and database indexing. If you can determine whether two graphs are isomorphic, you can determine whether two chemical compounds are the same, whether two circuits have identical topology, or whether a pattern exists within a larger network.

Why Graph Isomorphism Matters

The practical significance stems from the ubiquity of graph models. Almost any relational system — social networks, protein interaction maps, transportation grids, or dependency graphs in software — can be represented as a graph. When we need to compare such systems for equivalence, deduplication, or classification, we need isomorphism testing. Without an efficient algorithm, we would be forced to compare every possible permutation of vertices, an approach that becomes infeasible for graphs with more than a dozen vertices.

Furthermore, the graph isomorphism problem is deeply connected to other hard problems. The subgraph isomorphism problem, which asks whether one graph contains a subgraph isomorphic to another, is NP-complete and generalizes isomorphism. The graph automorphism problem, which counts the symmetries of a single graph, is polynomial-time equivalent to graph isomorphism. Studying isomorphism therefore provides insight into a whole family of structural comparison problems and informs the design of canonical labeling, hashing, and fingerprinting techniques used throughout computer science.

How It Works

At a high level, every graph isomorphism algorithm attempts to avoid the naive brute-force strategy of checking all n! possible bijections between two n-vertex graphs. Instead, they use invariants and pruning to dramatically reduce the search space. A graph invariant is a property that is preserved under isomorphism — if two graphs have different invariants, they cannot be isomorphic. Common invariants include the number of vertices, number of edges, degree sequence, eigenvalue spectrum, and distribution of cycles. Algorithms first compute these cheap invariants; a mismatch allows immediate rejection without further work.

The most powerful classical approach is individualization-refinement, which underlies state-of-the-art solvers like nauty, Traces, and bliss. The idea is to iteratively refine a partition of vertices into color classes based on structural information. Initially, all vertices may have the same color. The Weisfeiler-Lehman (WL) refinement then recolors each vertex based on the multiset of colors of its neighbors. This process repeats until the coloring stabilizes. If the stable colorings of two graphs differ (e.g., different counts of each color), the graphs are non-isomorphic. If they match, the algorithm may need to individualize — pick a vertex, assign it a unique color, and refine again — branching into a search tree.

Another major family is backtracking search, exemplified by the VF2 and Ullmann algorithms. These algorithms incrementally build a partial mapping between vertices of G1 and G2, extending the mapping one vertex at a time and backtracking when the partial mapping violates adjacency constraints. Crucially, they employ feasibility rules to prune branches early. For example, VF2 checks not only that mapped vertices preserve adjacency (syntactic feasibility) but also that the numbers of neighbors in mapped vs. unmapped regions are consistent (semantic feasibility). This look-ahead prevents exploring vast subtrees that cannot possibly lead to a full isomorphism.

The Role of Canonical Forms

Many modern systems reduce isomorphism testing to canonical labeling. A canonical form C(G) is a unique string or graph representation such that C(G1) = C(G2) if and only if G1 and G2 are isomorphic. Once a canonical form is computed, isomorphism testing becomes a simple equality check. This is invaluable for databases that need to index millions of graphs, such as chemical databases. Instead of pairwise isomorphism tests, each graph is stored by its canonical label, and lookup is O(1). Computing the canonical form is at least as hard as isomorphism itself, but highly optimized tools can handle graphs with thousands of vertices in practice for most real-world cases.

Babai's quasi-polynomial algorithm introduced group-theoretic techniques that provide theoretical guarantees. It leverages the structure of the automorphism group of the graph, using the classification of finite simple groups and combinatorial partitioning to split the problem into smaller subproblems. While not yet practical for implementation due to large constants, it proved that graph isomorphism is not exponentially hard in the worst case, settling a decades-old open question and suggesting that the problem is closer to P than to NP-complete.

Implementation

Implementing a graph isomorphism algorithm in Python requires careful attention to representation and pruning. Graphs are typically represented as adjacency matrices or adjacency lists. For dense graphs, an adjacency matrix allows O(1) edge existence checks, while adjacency lists are more memory-efficient for sparse graphs. The following examples illustrate progressively more sophisticated approaches, from brute force to pruned backtracking and color refinement.

The simplest implementation enumerates all permutations of vertices in the second graph and checks whether any permutation makes its adjacency matrix identical to the first. While correct, this approach is only feasible for n < 10 due to its factorial complexity. It serves as a baseline and a correctness oracle for testing more advanced methods.

import itertools

def is_isomorphic_bruteforce(adj1, adj2):
    """
    Brute-force isomorphism check via permutation enumeration.
    adj1, adj2: n x n adjacency matrices (list of lists)
    Returns True if graphs are isomorphic, else False.
    """
    n = len(adj1)
    if n != len(adj2):
        return False
    # Quick invariant: degree sequences must match
    deg1 = sorted(sum(row) for row in adj1)
    deg2 = sorted(sum(row) for row in adj2)
    if deg1 != deg2:
        return False

    # Try every permutation of vertices in G2
    for perm in itertools.permutations(range(n)):
        is_match = True
        for i in range(n):
            for j in range(n):
                # Check if adjacency is preserved under permutation
                if adj1[i][j] != adj2[perm[i]][perm[j]]:
                    is_match = False
                    break
            if not is_match:
                break
        if is_match:
            return True
    return False

# Example: Two isomorphic triangles
triangle1 = [[0,1,1],[1,0,1],[1,1,0]]
triangle2 = [[0,1,1],[1,0,1],[1,1,0]]
print(is_isomorphic_bruteforce(triangle1, triangle2))  # True

A practical backtracking implementation improves dramatically by pruning with degree and neighborhood checks. The VF2-style algorithm below maintains a partial mapping and only extends it with candidates that preserve adjacency and degree. It also uses forward checking to ensure that the number of unmapped neighbors remains consistent, which eliminates many dead ends early.

def is_isomorphic_vf2(adj1, adj2):
    """
    VF2-inspired backtracking with degree and adjacency pruning.
    Handles undirected graphs without self-loops.
    """
    n = len(adj1)
    if n != len(adj2):
        return False

    # Precompute degrees for ordering and pruning
    deg1 = [sum(row) for row in adj1]
    deg2 = [sum(row) for row in adj2]
    if sorted(deg1) != sorted(deg2):
        return False

    # Order vertices of G1 by descending degree for better pruning
    order = sorted(range(n), key=lambda x: deg1[x], reverse=True)
    mapping = [-1] * n  # mapping[i] = vertex in G2 mapped to order[i]
    used = [False] * n

    def is_feasible(depth, candidate):
        """Check if mapping order[depth] -> candidate is feasible."""
        v1 = order[depth]
        # Degree must match
        if deg1[v1] != deg2[candidate]:
            return False
        # Adjacency consistency with already mapped vertices
        for k in range(depth):
            u1 = order[k]
            u2 = mapping[k]
            if adj1[v1][u1] != adj2[candidate][u2]:
                return False
        # Look-ahead: neighbor counts in mapped vs unmapped sets
        # Count neighbors of v1 that are already mapped
        mapped_neighbors_v1 = sum(1 for k in range(depth) if adj1[v1][order[k]] == 1)
        mapped_neighbors_cand = sum(1 for k in range(depth) if adj2[candidate][mapping[k]] == 1)
        if mapped_neighbors_v1 != mapped_neighbors_cand:
            return False
        return True

    def backtrack(depth):
        if depth == n:
            return True
        v1 = order[depth]
        for cand in range(n):
            if not used[cand] and is_feasible(depth, cand):
                mapping[depth] = cand
                used[cand] = True
                if backtrack(depth + 1):
                    return True
                used[cand] = False
                mapping[depth] = -1
        return False

    return backtrack(0)

Color refinement via the 1-dimensional Weisfeiler-Lehman test provides a fast, non-backtracking filter. It can distinguish many non-isomorphic pairs in near-linear time and is often used as a preprocessing step before more expensive search. If WL reports graphs as non-isomorphic, they are guaranteed to be non-isomorphic; if it reports possibly isomorphic, a complete algorithm is still needed.

from collections import Counter, defaultdict

def weisfeiler_lehman_filter(adj1, adj2, iterations=3):
    """
    1-WL color refinement filter.
    Returns False if graphs are definitely NOT isomorphic,
    True if they might be isomorphic (inconclusive).
    """
    def wl_colors(adj):
        n = len(adj)
        # Initial coloring by degree
        colors = [sum(row) for row in adj]
        for _ in range(iterations):
            new_colors = []
            color_map = {}
            next_id = 0
            for v in range(n):
                # Multiset of neighbor colors
                neigh_colors = tuple(sorted(colors[u] for u in range(n) if adj[v][u] == 1))
                signature = (colors[v], neigh_colors)
                if signature not in color_map:
                    color_map[signature] = next_id
                    next_id += 1
                new_colors.append(color_map[signature])
            colors = new_colors
            # Early compression: if all colors distinct, stop
            if len(set(colors)) == n:
                break
        return Counter(colors)

    if len(adj1) != len(adj2):
        return False
    c1 = wl_colors(adj1)
    c2 = wl_colors(adj2)
    # If color histograms differ, not isomorphic
    return c1 == c2

# Example: 6-cycle vs two triangles (same degree sequence, WL distinguishes)
cycle6 = [[0,1,0,0,0,1],[1,0,1,0,0,0],[0,1,0,1,0,0],[0,0,1,0,1,0],[0,0,0,1,0,1],[1,0,0,0,1,0]]
two_triangles = [[0,1,1,0,0,0],[1,0,1,0,0,0],[1,1,0,0,0,0],[0,0,0,0,1,1],[0,0,0,1,0,1],[0,0,0,1,1,0]]
print(weisfeiler_lehman_filter(cycle6, two_triangles))  # False -> definitely not isomorphic

For production use, canonical labeling can be implemented by searching for the lexicographically smallest adjacency matrix among all permutations, with pruning. The following sketch shows how to generate a canonical string representation, which is useful for hashing graphs in databases or caching.

import itertools

def canonical_form(adj):
    """
    Compute canonical form by finding lexicographically smallest
    string among all permutations (feasible only for small n).
    For large graphs, use nauty/bliss via networkx or sage.
    """
    n = len(adj)
    best = None
    # For n > 8, this should be replaced with individualization-refinement
    for perm in itertools.permutations(range(n)):
        # Build permuted adjacency as string
        permuted = []
        for i in range(n):
            for j in range(n):
                permuted.append(str(adj[perm[i]][perm[j]]))
        s = "".join(permuted)
        if best is None or s < best:
            best = s
    return best

def are_isomorphic_canonical(adj1, adj2):
    """Isomorphism via canonical forms."""
    if len(adj1) != len(adj2):
        return False
    return canonical_form(adj1) == canonical_form(adj2)

# Production alternative using networkx (if available):
# import networkx as nx
# def nx_isomorphic(edges1, edges2):
#     G1 = nx.Graph(edges1)
#     G2 = nx.Graph(edges2)
#     return nx.is_isomorphic(G1, G2)  # Uses VF2 under the hood

Step-by-Step Example

To make the abstract algorithm concrete, let us walk through a complete example with two small graphs that are isomorphic but not obviously so due to different labelings. Consider Graph G1 with vertices {0,1,2,3} and edges {(0,1), (1,2), (2,3), (3,0)} — a 4-cycle or square. Graph G2 has vertices {A,B,C,D} and edges {(A,C), (C,B), (B,D), (D,A)}. Visually, G2 looks different if drawn with A at the top, but structurally it is also a 4-cycle. Our goal is to find the bijection f that proves isomorphism.

Step 1: Check invariants. Both graphs have 4 vertices and 4 edges. The degree sequence for both is [2,2,2,2] since every vertex in a cycle has degree 2. The number of connected components is 1 for both. No invariant rules them out, so we proceed to search.

Step 2: Apply Weisfeiler-Lehman refinement. Initially, all vertices have color 2 (degree). Each vertex has two neighbors, both colored 2, so the signature for every vertex is (2, (2,2)). After one iteration, all vertices still share the same new color, say 0. The histogram is {0:4} for both graphs. WL is inconclusive — it cannot distinguish regular graphs like cycles — so we need backtracking.

Step 3: Begin backtracking search. Order vertices of G1 by degree (all equal, so order is [0,1,2,3]). Map 0 → A as first guess. Check feasibility: degrees match (2=2) and no previously mapped neighbors to check. The mapping is feasible, so we recurse. Next, try to map 1. Candidates are B,C,D. Try 1 → B: check adjacency with mapped vertex 0. In G1, 0-1 is an edge (1), but in G2, A-B is not an edge (0) — adjacency mismatch, so prune. Try 1 → C: G1 edge 0-1 (1) vs G2 edge A-C (1) matches, so feasible. Recurse with mapping {0→A, 1→C}.

Step 4: Continue extending. Map vertex 2. Remaining candidates are B,D. Try 2 → B: check edges to mapped vertices: G1 edges 2-0 (0) vs G2 B-A (0) matches, and 2-1 (1) vs B-C (1) matches — feasible. Recurse with {0→A, 1→C, 2→B}. Finally, map 3 → D (only remaining). Check: 3-0 (1) vs D-A (1) matches, 3-1 (0) vs D-C (0) matches, 3-2 (1) vs D-B (1) matches. All checks pass, depth equals n, so we have found a full isomorphism: 0→A, 1→C, 2→B, 3→D. The algorithm returns True. If we had chosen a different initial branch, backtracking would have explored and pruned alternatives automatically.

What If Graphs Were Not Isomorphic?

Suppose G2 were instead a star graph with center A connected to B,C,D. Its degree sequence would be [3,1,1,1], immediately failing the degree invariant check. The algorithm would return False without any search. For a more subtle non-isomorphic pair, consider G1 as a 4-cycle and G2 as a path of length 3 (edges A-B, B-C, C-D). Both have 4 vertices and 3 edges, but degree sequences are [2,2,2,2] vs [1,2,2,1]. The invariant check fails again. The hardest cases are strongly regular graphs where all invariants coincide and extensive search is required — these are the benchmarks used to evaluate solver performance.

Complexity Analysis

The complexity of graph isomorphism is nuanced because it depends heavily on the algorithm and the graph class. The naive brute-force approach that checks all n! permutations has factorial time complexity, which is worse than exponential. For each permutation, it performs O(n^2) work to compare adjacency matrices, yielding O(n! * n^2) time and O(n) auxiliary space for the permutation array. This is only usable for n < 11.

More sophisticated backtracking algorithms like VF2 have exponential worst-case time O(n! * n) in theory, but with powerful pruning they achieve polynomial or near-polynomial performance on most practical graphs, especially sparse or labeled graphs. Their space complexity is O(n^2) for adjacency matrices plus O(n) for recursion stack and mapping arrays. The average case for random graphs is remarkably fast — often O(n^2) — because random graphs have trivial automorphism groups and invariants quickly distinguish vertices.

The Weisfeiler-Lehman filter runs in O(n + m) per iteration, where m is the number of edges, and typically converges in O(n) iterations, giving O(n * (n + m)) worst-case but O(n + m) in practice for sparse graphs. It uses O(n + m) space. Babai's quasi-polynomial algorithm runs in exp((log n)^O(1)) time, which is asymptotically faster than exponential but slower than polynomial; it is a theoretical breakthrough rather than a practical tool, with large hidden constants and complex group-theoretic operations.

It is critical to understand that worst-case exponential behavior is rarely observed except on specially constructed hard graphs, such as certain strongly regular graphs, Cai-Fürer-Immerman graphs, or Miyazaki graphs designed to defeat refinement. For bounded-degree graphs, isomorphism can be tested in polynomial time (Luks's algorithm), and for trees, planar graphs, and interval graphs, linear or O(n log n) algorithms exist. Therefore, the choice of algorithm should be guided by the expected graph family.

Variations and Optimizations

Beyond the basic unlabelled, undirected graph isomorphism, several variations address more general problems. Subgraph isomorphism asks whether G1 is isomorphic to a subgraph of G2; this is NP-complete and requires different pruning strategies. Induced subgraph isomorphism adds the constraint that non-edges must also be preserved. Graph homomorphism relaxes the bijection requirement to a structure-preserving map that need not be injective. Each variant modifies the feasibility checks in the backtracking framework.

For labeled graphs, where vertices and edges carry attributes (e.g., atom types in molecules, or roles in social networks), the algorithm can be substantially faster. Labels provide an initial coloring that dramatically reduces symmetries. The feasibility check simply adds a condition that labels must match: label1[v1] == label2[candidate]. This often makes even large graphs trivial to compare. Most real-world applications involve labeled graphs, which is why practical solvers excel despite theoretical hardness.

Key optimizations that make modern solvers fast include: degree and invariant pre-filtering, ordering vertices by degree or centrality to fail fast, using adjacency bitsets for O(1) neighbor set operations, employing automorphism pruning to avoid exploring symmetric branches, and using memoization of failed partial mappings. Parallelization is also effective — the search tree can be distributed across cores.

Advanced Techniques

Individualization-refinement solvers use sophisticated data structures like equitable partitions and union-find for color classes. They also implement target cell selection heuristics to choose which color class to individualize next, minimizing branching factor. Another optimization is to use incremental hashing: compute a hash of the graph that is invariant under isomorphism (e.g., based on WL colors) and use it as a fast fingerprint before full search.

For very large graphs (millions of vertices), approximate or heuristic methods are used. These include spectral methods that compare eigenvalues, graph kernels that embed graphs into vector spaces, and neural approaches like Graph Neural Networks that learn isomorphism-invariant embeddings. While not exact, they can quickly identify candidate pairs for exact verification.

Real-World Applications

Graph isomorphism algorithms are workhorses in numerous domains, often hidden behind higher-level abstractions. In cheminformatics and drug discovery, molecules are modeled as labeled graphs where vertices are atoms and edges are bonds. Determining whether two molecular graphs are isomorphic is equivalent to checking whether they represent the same compound, which is essential for database deduplication, patent searching, and virtual screening. Tools like RDKit and Open Babel rely on canonical SMILES strings, which are canonical forms of molecular graphs.

In computer vision and pattern recognition, images can be segmented into region adjacency graphs, and isomorphism is used for object recognition invariant to rotation and scaling. Similarly, in social network analysis, detecting identical community structures or matching anonymized networks requires isomorphism testing. Cybersecurity applications include malware detection via control-flow graph comparison and fingerprinting network topologies to detect clones or Sybil attacks.

Electronic design automation (EDA) uses isomorphism to verify circuit equivalence. Two netlists that differ only in component naming should be recognized as identical for layout vs. schematic checks. In databases, graph isomorphism underpins query optimization for graph databases like Neo4j and indexing of RDF data. Web servers and compilers use it to detect isomorphic subexpressions for common subexpression elimination and to deduplicate dependency graphs.

The choice of algorithm varies by domain. Chemical graphs are small, labeled, and sparse, making VF2 and WL extremely effective. Social networks are large and often require heuristic or parallel methods. For web-scale graphs, approximate techniques combined with exact verification on candidate pairs provide the best trade-off between accuracy and performance.

Comparison with Alternatives

Graph isomorphism is often confused with related problems that have different complexity and use cases. Understanding these distinctions is crucial for selecting the correct algorithm. Subgraph isomorphism is strictly harder (NP-complete) and asks whether a pattern graph appears inside a larger target graph, which is the basis for subgraph search in databases. Graph homomorphism is even more general and allows many-to-one mappings, used in constraint satisfaction.

Alternatives to exact isomorphism testing include approximate methods. Graph edit distance measures the minimum number of edits to transform one graph into another, providing a similarity score rather than a binary answer. Graph kernels and embeddings map graphs to vectors where Euclidean distance approximates structural similarity, enabling machine learning. These are faster but may produce false positives or negatives.

For exact testing, the main algorithmic alternatives are VF2, Ullmann, nauty/Traces/bliss, and Weisfeiler-Lehman. VF2 is simple, memory-efficient, and excellent for labeled graphs and subgraph isomorphism. Ullmann is older and uses matrix refinement. nauty and its successors are the gold standard for canonical labeling and automorphism group computation, dominating for unlabeled, highly symmetric graphs. WL is not a complete isomorphism test (it fails on certain regular graphs) but is an unbeatable filter.

In practice, a hybrid pipeline is common: use WL or hashing to filter candidates, then apply VF2 or nauty for exact verification, and fall back to edit distance or kernels when exact matching is too strict. For interview and system design contexts, be prepared to justify why isomorphism is chosen over these alternatives based on requirements for exactness, performance, and graph size.

Common Mistakes and Best Practices

One of the most frequent mistakes is assuming that equal invariants imply isomorphism. Many beginners check that two graphs have the same number of vertices, edges, and degree sequence, and then conclude they are isomorphic. This is false: the earlier example of a 6-cycle versus two disjoint triangles shows graphs with identical degree sequences [2,2,2,2,2,2] that are not isomorphic. Invariants are necessary but not sufficient; they can only prove non-isomorphism, never isomorphism (except for complete invariants like canonical forms).

Another pitfall is implementing brute-force permutation checks without pruning and then claiming the solution scales. Such code will time out on graphs with n > 12 and will fail hidden test cases designed with hard regular graphs. Always implement at least degree filtering and vertex ordering, and consider using iterative deepening or recursion limits to avoid stack overflow on deep search trees. Forgetting to handle disconnected graphs is also common; the algorithm must work component-wise or ensure the mapping respects component structure.

A subtle bug is mishandling directed vs. undirected graphs and self-loops. The adjacency check must be consistent: for directed graphs, both directions must be checked separately, and for graphs with self-loops, the diagonal of the adjacency matrix matters. Using adjacency lists without accounting for edge direction leads to false positives. Additionally, when graphs are labeled, labels must be compared with equality, not just structure, and label mismatches should be checked before expensive structural search.

Best Practices

• Filter first, search second: Always run O(n log n) invariant checks (vertex count, edge count, degree histogram, connected components) and a WL refinement pass before backtracking. This eliminates 99% of non-isomorphic pairs instantly.
• Order vertices wisely: Sort vertices by descending degree, centrality, or WL color rarity. Mapping high-constraint vertices first prunes the search tree earliest. Some implementations dynamically reorder remaining candidates based on current partial mapping.
• Use established libraries for production: Do not roll your own nauty for large graphs. Use networkx.algorithms.isomorphism, bliss, or pynauty, which are extensively tested and implement automorphism pruning. Custom code is fine for learning and interviews but not for production.
• Represent graphs efficiently: For n < 2000, use adjacency matrices with Python lists or numpy arrays for O(1) lookups. For larger sparse graphs, use adjacency sets or bitsets (Python's int as bitmask or python's builtin set) to iterate neighbors quickly. Cache degree sequences and neighbor sets.
• Test on hard cases: Validate against known difficult pairs: strongly regular graphs (e.g., Petersen graph vs. others), isospectral graphs, and Miyazaki graphs. Also test on isomorphic pairs with random permutations to ensure mapping is found, not just boolean result.
• Handle recursion depth: Python's recursion limit is ~1000. For graphs larger than that, implement backtracking iteratively with an explicit stack to avoid RecursionError.

Finally, document whether your function checks for isomorphism or automorphism, and whether it returns just a boolean or also the mapping. In many applications, the mapping itself is needed (e.g., to align molecules), so returning the permutation is more useful than a simple True/False.

Interview Questions

Graph isomorphism is a favorite topic for advanced algorithm interviews because it tests understanding of combinatorics, complexity theory, and practical pruning. Below are common questions and how to approach them.

Q1: How would you determine if two graphs are isomorphic? What is the brute-force complexity?

Answer: Explain the definition of isomorphism as a bijection preserving adjacency. Describe the brute-force method of checking all n! permutations, each requiring O(n^2) adjacency comparisons, for total O(n! * n^2) time. Then discuss optimizations: first check invariants (vertex count, edge count, degree sequence) in O(n log n), then use backtracking with pruning (VF2) or color refinement (Weisfeiler-Lehman). Mention that for random graphs this is fast in practice, but worst-case remains exponential, and Babai's result shows quasi-polynomial theoretical bound. Provide the Python brute-force code as illustration and note that you would never use it for n > 10 in production.

Q2: Why does the degree sequence check not guarantee isomorphism? Give a counterexample.

Answer: State that degree sequence is an invariant — isomorphic graphs must have the same degree sequence, but the converse is false. Provide the classic counterexample: G1 is a 6-cycle (C6) and G2 is two disjoint triangles (2 * C3). Both have degree sequence [2,2,2,2,2,2], same number of vertices and edges, but G1 is connected while G2 has two components, so they cannot be isomorphic. Another example is the pair of non-isomorphic strongly regular graphs with parameters (16,6,2,2) — the Shrikhande graph and the 4x4 rook's graph — which share the same degree sequence and even the same spectrum but are not isomorphic. Emphasize that invariants can only disprove isomorphism.

Q3: Explain the Weisfeiler-Lehman test and its limitations.

Answer: Describe 1-WL as iterative color refinement: start with colors based on degree, then repeatedly recolor each vertex based on the multiset of its neighbors' colors until stable. If the color histograms differ, graphs are definitely non-isomorphic; if they match, the test is inconclusive. Explain that 1-WL runs in O(n + m) per iteration and distinguishes almost all random graphs, but fails on regular graphs where all vertices have identical neighborhoods, such as the 6-cycle vs. two triangles case where it actually succeeds, but more subtle failures include the Cai-Fürer-Immerman graphs and certain strongly regular graphs. Mention that k-dimensional WL (k-WL) is more powerful but exponentially more expensive, and that WL is used as a fast filter before exact search.

Q4: How would you adapt an isomorphism algorithm for labeled graphs or for subgraph isomorphism?

Answer: For labeled graphs, add a label equality check to the feasibility function: two vertices can only be mapped if their labels match, and edge labels must also match. This initial coloring by label makes the problem much easier. For subgraph isomorphism (NP-complete), change the problem to finding an injective mapping from the smaller pattern graph into the larger target such that adjacency in the pattern implies adjacency in the target, but not vice versa. The backtracking must allow the target to have extra edges among mapped vertices that the pattern does not have, and the search must consider choosing which subset of target vertices to map to. Mention Ullmann and VF2 handle both, and that pruning becomes even more critical.

Q5: What is the complexity class of graph isomorphism? Is it in P or NP-complete?

Answer: Explain that graph isomorphism is in NP (a permutation can be verified in polynomial time) and also in co-AM, but is not known to be in P nor known to be NP-complete. It is a candidate for NP-intermediate per Ladner's theorem (if P != NP). Mention Babai's 2015 breakthrough showing it is in quasi-polynomial time exp((log n)^O(1)), which strongly suggests it is not NP-complete, as NP-complete problems are not believed to have quasi-polynomial algorithms. Also note that related problems like subgraph isomorphism are NP-complete, while bounded-degree graph isomorphism is in P. This question tests awareness of theoretical computer science beyond just coding.