Graph Isomorphism

Definition

Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there exists a bijection $f: V_1 \to V_2$ such that: $(u, v) \in E_1 \iff (f(u), f(v)) \in E_2$

Notation: $G_1 \cong G_2$

Intuitively, isomorphic graphs have the same structure — only vertex labels differ.

Graph Invariants

Properties preserved under isomorphism. If $G_1 \cong G_2$, they must have the same:

Basic Invariants

• Number of vertices $|V|$
• Number of edges $|E|$
• Degree sequence (multiset of all degrees)

Structural Invariants

• Number of connected components
• Number of cycles of each length
• Diameter (longest shortest path)
• Girth (length of shortest cycle)
• Chromatic number
• Number of spanning trees

Spectral Invariants

• Eigenvalues of adjacency matrix
• Eigenvalues of Laplacian matrix

Using Invariants

Invariants can prove graphs are NOT isomorphic.

Example:

• $G_1$: degree sequence $(2, 2, 2, 2)$
• $G_2$: degree sequence $(3, 2, 2, 1)$

$G_1 \not\cong G_2$ because degree sequences differ.

Warning: Equal invariants don't prove isomorphism!

Degree Sequence Analysis

Matching Vertices

Vertices with the same degree in isomorphic graphs can only map to each other.

Neighbors' Degrees

If $v$ maps to $w$, then neighbors of $v$ must map to neighbors of $w$ with matching degrees.

Algorithm for Small Graphs

1. Check basic invariants (if different, not isomorphic)
2. Partition vertices by degree
3. Try to match vertices of same degree
4. Verify adjacency relationships
5. If a valid bijection exists, graphs are isomorphic

Examples

Non-Isomorphic Detection

Graphs with 4 vertices, 4 edges:

• Square $C_4$: degree sequence $(2, 2, 2, 2)$
• $K_4$ minus edge: degree sequence $(3, 3, 2, 2)$

Not isomorphic (different degree sequences).

Isomorphism Verification

Example: Are these isomorphic?

• $G_1$: vertices $\{1,2,3,4\}$, edges $\{(1,2), (2,3), (3,4), (4,1)\}$
• $G_2$: vertices $\{a,b,c,d\}$, edges $\{(a,b), (b,c), (c,d), (d,a)\}$

Both are 4-cycles with degree sequence $(2,2,2,2)$.

Bijection: $1 \to a, 2 \to b, 3 \to c, 4 \to d$ preserves adjacency.

Therefore $G_1 \cong G_2$.

Automorphisms

An automorphism of a graph is an isomorphism from the graph to itself.

Automorphism Group

The set of all automorphisms forms a group under composition, denoted $\text{Aut}(G)$.

Examples

• Complete graph $K_n$: $|\text{Aut}(K_n)| = n!$
• Path $P_n$: $|\text{Aut}(P_n)| = 2$ (identity and reversal)
• Cycle $C_n$: $|\text{Aut}(C_n)| = 2n$ (rotations and reflections)

Vertex-Transitive Graphs

A graph is vertex-transitive if for any two vertices $u, v$, there exists an automorphism mapping $u$ to $v$.

Examples: Complete graphs, cycles, hypercubes.

Labeled vs. Unlabeled Graphs

Labeled Graphs

Vertices have distinct labels. Two labeled graphs are isomorphic if there's a label-preserving bijection (i.e., they're identical).

Unlabeled Graphs

We consider graphs the same if isomorphic.

Counting

$n$	Labeled simple graphs	Unlabeled simple graphs
1	1	1
2	2	2
3	8	4
4	64	11
5	1024	34

Labeled: $2^{\binom{n}{2}}$ (each potential edge is present or not)

Computational Complexity

Graph Isomorphism Problem

Given two graphs, determine if they're isomorphic.

• Not known to be in P
• Not known to be NP-complete
• Quasipolynomial time algorithm exists (Babai, 2015)

Subgraph Isomorphism Problem

Given $G$ and $H$, is $H$ isomorphic to a subgraph of $G$?

This problem is NP-complete.

Canonical Forms

A canonical form assigns a unique representative to each isomorphism class.

Canonical Labeling

Relabel vertices in a standard way so isomorphic graphs get identical representations.

Applications

• Graph databases
• Chemical structure comparison
• Network analysis