Wait, What?
Two graphs can look completely different on the page and still be exactly the same graph.
Vertex names, drawing positions and edge order are presentation details. Graph isomorphism asks whether one graph can be relabelled so that adjacency is preserved exactly. The problem is simple to state, surprisingly deep in theory, and a beautiful place to learn how invariants, pruning, refinement and search work together.
This article owns the graph-isomorphism learning job. The existing Graph Algorithms article owns general graph representation and traversal. The General-Graph Matching article owns matching. Isomorphism is different: it asks whether the entire relational structure is preserved under a bijection of vertices.
Quick Answer
Learn graph isomorphism through the route relabeling → bijection → adjacency preservation → cheap invariants → degree partitions → color refinement → failure cases → backtracking search → feasibility pruning → VF2/VF2++ → individualization–refinement → automorphisms → canonical labeling → Weisfeiler–Leman hierarchy → complexity theory → production validation. A beginner should be able to prove two small graphs are isomorphic by giving a vertex map. A professional should be able to choose invariants and pruning rules, distinguish heuristic refinement from proof, understand canonical forms and benchmark practical solvers on difficult symmetry classes.
1. Strip Away the Drawing
A graph is not the picture used to draw it. Move the vertices, rename them and reorder the edge list: the graph’s abstract adjacency relationships remain unchanged.
Begin with the same cycle drawn as a square, a diamond and a tangled loop. Ask learners what stayed invariant. This prepares them to distinguish representation from structure.
2. Isomorphism Means an Adjacency-Preserving Bijection
Graphs G and H are isomorphic if there is a one-to-one correspondence between their vertices such that an edge exists between two vertices in G exactly when an edge exists between their mapped vertices in H.
For labelled graphs, directed graphs or attributed graphs, the mapping may also need to preserve labels, direction or other semantic constraints.
3. Start With Cheap Invariants That Can Prove “No” Quickly
If two graphs have different numbers of vertices or edges, they cannot be isomorphic. If their sorted degree sequences differ, they cannot be isomorphic. Connected-component sizes, triangle counts and other structural summaries can provide additional rejection tests.
The key logical rule is one-way: a mismatch in a true invariant proves non-isomorphism, but a match usually does not prove isomorphism.
4. Degree Sequence Is Useful but Weak
Many non-isomorphic graphs share the same degree sequence. This makes degree an excellent first filter but a poor final decision procedure.
Give learners two non-isomorphic graphs with the same degree sequence. That counterexample teaches why structural refinement is needed.
5. Color Refinement Turns Local Neighbourhoods Into Stronger Signatures
Start by assigning vertices colors based on an initial property such as degree. Then repeatedly update each vertex’s color from its current color together with the multiset of colors of its neighbours.
If the color-class size patterns differ between the two graphs, the graphs are not isomorphic. If refinement stabilises with matching patterns, the graphs may still be non-isomorphic; refinement is powerful but not complete.
6. Weisfeiler–Leman Generalises the Refinement Idea
The one-dimensional Weisfeiler–Leman procedure is closely related to color refinement. Higher-dimensional versions refine colors on tuples of vertices and distinguish broader classes of graphs at increased computational cost.
Current NetworkX Weisfeiler–Leman hashing exposes a practical form of iterative neighbourhood aggregation. A hash match should be treated as a candidate signal, not a universal proof of isomorphism.
7. Refinement Failure Is Not Algorithm Failure
When refinement cannot separate two ambiguous vertices, the algorithm has learned something useful: those vertices currently look structurally equivalent under the available local evidence. The next step is to branch on that ambiguity rather than pretending it does not exist.
8. Backtracking Search Builds a Candidate Bijection
Choose a vertex in G, try mapping it to a compatible vertex in H, propagate the consequences, and backtrack if a contradiction appears. The naive version explores far too many permutations, so practical algorithms devote enormous effort to choosing good candidates and rejecting impossible partial mappings early.
9. Feasibility Tests Are the Difference Between Search and Blind Enumeration
A partial mapping must already preserve the edges and non-edges implied by mapped vertices. Candidate vertices can also be constrained by degree, labels, neighbourhood partitions and frontier relationships.
Every contradiction found early removes an entire subtree of permutations that never need to be explored.
10. VF2 Makes Search State Explicit
VF2 is a widely used family of graph and subgraph isomorphism algorithms. It maintains a partial mapping and frontier information, applying syntactic and optionally semantic feasibility checks before extending the mapping.
The current NetworkX VF2 documentation is a useful implementation-facing reference for graph, directed-graph and subgraph matching interfaces.
11. VF2++ Improves Ordering and Cutting Rules
VF2++ follows the same broad search logic while improving the order in which vertices are considered and adding efficient cutting rules. Current NetworkX 3.6.1 isomorphism documentation describes its implementation and notes that ordering can use both degree and label rarity to expose unpromising branches sooner.
This is a general algorithm-design lesson: the mathematical solution space can stay the same while a better branching order changes practical runtime dramatically.
12. Individualization–Refinement Turns Ambiguity Into New Information
If a color class contains several indistinguishable vertices, choose one vertex and temporarily give it a unique color—individualize it—then run refinement again. This forced distinction may propagate through the graph and split many other classes.
If ambiguity remains, branch again. Practical canonical-labeling and isomorphism solvers build search trees around this interaction between individualization and refinement.
13. Symmetry Is Why Some Instances Are Hard
A highly asymmetric graph may become uniquely colored after a few refinement rounds, making isomorphism easy. A highly symmetric graph may contain many vertices that remain structurally interchangeable, creating a large search space.
Difficulty therefore depends on graph structure, not merely the number of vertices.
14. Automorphisms Are Isomorphisms From a Graph to Itself
An automorphism is a vertex permutation that preserves the graph. The set of all automorphisms forms a group and describes the graph’s internal symmetries.
Recognising automorphisms can prevent a solver from repeatedly exploring branches that are equivalent by symmetry.
15. Canonical Labeling Solves a Stronger Representation Problem
A canonical-labeling algorithm assigns every graph in an isomorphism class the same canonical representation. If two graphs have identical canonical forms, they are isomorphic; if the canonical forms differ, they are not.
This is useful for deduplicating chemical structures, graph databases, combinatorial generation and any workflow where structurally identical graphs may arrive under different vertex names.
16. Canonical Hashing and Canonical Labeling Are Not Automatically the Same
A graph hash can be a quick fingerprint, but a hash function may collide and some refinement-based hashes do not distinguish every non-isomorphic graph. A canonical form is intended to encode the complete isomorphism class according to the canonicalization procedure.
Professionals must know whether a system uses a heuristic filter, a cryptographic digest of a canonical form, or a proof-producing isomorphism test.
17. Subgraph Isomorphism Is a Different and Typically Harder Problem
Graph isomorphism asks whether two whole graphs are structurally identical. Subgraph isomorphism asks whether one graph occurs inside another. This distinction matters in pattern matching, cheminformatics and graph querying.
Do not transfer complexity claims carelessly between the two problems.
18. Complexity Theory Gives the Problem an Unusual Status
Graph Isomorphism is known to lie in NP, but it is not known to be NP-complete, and major theoretical progress has produced quasipolynomial-time algorithms. László Babai’s Institute for Advanced Study lecture on graph isomorphism in quasipolynomial time explains the framework and the role of local certificates and symmetry.
The lesson for students is important: practical algorithms and worst-case theory are related but not identical. Software can solve many huge everyday instances rapidly even while the theoretical classification remains subtle.
19. Difficult Test Families Matter More Than Random Graphs Alone
Random graphs often have little symmetry and can be easy for refinement-based approaches. To test a solver meaningfully, include regular graphs, strongly regular graphs, highly symmetric constructions, near-isomorphic pairs and adversarial cases designed to defeat simple invariants.
20. Verification of a Claimed Mapping Is Easy
If a solver claims an isomorphism, independently verify that the mapping is a bijection and that every adjacency and required attribute is preserved. Verification is much simpler than finding the mapping.
This asymmetry is pedagogically useful: learners can test sophisticated library output with a simple checker they understand completely.
21. Common Learning Failure States
- Judging isomorphism from the visual drawing.
- Assuming matching degree sequences prove isomorphism.
- Treating Weisfeiler–Leman refinement as a complete test in all cases.
- Forgetting that labels or edge attributes may be part of the required structure.
- Enumerating all n! vertex permutations before trying invariants and pruning.
- Confusing graph isomorphism with graph matching or subgraph isomorphism.
- Calling two vertices “the same” when they are only currently indistinguishable under a refinement.
- Using a graph hash as an unconditional proof without understanding its guarantees.
- Benchmarking only random graphs.
- Reporting runtime without reporting graph family and symmetry structure.
22. A Beginner-to-Professional Learning Ladder
- Level 1: relabel a small graph while preserving edges.
- Level 2: reject non-isomorphic graphs using vertex, edge and degree invariants.
- Level 3: perform color refinement by hand.
- Level 4: construct a counterexample where degree sequence is insufficient.
- Level 5: implement a backtracking isomorphism search with feasibility checks.
- Level 6: compare naive search with VF2/VF2++ on labelled and unlabelled graphs.
- Level 7: trace individualization–refinement on a symmetric graph.
- Level 8: compute or use canonical forms to deduplicate graphs.
- Level 9: benchmark difficult graph families and explain the effect of symmetry.
- Level 10: connect practical solver behaviour with automorphism groups, WL refinement and modern complexity results.
23. Teach With “Same or Different?” Before Code
Present pairs of graph drawings and ask learners to predict whether they are isomorphic. Require a reason: an invariant that rules the pair out, or a candidate vertex map that might prove it. Then verify with code.
This prediction-first structure fits the PRIMM approach used in programming education: predict, run, investigate, modify and make. Recent work, including 2026 PRIMM research, continues to examine how structured code comprehension can support learners before independent programming.
24. Use Faded Search Trees
First provide a complete backtracking tree showing why each branch fails. In the next example remove the feasibility annotations. Then remove the candidate ordering. Finally ask the learner to design the branching rule and justify which invariant should run before search.
25. Parsons Problems Fit Refinement Pipelines
Give shuffled blocks for: compute initial colors, aggregate neighbourhood signatures, relabel color classes, test stabilization, compare partitions, choose an ambiguous class and branch. Reconstructing the pipeline can reduce blank-page syntax load while preserving the conceptual sequence.
26. Immediate, Delayed and Transfer Checks
- Immediate: give an explicit isomorphism between two four-vertex graphs.
- Concept: explain why matching degree sequences do not prove isomorphism.
- Delayed: reproduce the color-refinement cycle without notes.
- Transfer: choose between hashing, canonicalization, full isomorphism and subgraph matching for four application scenarios.
- Professional: diagnose why a solver is slow on one graph family but fast on another of the same size.
27. AI Assistance Boundary
AI can generate graph pairs, visualize candidate mappings and propose test families. The learner should still be able to verify a mapping, distinguish necessary invariants from complete tests, explain the pruning logic, recognise symmetry and independently validate the solver’s claim.
Professional Direction
Advanced study includes nauty/Traces-style canonical labeling, automorphism-group computation, partition refinement, equitable partitions, higher-dimensional Weisfeiler–Leman, CFI constructions, bounded-degree algorithms, Babai’s quasipolynomial framework, graph kernels, chemical graph canonicalization, graph database indexing and symmetry breaking in combinatorial search.
Algorithm-learning rule: never ask only whether two graphs “look the same.” Ask which properties survive relabeling, which invariant can reject the pair cheaply, where refinement leaves ambiguity, how search breaks that symmetry, and what evidence turns a candidate mapping into a proof.
eduKate Sengkang 