Graph Isomorphism

Introduction

Two graphs may look different when drawn but actually have the same structure. Graph isomorphism helps us determine if two graphs are essentially the same.

Definition

Two graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) are isomorphic if there exists a bijection (one-to-one correspondence) f: V₁ → V₂ such that:

For any vertices u, v in V₁: {u, v} ∈ E₁ if and only if {f(u), f(v)} ∈ E₂

In simple terms: We can relabel the vertices of one graph to make it identical to the other.

Example 1: Isomorphic Graphs

Graph G₁:

A --- B
|     |
D --- C

Graph G₂:

1 --- 2
|     |
4 --- 3

Are they isomorphic?

YES! Mapping: A→1, B→2, C→3, D→4

Verification:

• Edge {A,B} maps to {1,2} ✓
• Edge {B,C} maps to {2,3} ✓
• Edge {C,D} maps to {3,4} ✓
• Edge {D,A} maps to {4,1} ✓

Example 2: Non-Isomorphic Graphs

Graph G₁:

A --- B --- C

Graph G₂:

  1
 / \
2---3

Are they isomorphic?

NO!

• G₁ has vertices with degrees: 1, 2, 1
• G₂ has vertices with degrees: 2, 2, 2
• Different degree sequences → cannot be isomorphic

Necessary Conditions for Isomorphism

If G₁ and G₂ are isomorphic, they MUST have:

1. Same number of vertices: |V₁| = |V₂|
2. Same number of edges: |E₁| = |E₂|
3. Same degree sequence
4. Same number of cycles of each length
5. Same connectivity

Important: These are necessary but NOT sufficient conditions!

Degree Sequence

Definition: List of all vertex degrees, typically in non-increasing order.

Example:

Graph:
1 --- 2
| \\ /|
|  X |
| / \\|
4 --- 3

Degrees: deg(1)=3, deg(2)=3, deg(3)=3, deg(4)=3 Degree sequence: (3, 3, 3, 3)

Invariants Under Isomorphism

Properties that are preserved:

1. Number of vertices
2. Number of edges
3. Degree sequence
4. Number of vertices of each degree
5. Number of cycles
6. Connectivity
7. Chromatic number
8. Diameter
9. Girth (length of shortest cycle)

Steps to Check Isomorphism

1. Check necessary conditions (vertices, edges, degree sequence)
2. Find potential vertex mappings based on degrees
3. Verify edge preservation for the mapping
4. Check all edges map correctly

Example 3: Detailed Verification

Graph G₁:

A --- B
|  ×  |
C --- D

Edges: {A,B}, {A,C}, {B,D}, {C,D}, {A,D}, {B,C}

Graph G₂:

1 --- 2
|  ×  |
3 --- 4

Edges: {1,2}, {1,3}, {2,4}, {3,4}, {1,4}, {2,3}

Step 1: Check basic properties

• Vertices: 4 = 4 ✓
• Edges: 6 = 6 ✓
• All degrees = 3 ✓

Step 2: Try mapping A→1, B→2, C→3, D→4

Step 3: Verify edges:

• {A,B} → {1,2} ✓
• {A,C} → {1,3} ✓
• {B,D} → {2,4} ✓
• {C,D} → {3,4} ✓
• {A,D} → {1,4} ✓
• {B,C} → {2,3} ✓

Result: Isomorphic!

Example 4: Proving Non-Isomorphism

Graph G₁:

A --- B --- C
      |
      D

Graph G₂:

1 --- 2
|     |
4 --- 3

Step 1: Check degrees

• G₁: (3, 2, 1, 1) - one vertex degree 3
• G₂: (2, 2, 2, 2) - all vertices degree 2

Result: NOT isomorphic (different degree sequences)

Example 5: Same Degrees, Still Different

Graph G₁:

A --- B --- C
|           |
D-----------+

Graph G₂:

1 --- 2
|     |
3 --- 4

Degrees:

• G₁: (2, 2, 2, 2)
• G₂: (2, 2, 2, 2) ✓

But check cycles:

• G₁: One cycle of length 4
• G₂: One cycle of length 4 ✓

Try mapping: Various attempts fail to preserve all edges

Verification shows: NOT isomorphic (despite same degree sequence)

Special Cases

Complete Graphs

All complete graphs Kₙ with same n are isomorphic.

Example: Any two drawings of K₄ are isomorphic.

Cycle Graphs

All cycle graphs Cₙ with same n are isomorphic.

Example: Any two pentagons are isomorphic.

Trees

Trees with same degree sequence may or may not be isomorphic.

Isomorphism Classes

An isomorphism class is a set of all graphs isomorphic to each other.

Example: All graphs with 2 vertices and 1 edge form one isomorphism class.

Automorphism

An automorphism is an isomorphism from a graph to itself.

Example: K₄ has 24 automorphisms (4! = 24 ways to relabel)

The Graph Isomorphism Problem

Question: Given two graphs, determine if they are isomorphic.

Complexity:

• No known polynomial-time algorithm
• Not proven to be NP-complete
• Quasi-polynomial algorithm exists (2015, Babai)
• One of the most interesting open problems

Practical Applications

1. Chemistry: Molecular structure comparison
2. Pattern recognition: Image matching
3. Computer vision: Object recognition
4. Network analysis: Comparing network structures
5. Social networks: Finding similar communities
6. Bioinformatics: Protein structure comparison

Common Mistakes to Avoid

1. Same degree sequence ≠ isomorphic
2. Visual similarity ≠ isomorphic
3. Must verify ALL edges map correctly
4. Necessary conditions don’t guarantee isomorphism

Key Points for Exams

1. Isomorphism: bijection preserving edge relationships
2. Necessary conditions: same |V|, |E|, degree sequence
3. Degree sequence: list of vertex degrees
4. Same degrees ≠ isomorphic (not sufficient)
5. Verify edge mapping for all edges
6. All Kₙ graphs are isomorphic to each other
7. All Cₙ graphs are isomorphic to each other
8. Invariants: properties preserved under isomorphism
9. Automorphism: isomorphism to itself
10. Graph isomorphism problem: no known polynomial algorithm

Practice Problems

1. Are these isomorphic? G₁: Triangle, G₂: Path of length 2

2. Check if K₃ and C₃ are isomorphic

3. Two graphs have degree sequences (3,2,2,1) and (2,2,2,2). Can they be isomorphic?

4. Draw all non-isomorphic graphs with 3 vertices

5. Find an isomorphism between two squares drawn differently

6. How many automorphisms does a square (C₄) have?

7. Are all trees with 5 vertices isomorphic? Explain.

8. Given degree sequence (2,2,2,2,2,2), how many non-isomorphic graphs?

9. Prove two complete graphs K₅ are always isomorphic

10. Can two graphs with different numbers of triangles be isomorphic?