← Back to Examples

Graph Isomorphism Explained

Like comparing building blueprints - same structure, different labels!

Graph Isomorphism determines if two graphs have identical structure. Two graphs are isomorphic if you can relabel the nodes of one graph to perfectly match the other graph's connections.

Choose Test Scenario:

Graph A

Graph B

0
Nodes A
0
Nodes B
0
Edges A
0
Edges B
?
Isomorphic

Isomorphism Result

Node Mapping (Graph A → Graph B):

Click "Check Isomorphism" to test if the graphs have identical structure
Unvisited
Exploring
Candidate
Mapped
Rejected
1.5s

Key Concept:

Graph Isomorphism uses the VF2 algorithm to systematically test all possible node mappings:

1. Initial checks: Same number of nodes, edges, and degree sequence

2. Recursive mapping: Try to map each node while preserving all connections

3. Backtracking: If a mapping fails, try different combinations

Two graphs are isomorphic if there exists a bijection (one-to-one mapping) between their nodes that preserves all edge relationships. This is a fundamental problem in graph theory with applications in chemistry, pattern recognition, and network analysis!

Code Example

Loading code...