Course contentsShow
← Computer Science
Lesson 668 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Graph Isomorphism

Learn when two graphs are considered structurally identical despite different vertex/edge labeling.

Graph Isomorphism

What you'll learn: You'll understand when two graphs are considered structurally identical even when their vertices and edges have different labels or are drawn differently.

The Core Idea

Imagine you have two social networks from different countries. The people have different names and the friendships are listed differently, but the pattern of connections is exactly the same. That's graph isomorphism—two graphs that are structurally identical despite different labeling or visual representation.

Two graphs G₁ and G₂ are isomorphic if there exists a one-to-one correspondence (mapping) between their vertices that preserves all edge connections. In other words, if vertex u connects to vertex v in G₁, then the corresponding vertices in G₂ must also be connected.

What Makes Graphs Isomorphic?

For graphs to be isomorphic, they must have:

  • The same number of vertices
  • The same number of edges
  • The same degree sequence (list of vertex degrees in sorted order)
  • Preservation of adjacency relationships through the mapping

However, having these properties doesn't guarantee isomorphism—they're necessary but not sufficient conditions.

Why It Matters

Graph isomorphism helps us recognize when two seemingly different graphs represent the same structure. This is crucial in:

  • Pattern recognition and matching
  • Chemical compound analysis (molecules with same structure)
  • Network comparison and social network analysis
  • Circuit design verification

Visual Example

Think of two triangles: one labeled A-B-C with edges A↔B, B↔C, C↔A, and another labeled 1-2-3 with edges 1↔2, 2↔3, 3↔1. These are isomorphic because the mapping (A→1, B→2, C→3) preserves all connections—both form complete 3-vertex graphs.

Key Takeaway: Two graphs are isomorphic if you can relabel one graph's vertices to exactly match the other's structure, preserving all edge connections.