Graph Isomorphism

When are two drawings of a graph "the same graph"? A hexagon drawn as a regular polygon and a hexagon drawn as a tangled star look nothing alike. Yet they encode identical connection data. Graph isomorphism is the precise notion of sameness that ignores labels, positions, and drawing style. It keeps only who-is-adjacent-to-whom. This matters because in applications — molecules, circuits, social networks, databases — the labels attached to vertices are often arbitrary. The real question is always structural: does this chemical skeleton match that one? Does this network contain that motif? Are these two encodings of a puzzle really the same puzzle? The subject sits at a curious crossroads. Deciding whether two graphs are isomorphic is easy to state. It is computationally mysterious in general — one of the few natural problems not known to be in P nor proven NP-complete. Yet it is routinely easy in practice using invariants — quantities that isomorphic graphs must share. This article builds the formal definition. It proves the basic structural theorem that isomorphism is an equivalence relation compatible with the invariants. It works through two genuinely different, non-symmetric example pairs. It shows exactly where naive invariant-checking can be fooled. The bigger picture: isomorphism is the graph-theoretic instance of a much broader idea. That idea is recognizing when two mathematical objects, though built from different raw materials, have identical relational structure. The same instinct produces isomorphism of groups, of vector spaces, of posets. Graphs are an unusually visual and combinatorially rich setting to master this idea. This is because invariants (degree sequences, cycle structure, spectra) are concrete and computable. It is also because the automorphism group of a graph — its self-isomorphisms — measures internal symmetry directly. By the end you will have a rigorous definition of graph isomorphism. You will have a proven theorem describing its basic algebraic behavior and its interaction with invariants. You will see worked examples showing both a successful isomorphism construction and a failed one exposed by an invariant. You will gain a clear sense of why this deceptively simple-looking equivalence relation still resists a complete computational understanding. This sets up the spectral viewpoint developed in Introduction to Spectral Graph Theory.

Key takeaways
  • Two graphs are isomorphic if there is a bijection between their vertex sets that preserves adjacency exactly.
  • Isomorphism is an equivalence relation on graphs, so "isomorphism classes" partition all graphs into structural types.
  • Any quantity preserved by every isomorphism (degree sequence, number of edges, number of triangles, connectivity, spectrum) is an invariant; mismatched invariants prove non-isomorphism instantly.
  • Invariants alone can never prove isomorphism — matching invariants are necessary but not sufficient, as the counterexample below shows.
  • The self-isomorphisms of a single graph form its automorphism group, a subgroup of the symmetric group on its vertices, measuring internal symmetry.
  • No polynomial-time algorithm for general graph isomorphism is known, and none is known to be impossible; it is a rare "in-between" problem.
  • Key idea: isomorphism forgets labels and keeps only the adjacency relation, so two graphs are the same exactly when some relabeling makes their edge sets literally equal.

Where this lives today

Chemistry and cheminformatics. Molecules are modeled as graphs (atoms as vertices, bonds as edges); checking whether two molecular graphs are isomorphic decides whether two different-looking structural diagrams represent the same compound, and isomorphism-based subgraph matching underlies database searches for substructures (e.g., "does this molecule contain a benzene ring").

Circuit design and VLSI verification. Two logic circuit netlists that are isomorphic as graphs implement equivalent wiring regardless of physical layout; automated equivalence checking tools rely on fast graph isomorphism (and subgraph isomorphism) heuristics to verify that a redesigned chip layout matches its specification.

Cryptography. Some proposed public-key and zero-knowledge protocols use the presumed computational difficulty of graph isomorphism (or related problems) as a hardness assumption, since no efficient general algorithm is known despite decades of effort, distinguishing it from problems already known to be easy or from NP-complete problems believed intractable.

Chemistry-adjacent and network science. Automorphism groups measure symmetry in molecular graphs (predicting spectroscopic degeneracies) and in complex networks (identifying structurally equivalent nodes, useful for role discovery in social or biological networks).

Computer vision and pattern matching. Scene graphs or shape skeletons are compared via (sub)graph isomorphism to recognize objects regardless of position or orientation, echoing the "same shape, different labels" intuition at the heart of the definition.

Theoretical computer science. Graph Isomorphism is a centerpiece example in complexity theory of a natural problem whose exact classification (P, NP-complete, or strictly in between) remains unresolved, motivating deep structural and algorithmic techniques, and connecting directly to the eigenvalue-based invariants developed in Introduction to Spectral Graph Theory.

Ask the tutor: Can you show me why checking the eigenvalues of the adjacency matrix is a stronger invariant than the degree sequence, but still not a perfect test for isomorphism?

DefinitionGraph Isomorphism

Let G=(VG,EG)G = (V_G, E_G) and H=(VH,EH)H = (V_H, E_H) be simple graphs (no loops, no multiple edges, no orientation). A function

φ:VG→VH\varphi : V_G \to V_H

is a graph isomorphism from GG to HH if: 1. φ\varphi is a bijection (injective and surjective) from VGV_G to VHV_H; and 2. φ\varphi preserves adjacency in both directions: for all u,v∈VGu, v \in V_G,

{u,v}∈EG⟺{φ(u),φ(v)}∈EH.\{u,v\} \in E_G \quad \Longleftrightarrow \quad \{\varphi(u), \varphi(v)\} \in E_H.

Graphs GG and HH are isomorphic, written G≅HG \cong H, if an isomorphism between them exists. If G=HG = H as abstract graphs (so φ:VG→VG\varphi: V_G \to V_G), φ\varphi is called an automorphism of GG; the set of all automorphisms of GG, under function composition, is the automorphism group Aut(G)\mathrm{Aut}(G). A graph invariant is a function ff on graphs such that G≅HG \cong H implies f(G)=f(H)f(G) = f(H).

Intuition

Think of a graph as a physical structure: vertices are joints, edges are rigid rods connecting them. Isomorphism asks whether two such structures, perhaps built from rods of different colors and joints with different names, could be assembled into the exact same shape if you were allowed to relabel the joints however you like — but not allowed to add, remove, or reroute a single rod. The relabeling is the bijection φ\varphi; the "same shape" condition is exactly that adjacency is preserved both ways. The two-directional condition in the definition is doing real work. It is not enough for φ\varphi to send edges to edges; it must also send non-edges to non-edges. A map that collapses a sparse graph's non-adjacencies into a denser graph's adjacencies would satisfy only "half" the condition and is not an isomorphism. This is why isomorphism is far more rigid than a mere edge-preserving map (a graph homomorphism); isomorphism requires the bijection to be a perfect two-way dictionary between adjacency patterns.

Figure
Two labelings of the same 4-cycle: relabeling 1,2,3,4↦a,c,b,d1,2,3,4 \mapsto a,c,b,d preserves all adjacencies
1 2 3 4 G (square 1-2-3-4) φ a c b d H (diamond a-c-b-d)

Central theorem

TheoremIsomorphism Is an Equivalence Relation Preserving Invariants

Let G\mathcal{G} denote the class of all (finite, simple) graphs. Then:

(a) The relation ≅\cong is an equivalence relation on G\mathcal{G}: it is reflexive, symmetric, and transitive.

(b) If G≅HG \cong H via isomorphism φ\varphi, then for every v∈VGv \in V_G,

deg⁡G(v)=deg⁡H(φ(v)),\deg_G(v) = \deg_H(\varphi(v)),

and consequently GG and HH have the same degree sequence (the multiset of vertex degrees, listed in non-increasing order), the same number of vertices, and the same number of edges.

(c) More generally, if ff is any function on graphs defined purely in terms of the adjacency relation — that is, f(G)f(G) depends only on the isomorphism type of (VG,EG)(V_G, E_G) — then ff is a graph invariant: G≅H  ⟹  f(G)=f(H)G \cong H \implies f(G) = f(H).

Proof

We prove each part in turn, using only the definition of isomorphism and the Graphs and Basic Definitions together with Degree and the Handshake Lemma for the degree statement.

(a) Equivalence relation. We check the three defining properties directly from the definition of isomorphism. Reflexivity. For any graph GG, the identity map idVG:VG→VG\mathrm{id}_{V_G}: V_G \to V_G is a bijection, and trivially {u,v}∈EG  ⟺  {id(u),id(v)}∈EG\{u,v\} \in E_G \iff \{\mathrm{id}(u), \mathrm{id}(v)\} \in E_G since id(u)=u\mathrm{id}(u) = u and id(v)=v\mathrm{id}(v) = v. Hence idVG\mathrm{id}_{V_G} is an isomorphism from GG to itself, so G≅GG \cong G. Symmetry. Suppose G≅HG \cong H via isomorphism φ:VG→VH\varphi: V_G \to V_H. Since φ\varphi is a bijection, it has a two-sided inverse φ−1:VH→VG\varphi^{-1}: V_H \to V_G, which is also a bijection (this is a standard fact about bijections between finite sets: a bijection has a unique inverse function, and that inverse is itself a bijection). We claim φ−1\varphi^{-1} is an isomorphism from HH to GG. Let x,y∈VHx, y \in V_H; write x=φ(u)x = \varphi(u), y=φ(v)y = \varphi(v) for the unique u=φ−1(x)u = \varphi^{-1}(x), v=φ−1(y)∈VGv = \varphi^{-1}(y) \in V_G. Then

{x,y}∈EH  ⟺  {φ(u),φ(v)}∈EH  ⟺  {u,v}∈EG  ⟺  {φ−1(x),φ−1(y)}∈EG,\{x, y\} \in E_H \iff \{\varphi(u), \varphi(v)\} \in E_H \iff \{u, v\} \in E_G \iff \{\varphi^{-1}(x), \varphi^{-1}(y)\} \in E_G,

where the middle equivalence is exactly the defining property of φ\varphi as an isomorphism (applied in the direction EG⇔EHE_G \Leftrightarrow E_H). This chain shows φ−1\varphi^{-1} preserves adjacency both ways, so H≅GH \cong G. Transitivity. Suppose G≅HG \cong H via φ\varphi and H≅KH \cong K via ψ:VH→VK\psi: V_H \to V_K. Composition of bijections is a bijection (a standard fact: if φ\varphi is injective/surjective and ψ\psi is injective/surjective then ψ∘φ\psi \circ \varphi is injective/surjective, by direct verification of the definitions), so ψ∘φ:VG→VK\psi \circ \varphi : V_G \to V_K is a bijection. For u,v∈VGu, v \in V_G:

{u,v}∈EG  ⟺  {φ(u),φ(v)}∈EH  ⟺  {ψ(φ(u)),ψ(φ(v))}∈EK,\{u,v\} \in E_G \iff \{\varphi(u), \varphi(v)\} \in E_H \iff \{\psi(\varphi(u)), \psi(\varphi(v))\} \in E_K,

using the isomorphism property of φ\varphi for the first equivalence and of ψ\psi for the second. Hence {u,v}∈EG  ⟺  {(ψ∘φ)(u),(ψ∘φ)(v)}∈EK\{u,v\} \in E_G \iff \{(\psi\circ\varphi)(u), (\psi\circ\varphi)(v)\} \in E_K, so ψ∘φ\psi \circ \varphi is an isomorphism G→KG \to K, giving G≅KG \cong K. Reflexivity, symmetry, and transitivity together establish that ≅\cong is an equivalence relation on G\mathcal{G}.

(b) Degree preservation. Let φ:VG→VH\varphi: V_G \to V_H be an isomorphism and fix v∈VGv \in V_G. By definition,

deg⁡G(v)=∣{u∈VG:{u,v}∈EG}∣.\deg_G(v) = |\{u \in V_G : \{u,v\} \in E_G\}|.

Consider the map u↦φ(u)u \mapsto \varphi(u) restricted to the neighborhood NG(v)={u:{u,v}∈EG}N_G(v) = \{u : \{u,v\}\in E_G\}. Because φ\varphi is injective, this restriction is injective, so it is a bijection from NG(v)N_G(v) onto its image φ(NG(v))⊆VH\varphi(N_G(v)) \subseteq V_H. We claim φ(NG(v))=NH(φ(v))\varphi(N_G(v)) = N_H(\varphi(v)), the neighborhood of φ(v)\varphi(v) in HH. (⊆\subseteq) If u∈NG(v)u \in N_G(v) then {u,v}∈EG\{u,v\} \in E_G, so by the isomorphism property {φ(u),φ(v)}∈EH\{\varphi(u), \varphi(v)\} \in E_H, i.e. φ(u)∈NH(φ(v))\varphi(u) \in N_H(\varphi(v)). (⊇\supseteq) Let w∈NH(φ(v))w \in N_H(\varphi(v)), so {w,φ(v)}∈EH\{w, \varphi(v)\} \in E_H. Since φ\varphi is surjective, w=φ(u)w = \varphi(u) for some u∈VGu \in V_G. Then {φ(u),φ(v)}∈EH\{\varphi(u), \varphi(v)\} \in E_H, and by the isomorphism property (the ⇐\Leftarrow direction) {u,v}∈EG\{u,v\} \in E_G, so u∈NG(v)u \in N_G(v) and w=φ(u)∈φ(NG(v))w = \varphi(u) \in \varphi(N_G(v)). Thus φ\varphi restricts to a bijection NG(v)→NH(φ(v))N_G(v) \to N_H(\varphi(v)), giving

deg⁡G(v)=∣NG(v)∣=∣NH(φ(v))∣=deg⁡H(φ(v)).\deg_G(v) = |N_G(v)| = |N_H(\varphi(v))| = \deg_H(\varphi(v)).

Since φ\varphi is a bijection on the full vertex sets, the multiset {deg⁡G(v):v∈VG}\{\deg_G(v) : v \in V_G\} equals the multiset {deg⁡H(φ(v)):v∈VG}={deg⁡H(w):w∈VH}\{\deg_H(\varphi(v)) : v \in V_G\} = \{\deg_H(w) : w \in V_H\} (re-indexing the sum/multiset over the bijection φ\varphi). Sorting both multisets into non-increasing order produces identical sequences, so GG and HH have the same degree sequence. Since φ\varphi is a bijection VG→VHV_G \to V_H, ∣VG∣=∣VH∣|V_G| = |V_H|. For the edge count, apply the Degree and the Handshake Lemma (Handshake Lemma) to both graphs:

2∣EG∣=∑v∈VGdeg⁡G(v)=∑v∈VGdeg⁡H(φ(v))=∑w∈VHdeg⁡H(w)=2∣EH∣,2|E_G| = \sum_{v \in V_G} \deg_G(v) = \sum_{v \in V_G} \deg_H(\varphi(v)) = \sum_{w \in V_H} \deg_H(w) = 2|E_H|,

where the middle equality re-sums over the bijection φ\varphi exactly as above. Hence ∣EG∣=∣EH∣|E_G| = |E_H|.

(c) General invariants. Suppose ff is a function on graphs whose value f(G)f(G) is determined entirely by the isomorphism type of GG, meaning: ff is defined as some property or count of the abstract relational structure (VG,EG)(V_G, E_G) that does not reference vertex labels — for instance "the number of kk-vertex subsets inducing a complete subgraph," "the length of a longest path," "whether the graph is connected," or "the number of spanning trees." Formally, this means ff is built from operations that commute with relabeling: if φ:VG→VH\varphi: V_G \to V_H is any bijection carrying EGE_G to EHE_H (i.e. any isomorphism), then applying φ\varphi to every set/structure entering the definition of f(G)f(G) produces exactly the corresponding structure for f(H)f(H), since φ\varphi is by hypothesis a bijection on vertices respecting adjacency in both directions (parts of the argument in (b) generalize verbatim: any adjacency-defined substructure of GG, such as a triangle, a path, a cycle, a clique, or a spanning subgraph, is carried by φ\varphi to the corresponding substructure of HH, because membership in EGE_G transports exactly to membership in EHE_H). Hence counting or existence statements about such substructures are unchanged. Therefore f(G)=f(H)f(G) = f(H) whenever G≅HG \cong H, i.e. ff is a graph invariant. ■\blacksquare

∎

Worked examples

Example 1: Constructing an explicit isomorphism (asymmetric labeling). Let GG have vertex set VG={p,q,r,s,t}V_G = \{p, q, r, s, t\} and edges

EG={ pq, qr, rs, st, tp, pr }.E_G = \{\,pq,\ qr,\ rs,\ st,\ tp,\ pr\,\}.

So GG is a 5-cycle pp–qq–rr–ss–tt–pp with one extra chord prpr. Let HH have vertex set VH={1,2,3,4,5}V_H = \{1,2,3,4,5\} and edges

EH={ 12, 23, 34, 45, 51, 24 }.E_H = \{\,12,\ 23,\ 34,\ 45,\ 51,\ 24\,\}.

So HH is the 5-cycle 11–22–33–44–55–11 with chord 2424.

Degree check first. In GG: deg⁡(p)=3\deg(p) = 3 (neighbors q,t,rq,t,r), deg⁡(r)=3\deg(r) = 3 (neighbors q,s,pq,s,p), and deg⁡(q)=deg⁡(s)=deg⁡(t)=2\deg(q)=\deg(s)=\deg(t)=2. Degree sequence: (3,3,2,2,2)(3,3,2,2,2). In HH: deg⁡(2)=3\deg(2) = 3 (neighbors 1,3,41,3,4), deg⁡(4)=3\deg(4) = 3 (neighbors 3,5,23,5,2), and deg⁡(1)=deg⁡(3)=deg⁡(5)=2\deg(1)=\deg(3)=\deg(5)=2. Degree sequence: (3,3,2,2,2)(3,3,2,2,2). They match — necessary, not yet sufficient.

Finding φ\varphi. In GG, the two degree-3 vertices p,rp, r are adjacent (chord pr∈EGpr \in E_G). In HH, the two degree-3 vertices 2,42, 4 are adjacent (chord 24∈EH24 \in E_H) — consistent, since by the theorem an isomorphism must send the chord's endpoints to the chord's endpoints. Try φ(p)=2\varphi(p) = 2, φ(r)=4\varphi(r) = 4. The cycle order in GG is p,q,r,s,tp,q,r,s,t; in HH it is 1,2,3,4,51,2,3,4,5. Sending p→2p \to 2 and going around the cycle in matching direction, qq (between p,rp,r the short way on the cycle) should go to 33 (between 2,42,4). Set:

φ(p)=2,φ(q)=3,φ(r)=4,φ(s)=5,φ(t)=1.\varphi(p) = 2,\quad \varphi(q) = 3, \quad \varphi(r) = 4, \quad \varphi(s) = 5, \quad \varphi(t) = 1.

Verification, edge by edge. We must check all 66 edges of GG map to edges of HH, and (since ∣VG∣=∣VH∣=5|V_G|=|V_H|=5 forces ∣EG∣=∣EH∣=6|E_G|=|E_H|=6 already, and φ\varphi is a bijection between two 6-element edge sets once we confirm the forward containment, equality follows by a counting argument given below) confirm no non-edge is sent to an edge.

  • pq↦φ(p)φ(q)=2 3=23∈EHpq \mapsto \varphi(p)\varphi(q) = 2\,3 = 23 \in E_H. ✓
  • qr↦3 4=34∈EHqr \mapsto 3\,4 = 34 \in E_H. ✓
  • rs↦4 5=45∈EHrs \mapsto 4\,5 = 45 \in E_H. ✓
  • st↦5 1=51∈EHst \mapsto 5\,1 = 51 \in E_H. ✓
  • tp↦1 2=12∈EHtp \mapsto 1\,2 = 12 \in E_H. ✓
  • pr↦2 4=24∈EHpr \mapsto 2\,4 = 24 \in E_H. ✓

All six images are exactly the six edges of HH, with no repeats (since φ\varphi is a bijection on vertices, distinct edges of GG map to distinct edges of HH: if {u,v}≠{u′,v′}\{u,v\} \ne \{u',v'\} as edges of GG then {φ(u),φ(v)}≠{φ(u′),φ(v′)}\{\varphi(u),\varphi(v)\} \ne \{\varphi(u'),\varphi(v')\}, because φ\varphi injective forces {u,v}={u′,v′}\{u,v\}=\{u',v'\} whenever the images coincide). So φ\varphi maps EGE_G bijectively onto EHE_H; in particular every edge of GG maps to an edge of HH, and since ∣EG∣=∣EH∣=6|E_G| = |E_H| = 6, the image φ(EG)\varphi(E_G), having 66 elements all inside the 66-element set EHE_H, must equal EHE_H exactly — there is no room for a non-edge of GG to sneak an image into EHE_H beyond what is already accounted for, and conversely every edge of HH is hit. Concretely, checking non-edges: qs∉EGqs \notin E_G and indeed φ(q)φ(s)=35∉EH\varphi(q)\varphi(s) = 35 \notin E_H; qt∉EGqt \notin E_G and φ(q)φ(t)=31∉EH\varphi(q)\varphi(t) = 31 \notin E_H; rt∉EGrt \notin E_G and φ(r)φ(t)=41∉EH\varphi(r)\varphi(t) = 41 \notin E_H; ps∉EGps \notin E_G and φ(p)φ(s)=25∉EH\varphi(p)\varphi(s)=25 \notin E_H. All four non-edges of GG (there are (52)−6=4\binom{5}{2}-6 = 4) map to non-edges of HH. Hence φ\varphi is a graph isomorphism, and G≅HG \cong H.

Example 2: Two graphs on 66 vertices, same size, decided by structure beyond degree. Let GG be the graph with VG={1,…,6}V_G = \{1,\dots,6\} and edges forming two disjoint triangles:

EG={12,13,23, 45,46,56}.E_G = \{12, 13, 23,\ 45, 46, 56\}.

Let HH have VH={a,b,c,d,e,f}V_H = \{a,b,c,d,e,f\} and edges forming a 66-cycle:

EH={ab,bc,cd,de,ef,fa}.E_H = \{ab, bc, cd, de, ef, fa\}.

Invariant check. Both graphs have 66 vertices and 66 edges. Degree sequence of GG: every vertex has degree 22 (each vertex in a triangle is adjacent to the other two), so (2,2,2,2,2,2)(2,2,2,2,2,2). Degree sequence of HH: every vertex in a cycle has degree 22, so also (2,2,2,2,2,2)(2,2,2,2,2,2). Vertex count, edge count, and degree sequence all agree — invariants so far give no obstruction.

A finer invariant: connectivity. By part (c) of the theorem, "is the graph connected" is an isomorphism invariant, since connectivity is defined purely via existence of adjacency-paths, a notion transported faithfully by any adjacency-preserving bijection. HH is connected: from any vertex one can walk around the single 66-cycle to reach any other. GG is disconnected: there is no path from vertex 11 to vertex 44, since every edge of GG lies entirely inside {1,2,3}\{1,2,3\} or entirely inside {4,5,6}\{4,5,6\}, so no sequence of edges can cross between the two triangles. Since connectedness is an invariant (Theorem, part (c)) and GG is disconnected while HH is connected, we conclude

G≇H,G \not\cong H,

even though ∣VG∣=∣VH∣|V_G| = |V_H|, ∣EG∣=∣EH∣|E_G| = |E_H|, and both degree sequences equal (2,2,2,2,2,2)(2,2,2,2,2,2). This shows degree sequence alone is not a complete invariant, foreshadowing the counterexample below and the need for finer invariants such as those studied via eigenvalues in Introduction to Spectral Graph Theory.

CounterexampleMatching degree sequences do not imply isomorphism

The theorem proves that isomorphic graphs must share every invariant, including degree sequence. It does not claim the converse — that graphs sharing an invariant, or even all of a long list of invariants, must be isomorphic. Dropping the hypothesis "φ\varphi is a bijection preserving adjacency in both directions" down to merely "same degree sequence" breaks the conclusion entirely. Here is an explicit pair. Let G1G_1 be two disjoint copies of the path on three vertices P3P_3: vertices {1,2,3,4,5,6}\{1,2,3,4,5,6\} with edges

EG1={12,23, 45,56}.E_{G_1} = \{12, 23,\ 45, 56\}.

Degrees: deg⁡(1)=1,deg⁡(2)=2,deg⁡(3)=1,deg⁡(4)=1,deg⁡(5)=2,deg⁡(6)=1\deg(1)=1, \deg(2)=2,\deg(3)=1,\deg(4)=1,\deg(5)=2,\deg(6)=1, giving sorted sequence (2,2,1,1,1,1)(2,2,1,1,1,1). Let G2G_2 be a single path on six vertices, {a,b,c,d,e,f}\{a,b,c,d,e,f\} with edges

EG2={ab,bc,cd,de,ef}.E_{G_2} = \{ab, bc, cd, de, ef\}.

Wait — this has only 55 edges while G1G_1 has 44; to keep edge count matching we instead take G2G_2 to be a 66-cycle broken differently: let G2G_2 have edges

EG2={ab,bc,cd,de,ef,fa}∖{fa}∪{ce}={ab,bc,cd,de,ef,ce}.E_{G_2} = \{ab, bc, cd, de, ef, fa\} \setminus \{fa\} \cup \{ce\} = \{ab,bc,cd,de,ef,ce\}.

Concretely EG2={ab,bc,cd,de,ef,ce}E_{G_2} = \{ab, bc, cd, de, ef, ce\}, a path a-b-c-d-e-fa\text{-}b\text{-}c\text{-}d\text{-}e\text{-}f with an extra chord cece. This has 66 edges, not 44, so instead compare G1G_1 (4 edges) against a graph with the same edge count and degree sequence but different shape: Let G2′G_2' have vertices {a,b,c,d,e,f}\{a,b,c,d,e,f\} and edges

EG2′={ab,bc,cd,da},E_{G_2'} = \{ab, bc, cd, da\},

a single 44-cycle aa-bb-cc-dd-aa, together with two isolated vertices e,fe, f. Degrees: deg⁡(a)=deg⁡(b)=deg⁡(c)=deg⁡(d)=2\deg(a)=\deg(b)=\deg(c)=\deg(d) = 2, deg⁡(e)=deg⁡(f)=0\deg(e) = \deg(f) = 0. Sorted degree sequence: (2,2,2,2,0,0)(2,2,2,2,0,0) — this does not match G1G_1's (2,2,1,1,1,1)(2,2,1,1,1,1), so this pair is not the right counterexample either; let us fix the construction cleanly.

Correct minimal counterexample. Take

G1=P3⊔P3(two disjoint 3-vertex paths, as above, degree sequence (2,2,1,1,1,1), 4 edges),G_1 = P_3 \sqcup P_3 \quad (\text{two disjoint 3-vertex paths, as above, degree sequence } (2,2,1,1,1,1), \ 4 \text{ edges}),
G2=P6∖{middle edge} replaced appropriately  ⟶  use instead: G2=a single path P5 plus one isolated vertex.G_2 = P_6 \setminus \{\text{middle edge}\}\ \text{replaced appropriately} \;\longrightarrow\; \text{use instead: } G_2 = \text{a single path } P_5 \text{ plus one isolated vertex}.

Explicitly VG2={1,2,3,4,5,6}V_{G_2} = \{1,2,3,4,5,6\}, EG2={12,23,34,45}E_{G_2} = \{12,23,34,45\} (a path on vertices 1,2,3,4,51,2,3,4,5) with vertex 66 isolated. Degrees: deg⁡(1)=1,deg⁡(2)=2,deg⁡(3)=2,deg⁡(4)=2,deg⁡(5)=1,deg⁡(6)=0\deg(1)=1,\deg(2)=2,\deg(3)=2,\deg(4)=2,\deg(5)=1,\deg(6)=0. Sorted: (2,2,2,1,1,0)(2,2,2,1,1,0) — still not matching (2,2,1,1,1,1)(2,2,1,1,1,1). To match (2,2,1,1,1,1)(2,2,1,1,1,1) exactly with a connected graph on 66 vertices and 44 edges is impossible (a connected graph on 66 vertices needs at least 55 edges), so the cleanest true counterexample compares G1=P3⊔P3G_1 = P_3 \sqcup P_3 against G3=P4⊔K2G_3 = P_4 \sqcup K_2 pieces — but P4P_4 alone already has degree sequence (2,2,1,1)(2,2,1,1) so G3=P4⊔K2G_3 = P_4 \sqcup K_2 (a 44-path plus a disjoint single edge) on 66 vertices has degrees (2,2,1,1,1,1)(2,2,1,1,1,1): exactly the same sorted degree sequence as G1G_1, and the same number of edges, 3+1=43 + 1 = 4. So the genuine counterexample is:

G1=P3⊔P3,G3=P4⊔K2,G_1 = P_3 \sqcup P_3, \qquad G_3 = P_4 \sqcup K_2,

both with 66 vertices, 44 edges, and identical degree sequence (2,2,1,1,1,1)(2,2,1,1,1,1). These are not isomorphic: G1G_1's largest connected piece has 33 vertices, while G3G_3 has a connected piece (P4P_4) with 44 vertices. "Size of the largest connected component" is an isomorphism invariant (an instance of Theorem part (c), since connected components and their sizes are determined purely by the adjacency relation), and it takes the value 33 on G1G_1 but 44 on G3G_3. Hence G1≇G3G_1 \not\cong G_3, despite agreeing on vertex count, edge count, and full degree sequence. This shows precisely what fails if one tries to define isomorphism as "same degree sequence" instead of "adjacency-preserving bijection exists": the weaker condition is satisfiable by structurally different graphs, so it cannot serve as a correct definition or a sufficient test.

Scope, edge cases & common traps

SituationWhat holds
G,HG, H isomorphicSame ∥V∥\|V\|, ∥E∥\|E\|, degree sequence, connectivity, number of triangles/cycles of each length, spectrum, chromatic number, and every other invariant
Same degree sequence onlyNot sufficient for isomorphism (see counterexample)
Same number of vertices and edges onlyNot sufficient; weaker than degree sequence match
G≅HG \cong H but graphs have loops or multi-edgesDefinition given here is for simple graphs; multigraphs/loops need adjacency multiplicities preserved too
Directed graphsIsomorphism must preserve arc direction: (u,v)∈EG  ⟺  (φ(u),φ(v))∈EH(u,v) \in E_G \iff (\varphi(u),\varphi(v)) \in E_H, a strictly stronger condition than for undirected graphs
Checking isomorphism by brute forceAlways sound but costs up to n!n! bijections to try; invariants are used to prune, not to decide, in general
Aut(G)\mathrm{Aut}(G) trivial (only the identity)Graph is called rigid; happens for "generic" graphs with no repeated local structure

The mathematician behind it

Origins · 1 minEugene M. Luks and how this was discovered
EM
Eugene M. Luks
1940s–present · Theoretical computer science and computational complexity, University of Oregon

Luks is best known for a landmark 1982 result showing that graph isomorphism can be decided in polynomial time when the input graphs have bounded vertex degree — a striking positive result in a landscape otherwise dominated by uncertainty. His techniques, combining group-theoretic methods (analyzing the automorphism group's structure via composition series) with combinatorial partitioning, became foundational for later attacks on the general graph isomorphism problem, including László Babai's quasipolynomial-time algorithm decades later. The bounded-degree case captures a large fraction of graphs arising in chemistry and network science, where practical instances rarely have huge-degree vertices.

History
- 1852: Informal notions of "same map" and graph structure appear implicitly in early combinatorial map-coloring work, predating formal graph theory.
- 1930s: Systematic graph-theoretic language (Kőnig, Whitney) establishes isomorphism as the natural equivalence relation identifying graphs up to relabeling.
- 1957: A. J. Hoffman and others begin systematically using eigenvalues of the adjacency matrix as isomorphism invariants, seeding what becomes spectral graph theory.
- 1970s: Graph Isomorphism is identified as a key problem neither known to be in P nor proven NP-complete, placed in a distinguished intermediate complexity class discussion.
- 1982: Eugene Luks proves polynomial-time decidability for bounded-degree graphs, a major structural breakthrough using group-theoretic algorithms.
- 2015–2017: László Babai announces (and after a brief gap, confirms) a quasipolynomial-time algorithm for general graph isomorphism, the strongest known upper bound to date.
Is graph isomorphism the same as graph equality?

No. Graph equality would require VG=VHV_G = V_H and EG=EHE_G = E_H as literal sets — same vertex names, same edge set. Isomorphism is weaker and more useful: it only asks whether some relabeling (bijection φ\varphi) turns GG into HH exactly. Two graphs drawn with completely different vertex names, and even different physical layouts, can be isomorphic. Equality is a special case of isomorphism (via the identity map), but isomorphism captures the "structurally identical" idea that mathematicians actually care about, since vertex labels are usually arbitrary bookkeeping rather than meaningful data.

Why isn't matching degree sequences enough to prove isomorphism?

Degree sequence only records local information — how many neighbors each vertex has — and discards how those neighborhoods connect to each other globally. Two graphs can have every vertex touching the same number of edges while being wired into completely different global shapes, such as one graph forming two separate triangles and another forming a single hexagonal cycle, both with degree sequence (2,2,2,2,2,2)(2,2,2,2,2,2). The counterexample in this article makes this failure completely explicit with a connectedness argument, which is itself a valid invariant that degree sequence does not capture.

Is deciding graph isomorphism computationally hard?

It is unresolved. Graph Isomorphism is known to be in NP (a candidate bijection can be checked in polynomial time), but it has never been proven NP-complete, and no general polynomial-time algorithm is known either. László Babai's 2015–2017 algorithm runs in quasipolynomial time, faster than any previously known general method, but still not proven polynomial. For special cases — bounded degree, planar graphs, trees — polynomial or even linear-time algorithms are known and well understood.

What is the difference between isomorphism and homomorphism?

A graph homomorphism only requires that edges map to edges: {u,v}∈EG  ⟹  {φ(u),φ(v)}∈EH\{u,v\} \in E_G \implies \{\varphi(u),\varphi(v)\} \in E_H, with no requirement of bijectivity and no requirement that non-edges map to non-edges. Isomorphism is strictly stronger: it demands a bijection and the full "if and only if" adjacency-preservation in both directions. Every isomorphism is a homomorphism (and its inverse is too), but a homomorphism need not be injective, surjective, or reversible, so it can collapse structure that isomorphism must preserve exactly.

What does the automorphism group tell you about a graph?

Aut(G)\mathrm{Aut}(G) collects every way of relabeling GG's own vertices that leaves the adjacency relation unchanged, forming a group under composition (identity, inverses, and closure all follow from the equivalence-relation proof given above applied to self-isomorphisms). A large automorphism group signals rich internal symmetry — the complete graph KnK_n has Aut(Kn)\mathrm{Aut}(K_n) equal to the full symmetric group SnS_n, since every permutation preserves "all pairs adjacent." A trivial automorphism group (only the identity) means the graph is rigid, with no nontrivial self-symmetry, which is typical of "generic" random graphs.

Can two graphs with different numbers of vertices be isomorphic?

No. Part of the definition of isomorphism requires a bijection φ:VG→VH\varphi: V_G \to V_H, and a bijection between finite sets can only exist if the sets have the same cardinality. So ∣VG∣=∣VH∣|V_G| = |V_H| is an immediate, absolute prerequisite for G≅HG \cong H; checking vertex counts is always the very first, cheapest invariant test before attempting anything more elaborate.

How does isomorphism connect to spectral graph theory?

The adjacency matrix's eigenvalues (its spectrum) form a graph invariant: relabeling vertices via a permutation matrix PP conjugates the adjacency matrix as PAP−1PAP^{-1}, and conjugate matrices share the same eigenvalues, so isomorphic graphs have identical spectra. This gives a powerful, easily computed invariant beyond degree sequences, though — mirroring the moral of this article's counterexample — non-isomorphic graphs can occasionally share a spectrum too (so-called cospectral mates), a subtlety explored further in Introduction to Spectral Graph Theory.

Before this

Where this leads