1
It is a bijection that preserves adjacency
Both directions: adjacent vertices map to adjacent vertices, and non-adjacent to non-adjacent.
Lesson · Graphs and Trees · Structure
Subgraphs and Graph Isomorphism
An isomorphism is a relabelling preserving adjacency. Proving two graphs isomorphic means exhibiting one; proving they are not means finding an invariant that differs.
isomorphism: a bijection f : V₁ → V₂ with u~v ⟺ f(u)~f(v)
to PROVE isomorphic: exhibit the bijection
to DISPROVE: find an invariant that differs
invariants: |V|, |E|, degree sequence, cycle lengths, connectivity
Same graph, different labels
Core ideas
What this lesson establishes
Isomorphism is Sets, Relations, and Functions's bijection with a structure-preserving condition attached.
2
Invariants disprove, they never prove
Matching every invariant you can think of is not a proof of isomorphism. Only an explicit bijection is.
3
Nobody knows how hard the problem is
Graph isomorphism is not known to be in P and not known to be NP-complete — an unusual position for a natural problem.
The material
Isomorphism
The definition, the invariants, and how to argue each way.
Definition · Subgraph
H is a subgraph of G when V(H) ⊆ V(G) and E(H) ⊆ E(G). It is induced by a vertex set S when it contains every edge of G with both ends in S.
Definition · Isomorphism
Graphs G₁ and G₂ are isomorphic, written G₁ ≅ G₂, when there is a bijection f : V₁ → V₂ such that u and v are adjacent in G₁ if and only if f(u) and f(v) are adjacent in G₂.
Isomorphic graphs are the same graph with different labels and different drawings. Every property expressible in terms of adjacency alone — connectivity, cycle lengths, degrees, colourability — is shared by isomorphic graphs.
Invariants
number of vertices
number of edges
degree sequence (sorted)
number of components
lengths of the cycles present
bipartite or not
number of triangles ( = trace(A³)/6 )
connectivity, chromatic number, planarity
Any difference in any invariant proves non-isomorphism, and this is the practical method: check the cheap invariants first and stop at the first disagreement. Agreement on all of them proves nothing.
Example · Same degree sequence, not isomorphic
Take G₁ to be two disjoint triangles and G₂ to be a 6-cycle. Both have 6 vertices, both have 6 edges, and both are 2-regular with degree sequence (2,2,2,2,2,2). They are not isomorphic: G₁ has two components and G₂ has one, and G₁ contains 3-cycles while G₂'s only cycle has length 6.
That example is the standard warning. The degree sequence is the invariant people reach for first, and it is genuinely weak — there are non-isomorphic pairs agreeing on every invariant in the table above.
Proving isomorphism
The only proof is an explicit bijection, verified on every edge. A practical strategy is to use the degrees to narrow the possibilities: a vertex of degree 5 must map to a vertex of degree 5, and often that pins most of the map.
Example · A bijection
Take the 4-cycle labelled 1–2–3–4–1 and the graph on a,b,c,d with edges ab, bd, dc, ca. Map 1→a, 2→b, 3→d, 4→c. Check all four edges: 12→ab ✓, 23→bd ✓, 34→dc ✓, 41→ca ✓. And there are four edges in each, so no non-edge maps to an edge. Isomorphic.
How hard is the problem?
Deciding isomorphism has no known polynomial-time algorithm and is not known to be NP-complete. It sits in an unusual middle position that very few natural problems occupy. Babai announced a quasi-polynomial algorithm in 2015 — running in time exp((log n)^{O(1)}), faster than exponential and slower than polynomial.
In practice, isomorphism testers handle graphs with thousands of vertices routinely, because real graphs have structure the worst case does not. This is the same gap between worst-case hardness and practical difficulty that Logic and Proof noted for SAT.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Deciding isomorphism
Try to disprove first; it is much cheaper.
1
Compare the cheap invariants
Vertex count, edge count, degree sequence. Any difference ends the question immediately.
2
Compare structural invariants
Component count, cycle lengths, triangle count, bipartiteness. These catch most remaining pairs.
3
If all agree, construct a bijection
Use degrees to constrain it: degree-k vertices must map to degree-k vertices, and neighbourhoods must correspond.
4
Verify every edge
Both directions. A bijection preserving edges but mapping a non-edge to an edge is not an isomorphism — though for graphs with equal edge counts, preserving edges is enough.
Isomorphism
Score 0 / 0Choose the answer you can justify.
Are these isomorphic?
G₁: 6-cycle. G₂: two disjoint triangles.
|V| 6 6 same
|E| 6 6 same
degree sequence 222222 222222 same
components 1 2 DIFFERENT
⟹ NOT isomorphic.
A second invariant confirms it:
shortest cycle length 6 3 DIFFERENT
Three invariants agreed and two disagreed. Either disagreement
is a complete proof; the three agreements were worth nothing.
This asymmetry is the whole method. Disproving is a matter of finding one difference, and proving requires exhibiting a bijection — which is why every practical algorithm spends its time trying to disprove.
Common mistakes
1
Treating matching invariants as proofThey are necessary conditions. Only an explicit bijection establishes isomorphism.
2
Assuming similar drawings mean isomorphic graphsThe drawing carries no information. K₄ drawn as a square with diagonals and as a triangle with a centre are the same graph.
3
Checking only that edges map to edgesFor graphs with equal edge counts that suffices, and stating why is part of the argument. In general both directions must be checked.
Check your understanding
✓
Finish when you reach for invariants before attempting a bijection.
Given two graphs on eight vertices, list the invariants you would check and in what order. Cheapest first, and stop at the first disagreement.
Note: Isomorphism is why graph theory speaks of "the" cycle Cₙ and "the" complete graph Kₙ. There are many labelled graphs with that structure and exactly one up to isomorphism, and the theorems are about the structure.