Mathematics.

graph structures

Graph Isomorphism

Graph Theory25 minDifficulty4 out of 10

You should know: graph basics

Overview

Two graphs are isomorphic if there exists a bijection between their vertex sets that preserves adjacency: an edge exists between two vertices in one graph exactly when an edge exists between their corresponding vertices in the other. Isomorphic graphs are structurally identical — they may look different when drawn (different vertex labels, positions) but represent the same abstract structure. Checking two graphs are NOT isomorphic is often easy using invariants (properties preserved by isomorphism, like degree sequence, number of vertices/edges, or number of triangles) that must match if the graphs are isomorphic; but proving two graphs ARE isomorphic, or finding an efficient general algorithm, remains a famously open problem — graph isomorphism is one of the few problems believed to be neither NP-complete nor solvable in polynomial time.

Intuition

Imagine two org charts drawn with employees at different positions on the page, using different names, but representing the exact same reporting structure. If you could relabel one chart's names to match the other and every reporting line would line up perfectly, the charts are isomorphic — same underlying structure, different surface presentation. Graph isomorphism asks exactly this: strip away labels and layout, and ask whether two graphs are 'the same shape'.

Formal Definition

Definition

Graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there is a bijection f preserving adjacency:

∃ f:V1→V2 bijective such that {u,v}∈E1  ⟺  {f(u),f(v)}∈E2\exists\ f: V_1 \to V_2 \text{ bijective such that } \{u,v\} \in E_1 \iff \{f(u), f(v)\} \in E_2
Isomorphism definition
G1≅G2⇒deg⁡G1(v)=deg⁡G2(f(v)) ∀vG_1 \cong G_2 \Rightarrow \deg_{G_1}(v) = \deg_{G_2}(f(v)) \ \forall v
Degree sequence is preserved (invariant)

Worked Examples

  1. Try the mapping f: 1→a, 2→b, 3→c. Check each edge of G1 maps to an edge of G2: edge 1-2 maps to a-b (present); edge 2-3 maps to b-c (present).

    f(1)=a, f(2)=b, f(3)=cf(1)=a,\ f(2)=b,\ f(3)=c

  2. Both graphs have exactly 2 edges and the mapping preserves all of them with no extras, so f is a valid isomorphism.

    {1,2}∈E1  ⟺  {a,b}∈E2, {2,3}∈E1  ⟺  {b,c}∈E2\{1,2\}\in E_1 \iff \{a,b\}\in E_2,\ \{2,3\}\in E_1 \iff \{b,c\}\in E_2

Answer: Yes, isomorphic via f(1)=a, f(2)=b, f(3)=c (both are the path graph on 3 vertices).

Practice Problems

Difficulty 3/10

Graph G1 has 5 vertices and 6 edges. Graph G2 has 5 vertices and 7 edges. Can they be isomorphic?

Difficulty 4/10

Two companies each model their internal communication network as a graph with the same number of employees and the same degree sequence. Does matching degree sequences guarantee the networks are isomorphic?

Difficulty 5/10

Why is the graph isomorphism problem considered theoretically unusual in computational complexity?

Quiz

Two graphs are isomorphic if there exists:
If two graphs have different degree sequences, they:
Matching degree sequences between two graphs is:

Summary

  • Two graphs are isomorphic if an adjacency-preserving bijection exists between their vertices — they're structurally identical despite different labels/drawings.
  • Invariants like degree sequence, edge count, and triangle count must match for isomorphic graphs, giving an easy way to disprove isomorphism.
  • No efficient general algorithm for graph isomorphism is known, and its complexity status (neither known P nor believed NP-complete) remains a celebrated open problem.

References

  1. WebsiteWikipedia — Graph isomorphism