Skip to content

Chapter 10: Isomorphism, Subgraphs, Special Graphs

(TB1 Ch.5, Article 2)

1. Graph Isomorphism

Definition

Two graphs (G_1 = (V_1, E_1)) and (G_2 = (V_2, E_2)) are isomorphic if there exists a one-to-one correspondence (f: V_1 \to V_2) such that:

[ (u,v) \in E_1 \iff (f(u), f(v)) \in E_2 ]

  • Essentially, same structure, possibly with different vertex labels.
  • Isomorphism preserves adjacency.

Example 1

[ G_1: V = {1,2,3}, E = {(1,2),(2,3),(3,1)} G_2: V = {A,B,C}, E = {(A,B),(B,C),(C,A)} ]

  • Mapping: (1 \to A, 2 \to B, 3 \to C)
  • Both graphs are triangles → isomorphic

Properties of Isomorphic Graphs

  1. Same number of vertices ((|V_1| = |V_2|))
  2. Same number of edges ((|E_1| = |E_2|))
  3. Same degree sequence
  4. Same number of components

Exam Tip

  • Compare degree sequences first; if different → not isomorphic
  • Check adjacency preservation

2. Subgraphs

Definition

A subgraph (H = (V_H, E_H)) of a graph (G = (V, E)) satisfies:

[ V_H \subseteq V, \quad E_H \subseteq E ]

  • A subgraph inherits edges from the original graph
  • Induced subgraph: contains all edges of G that connect vertices in (V_H)

Example 2

[ G: V = {1,2,3,4}, E = {(1,2),(2,3),(3,4),(1,4)} ]

  • Subgraph (H: V_H = {1,2,3}, E_H = {(1,2),(2,3)})
  • Induced subgraph on ({1,2,3}) → edges {(1,2),(2,3)}

Special Cases

  • Spanning subgraph: Contains all vertices of G
  • Proper subgraph: H ≠ G

3. Special Graphs

(a) Complete Graph (K_n)

  • Every vertex is connected to every other vertex
  • Edges: (|E| = \frac{n(n-1)}{2})

(b) Cycle Graph (C_n)

  • Forms a closed loop of n vertices
  • Degree of each vertex = 2

(c) Path Graph (P_n)

  • Vertices connected in a line
  • Two endpoints of degree 1, others degree 2

(d) Bipartite Graph

  • Vertices partitioned into sets (U, V)
  • Edges connect vertices only from U to V
  • No edge within same set

(e) Complete Bipartite Graph (K_{m,n})

  • Every vertex in U connected to every vertex in V
  • Edges = (m \times n)

(f) Star Graph

  • Complete bipartite graph (K_{1,n})
  • One central vertex connected to n vertices

(g) Wheel Graph (W_n)

  • Cycle (C_{n-1}) with an extra central vertex connected to all vertices of the cycle

4. Graph Representation Recap

  • Adjacency matrix → useful for checking edges
  • Adjacency list → memory efficient for sparse graphs
  • Drawing diagrams → essential for spotting isomorphism or subgraphs

5. Applications in Computer Science

  • Pattern recognition (graph matching)
  • Network design (subnetwork analysis)
  • Compiler optimization (control flow graphs)
  • Database query optimization (isomorphic schemas)

Comments