Isomorphism — Definition, Formula & Examples

Isomorphism is a structure-preserving mapping between two mathematical objects that shows they are essentially the same in form, even if they look different. Two objects are called isomorphic if such a mapping exists between them.

An isomorphism is a bijective (one-to-one and onto) map $f: A \to B$ between two structures such that $f$ and its inverse $f^{-1}$ both preserve the relevant structural relations. In graph theory, graphs $G$ and $H$ are isomorphic if there exists a bijection $f: V(G) \to V(H)$ such that vertices $u$ and $v$ are adjacent in $G$ if and only if $f(u)$ and $f(v)$ are adjacent in $H$ .

How It Works

To check whether two graphs are isomorphic, first verify they share basic invariants: same number of vertices, same number of edges, and matching degree sequences. If these match, attempt to construct a bijection between vertex sets that preserves all adjacencies. If any invariant differs, the graphs cannot be isomorphic. Finding an explicit isomorphism for large graphs is computationally hard, so invariants serve as efficient filters.

Worked Example

Problem: Determine whether graph G with vertices {1, 2, 3} and edges {(1,2), (2,3), (1,3)} is isomorphic to graph H with vertices {a, b, c} and edges {(a,c), (b,c), (a,b)}.

Check invariants: Both graphs have 3 vertices and 3 edges. The degree sequence of G is (2, 2, 2) and the degree sequence of H is also (2, 2, 2). The invariants match, so an isomorphism may exist.

Construct a bijection: Define f(1) = a, f(2) = b, f(3) = c. Check adjacency preservation: (1,2) maps to (a,b) which is an edge in H; (2,3) maps to (b,c) which is an edge in H; (1,3) maps to (a,c) which is an edge in H.

f: 1 \mapsto a,\; 2 \mapsto b,\; 3 \mapsto c

Verify bijectivity: The map f is one-to-one (no two vertices in G map to the same vertex in H) and onto (every vertex in H is the image of some vertex in G).

Answer: Yes, G and H are isomorphic via the mapping f(1) = a, f(2) = b, f(3) = c.

Why It Matters

Isomorphism lets you recognize when two seemingly different structures are fundamentally identical, which is central to classifying groups in abstract algebra and identifying equivalent networks in computer science. Graph isomorphism testing appears in chemistry (comparing molecular structures), circuit design, and network analysis.

Common Mistakes

Mistake: Concluding two graphs are isomorphic just because they share the same number of vertices, edges, and degree sequence.

Correction: Matching invariants are necessary but not sufficient. Non-isomorphic graphs can share all common invariants. You must construct an explicit bijection or use deeper invariants to confirm isomorphism.