Isomorphism

Definition of Graph Isomorphism

Two graphs $G$ and $H$ are called $\text{isomorphic}$ if there exists a one-to-one correspondence between their vertices that makes them “structurally identical.”

In other words, although the vertex labels may differ, the connectivity pattern is the same. Isomorphism captures the idea that $G$ and $H$ have the same shape as abstract graphs, even if they look different at first glance.

Studying isomorphic graphs allows us to classify graphs by their underlying structure, ignoring superficial differences in labeling or drawing style.

Figure 1. Isomorphic graphs.

$\mathbf{\text{Example}}$
Consider two triangles: one with vertices labeled $\{a,b,c\}$ and another with $\{x,y,z\}$. They are isomorphic because each vertex in the first can be matched to a vertex in the second so that edges correspond.

$\mathbf{\text{Metaphor}}$
Graph isomorphism is like having two jigsaw puzzles with different artwork on the pieces but the same shapes—they fit together in exactly the same way.

Bijection and Edge Preservation

The core of graph isomorphism is a $\text{bijection}$ $f:V(G)\to V(H)$ that preserves $\text{edges}$ in both directions.

This means for any two vertices $u,v\in V(G)$ we have

Thus, if $u$ and $v$ are adjacent in $G$, their images under $f$ are adjacent in $H$, and vice versa.

Edge preservation guarantees that the bijection does not create or destroy connections, maintaining the exact adjacency relationships between vertices.

Figure 2. Isomorphic graphs with different vertex labels.

$\mathbf{\text{Example}}$
If $G$ has edge $ab$ and our bijection sends $a\mapsto x$, $b\mapsto y$, then $xy$ must be an edge in $H$.

$\mathbf{\text{Metaphor}}$
A bijection preserving edges is like renaming streets on a map—every intersection and road remains the same, only the names change.

Notation and Equivalence

We denote graph isomorphism by

This symbol indicates that $G$ and $H$ belong to the same equivalence class under the isomorphism relation.
Indeed, $\text{isomorphism}$ is an equivalence relation on the set of all graphs, satisfying reflexivity, symmetry, and transitivity.

• Reflexivity: every graph is isomorphic to itself via the identity map.
• Symmetry: if $G\cong H$ via $f$, then $H\cong G$ via $f^{-1}$.
• Transitivity: if $G\cong H$ and $H\cong K$, then $G\cong K$ by composing bijections.

$\mathbf{\text{Example}}$
If $G\cong H$ and $H\cong K$, you can chain the bijections to get an isomorphism from $G$ to $K$.

$\mathbf{\text{Metaphor}}$
Treating isomorphic graphs as equivalent is like considering two languages interchangeable if there is a perfect translation both ways—meaning anything said in one can be faithfully conveyed in the other.

Conclusion

Graph isomorphism identifies when two graphs share the same structure up to relabeling of vertices. It relies on a bijection that preserves adjacency exactly. The notation $G\cong H$ captures this equivalence relation, grouping graphs into classes of structurally identical networks. Understanding isomorphism is fundamental for classification, enumeration, and symmetry analysis in graph theory.