Chapter 15. Graph Isomorphism

Two graphs may look different when drawn, yet represent the same abstract structure. Graph theory studies adjacency relations, not geometric appearance or vertex labels. The concept that captures structural sameness is graph isomorphism.

An isomorphism is a relabeling of vertices that preserves adjacency. If two graphs are isomorphic, they differ only in presentation. They are considered the same graph from the structural viewpoint of graph theory. Standard definitions describe graph isomorphism as a bijection preserving adjacency relations. (en.wikipedia.org)

15.1 Definition of Graph Isomorphism

Let

G=(V_G,E_G)

and

H=(V_H,E_H)

be graphs.

An isomorphism from $G$ to $H$ is a bijection

f:V_G\to V_H

such that for all vertices

u,v\in V_G,

we have

\{u,v\}\in E_G \quad\Longleftrightarrow\quad \{f(u),f(v)\}\in E_H.

Thus adjacency is preserved exactly.

If such a bijection exists, the graphs are isomorphic, written

G\cong H.

If no such bijection exists, the graphs are non-isomorphic.

The condition must preserve both edges and non-edges. Adjacent vertices must map to adjacent vertices, and nonadjacent vertices must map to nonadjacent vertices.

15.2 Structural Interpretation

An isomorphism changes names but not structure.

Suppose

G

has vertices

\{a,b,c,d\}

and edges

\{\{a,b\},\{b,c\},\{c,d\}\}.

Suppose

H

has vertices

\{1,2,3,4\}

and edges

\{\{1,2\},\{2,3\},\{3,4\}\}.

The mapping

a\mapsto 1, \qquad b\mapsto 2, \qquad c\mapsto 3, \qquad d\mapsto 4

preserves adjacency. Therefore

G\cong H.

Both graphs are simply paths on four vertices.

A graph drawing may stretch, rotate, bend, or reorder vertices. None of these changes affect isomorphism.

15.3 Non-Isomorphic Graphs

Two graphs are not isomorphic if no adjacency-preserving bijection exists.

Often this can be shown using graph invariants.

For example, suppose $G$ has degree sequence

(3,2,2,1)

while $H$ has degree sequence

(2,2,2,2).

Since degree sequence is preserved by isomorphism, the graphs cannot be isomorphic.

Thus

G\not\cong H.

Differences in order, size, degree sequence, component count, diameter, cycle structure, chromatic number, or other invariants can all prove non-isomorphism.

15.4 Isomorphism as an Equivalence Relation

Graph isomorphism is an equivalence relation.

Reflexivity

Every graph is isomorphic to itself. The identity map

f(v)=v

preserves adjacency.

Thus

G\cong G.

Symmetry

G\cong H,

then

H\cong G.

The inverse of an isomorphism is also an isomorphism.

Transitivity

G\cong H

and

H\cong K,

then

G\cong K.

The composition of two isomorphisms is an isomorphism.

Therefore isomorphism partitions graphs into equivalence classes of structurally identical graphs.

15.5 Preserved Quantities

Any graph invariant is preserved under isomorphism.

G\cong H,

then:

Quantity	Preserved?
Number of vertices	Yes
Number of edges	Yes
Degree sequence	Yes
Number of components	Yes
Diameter	Yes
Girth	Yes
Chromatic number	Yes
Clique number	Yes
Planarity	Yes
Bipartiteness	Yes

Thus invariants are necessary conditions for isomorphism.

However, equality of invariants is usually not sufficient.

15.6 Adjacency Matrix View

Two graphs are isomorphic if and only if their adjacency matrices differ only by simultaneous permutation of rows and columns.

Let

A(G)

and

A(H)

be adjacency matrices.

G\cong H,

then there exists a permutation matrix $P$ such that

A(H)=P^{-1}A(G)P.

The permutation matrix reorders the vertices.

Thus isomorphism corresponds to relabeling rows and columns consistently. This matrix characterization is standard in algebraic graph theory. (mathworld.wolfram.com)

15.7 Automorphisms

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

Thus an automorphism is a permutation of the vertices that preserves adjacency.

The set of automorphisms of $G$ forms a group under composition, called the automorphism group of $G$ .

Automorphisms describe graph symmetries.

For example:

Graph	Automorphism behavior
$K_n$	Any vertex permutation works
Cycle $C_n$	Rotations and reflections
Path $P_n$	Reflection symmetry only
Generic asymmetric graph	Identity only

Automorphisms connect graph theory with group theory and symmetry.

15.8 Labeled and Unlabeled Graphs

A labeled graph treats vertex names as meaningful.

An unlabeled graph treats only structure as meaningful.

Two labeled graphs may be different as labeled objects even when they are isomorphic as unlabeled graphs.

For example:

Graph A: a-b-c
Graph B: 1-2-3

These are different labeled graphs but the same unlabeled graph structure.

Enumeration problems often distinguish between labeled and unlabeled counting.

15.9 Canonical Forms

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

If two graphs have the same canonical form, they are isomorphic.

For example, one may reorder vertices according to a deterministic rule and choose the lexicographically smallest adjacency matrix among all labelings.

Canonical forms are important in:

Area	Use
Chemical graph theory	Molecule comparison
Databases	Duplicate structure detection
Model checking	State compression
Network analysis	Pattern matching

Efficient canonicalization is closely related to the graph isomorphism problem.

15.10 The Graph Isomorphism Problem

The graph isomorphism problem asks:

Given graphs $G$ and $H$ , determine whether
$> G\cong H. >$

This is one of the major computational problems in discrete mathematics and theoretical computer science.

No polynomial-time algorithm is known for the general problem, but the problem is also not known to be NP-complete. In 2015, László Babai announced a quasipolynomial-time algorithm for graph isomorphism. (en.wikipedia.org)

Many important graph classes admit efficient isomorphism algorithms, including:

Graph class	Complexity
Trees	Polynomial time
Planar graphs	Polynomial time
Graphs of bounded degree	Polynomial time
General graphs	Quasipolynomial known

The graph isomorphism problem sits in a special position in complexity theory.

15.11 Isomorphism of Trees

Trees have particularly structured isomorphism behavior.

Two rooted trees are isomorphic if there exists a root-preserving adjacency-preserving bijection.

Tree isomorphism can be solved efficiently by recursively comparing subtree structure.

For example, two rooted trees are isomorphic when:

Their roots have the same number of children.
Corresponding child subtrees are recursively isomorphic.

Tree isomorphism algorithms are much easier than general graph isomorphism because trees contain no cycles.

15.12 Isomorphic Subgraphs

A graph $G$ contains a copy of a graph $H$ if some subgraph of $G$ is isomorphic to $H$ .

For example, $G$ contains a triangle if it contains a subgraph isomorphic to

K_3.

Subgraph isomorphism differs from graph isomorphism.

Problem	Question
Graph isomorphism	Are the entire graphs structurally identical?
Subgraph isomorphism	Does one graph contain a copy of the other?

Subgraph isomorphism is generally harder computationally.

15.13 Isomorphism and Complements

Complementation preserves isomorphism.

G\cong H,

then

\overline{G}\cong \overline{H}.

An adjacency-preserving bijection automatically preserves non-adjacency.

Thus complement graphs belong to corresponding isomorphism classes.

15.14 Self-Isomorphic Structures

Some graphs are isomorphic to their own complement.

Such graphs are called self-complementary.

Examples include:

Graph	Self-complementary?
$P_4$	Yes
$C_5$	Yes
$K_n$	No for $n>1$
Empty graph	No for $n>1$

Self-complementary graphs illustrate how different-looking adjacency descriptions can encode the same structure after relabeling.

15.15 Counting Non-Isomorphic Graphs

The number of unlabeled graphs on $n$ vertices is the number of isomorphism classes of labeled graphs.

For small $n$ :

$n$	Number of non-isomorphic simple graphs
1	1
2	2
3	4
4	11
5	34

The number grows rapidly.

Counting unlabeled graphs is substantially harder than counting labeled graphs because one must factor out isomorphisms.

15.16 Distinguishing Graphs

To test whether two graphs are isomorphic, one typically proceeds through increasingly refined invariants.

Common checks include:

Compare order.
Compare size.
Compare degree sequence.
Compare component structure.
Compare cycle counts.
Compare spectra.
Attempt explicit bijection construction.

Failure at any step proves non-isomorphism.

Agreement does not prove isomorphism unless a full adjacency-preserving bijection is found.

15.17 Example

Let

G

have vertices

\{a,b,c,d\}

and edges

\{\{a,b\},\{b,c\},\{c,d\},\{d,a\}\}.

Let

H

have vertices

\{1,2,3,4\}

and edges

\{\{1,2\},\{2,4\},\{4,3\},\{3,1\}\}.

Both graphs are cycles of length $4$ .

Define

f(a)=1, \qquad f(b)=2, \qquad f(c)=4, \qquad f(d)=3.

Then:

\{a,b\}\mapsto \{1,2\},

\{b,c\}\mapsto \{2,4\},

\{c,d\}\mapsto \{4,3\},

\{d,a\}\mapsto \{3,1\}.

All adjacencies are preserved.

Therefore

G\cong H.

The drawings may look different, but the graphs have identical cycle structure.

15.18 Example of Non-Isomorphism

Let $G$ and $H$ both have:

|V|=6, \qquad |E|=6.

Suppose:

$G=C_6$ .
$H=C_3\cup C_3$ .

Both graphs have degree sequence

(2,2,2,2,2,2).

However:

c(G)=1, \qquad c(H)=2.

Since the number of connected components differs,

G\not\cong H.

This example shows that several invariants may agree before one finally distinguishes the graphs.

15.19 Summary

Graph isomorphism formalizes structural equality of graphs. Two graphs are isomorphic when there exists a bijection between their vertex sets that preserves adjacency.

Isomorphism is an equivalence relation. Graph invariants are preserved under isomorphism and are useful for disproving isomorphism. However, equal invariants generally do not prove isomorphism.

Automorphisms describe graph symmetries. Canonical forms attempt to represent each isomorphism class uniquely. The graph isomorphism problem asks whether two graphs are structurally identical and remains one of the central algorithmic problems in graph theory and theoretical computer science.