9.2 Graph Representations, Subgraphs & Graph Isomorphism Invariants

Back to Discrete Mathematics Notes

📚Module 09: Graph Theory Foundations, Paths & ConnectivityTopic 9.2: Representations & Isomorphism⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Spreadsheets vs Contact Books & Identical Floor Plans

Think of graph representation and isomorphism like organizing contact lists and recognizing twin architectural blueprints:

1. Adjacency Matrix (The Full 2D Grid Table): An $n \times n$ spreadsheet with all people on both rows and columns. Cell $(i, j) = 1$ if they are friends; $0$ if not. You can instantaneously verify whether any two people know each other ($O(1)$ time), but it wastes memory storing zeros if people only have a few friends ($O(V^2)$ space).
2. Adjacency List (The Mobile Contact Book): Each person only stores the names and numbers of their actual friends. Sparse, compact, and uses memory strictly proportional to real connections ($O(V + E)$).
3. Graph Isomorphism (Same House, Different Blueprint Orientation): Imagine two architects drawing blueprints of the exact same house. Architect 1 numbers the rooms 1 to 4; Architect 2 numbers them $a$ to $d$ and rotates the drawing 90 degrees. The drawings look completely different at first glance, but if room 1 connects to 2 and 3, and room $a$ connects to $b$ and $c$ with identical relational connectivity, the two houses are isomorphic!

💻 Bridging to Computer Science: Traversal Engines, Matrix Multiplications & GI Complexity

In computer systems:

• Graph Traversal (BFS / DFS / Dijkstra): Production graph algorithms use adjacency lists to achieve optimal linear $O(V + E)$ execution.
• Walk Counting via Matrix Multiplication: In distributed systems and Markov chains, $(A^k)_{i, j}$ calculates the exact number of packet routes of length $k$ between network routers using matrix powers.
• The Graph Isomorphism (GI) Complexity Class: Unlike most problems which are either in $P$ or $NP$-complete, Graph Isomorphism is one of the celebrated problems suspected to be NP-Intermediate (solved in quasipolynomial time by László Babai in 2015).

📑Table of Contents

• 💾 Graph Representations: Matrix vs List
  • Incidence Matrix Formalism
  • Structural Invariants of the Incidence Matrix:
• 🧮 Multi-Hop Walk Counting & Matrix Trace Theorems
• 🧩 Subgraphs: Spanning, Vertex-Induced & Edge-Induced
• 🪞 Graph Isomorphism: Structural Equivalence
• 📝 Step-by-Step Worked Examples
  • Example 1: Counting Multi-Hop Walks via Matrix Powers
  • Example 2: Proving Graph Isomorphism with Bijection Construction
• 🎯 Exam & Interview Pitfall Check

---

💾 Graph Representations: Matrix vs List

Adjacency Matrix vs Adjacency List

The fundamental architectural trade-off between dense random access and sparse memory efficiency

Adjacency Matrix

Adjacency Matrix A

📋

Dominant Architecture / DomainDense Graph Optimization

• •Structure: An n × n binary matrix where A[i][j] = 1 if {vᵢ, vⱼ} ∈ E, else 0.
• •Space Complexity: O(V²) fixed memory regardless of edge density.
• •Edge Query Time: O(1) instantaneous lookup (A[u][v] == 1).
• •Row Sum: Sum of row i equals deg(vᵢ); total entries sum to 2|E|.
• •Algebraic Power: Matrix powers Aᵏ count multi-hop walks!

"Dense 2D grid ideal when |E| ≈ |V|²."

Adjacency List

Adjacency List

📜

Dominant Architecture / DomainSparse Graph Optimization

• •Structure: Array of V linked lists or vectors storing adjacent neighbors.
• •Space Complexity: O(V + E) compact memory footprint.
• •Edge Query Time: O(deg(u)) requires scanning neighbor list.
• •Traversal Standard: Native format for BFS, DFS, Dijkstra, and Tarjan.
• •Iteration: Scanning all incident edges takes optimal O(deg(v)) time.

"Linear space ideal for real-world sparse graphs where |E| ≪ |V|²."

Incidence Matrix Formalism

📖Definition 9.1: The Incidence Matrix Mdefinition

Let $G = (V, E)$ be an undirected graph with $n$ vertices $\{v_1, \dots, v_n\}$ and $m$ edges $\{e_1, \dots, e_m\}$: The Incidence Matrix $M$ is an $n \times m$ matrix defined as:

$$M_{i, j} = \begin{cases} 1 & \text{if vertex } v_i \text{ is incident with edge } e_j \\ 0 & \text{otherwise} \end{cases}$$

Structural Invariants of the Incidence Matrix:

1. Column Sum Invariant: Every edge connects exactly two vertices. Therefore, every column of $M$ contains exactly two 1s, and the sum of each column is always $2$: $$\sum_{i=1}^{n} M_{i, j} = 2 \quad (\forall j)$$
2. Row Sum Invariant: The sum of row $i$ equals the degree of vertex $v_i$: $$\sum_{j=1}^{m} M_{i, j} = \deg(v_i)$$
3. Total Sum: Summing all elements in $M$ yields $2m = 2|E|$.

---

🧮 Multi-Hop Walk Counting & Matrix Trace Theorems

📐Theorem 9.1: Walk Counting via Matrix Powerstheorem

Let $A$ be the adjacency matrix of a simple graph $G$ with vertices $\{v_1, v_2, \dots, v_n\}$. For any positive integer $k \ge 1$, the $(i, j)$-th entry of the $k$-th power matrix $A^k$:

$$(A^k)_{i, j}$$

equals the exact number of distinct walks of length $k$ from vertex $v_i$ to vertex $v_j$!

Proof by Induction on $k$:

• Base Case ($k = 1$): $A^1 = A$. By definition, $A_{i, j} = 1$ if there is an edge (a walk of length 1) from $v_i$ to $v_j$, and $0$ otherwise. Holds!
• Inductive Step: Assume $(A^k)_{i, j}$ counts walks of length $k$. Any walk of length $k + 1$ from $v_i$ to $v_j$ consists of a walk of length $k$ from $v_i$ to an intermediate neighbor $v_m$, followed by a single edge from $v_m$ to $v_j$. By matrix multiplication: $$(A^{k+1})_{i, j} = \sum_{m=1}^{n} (A^k)_{i, m} \cdot A_{m, j}$$ Summing over all possible intermediate bridges $v_m$ gives the total number of walks of length $k + 1$.

📐Theorem 9.2: Trace Invariants for Edges and Trianglestheorem

Let $A$ be the adjacency matrix of a simple graph $G$. The trace $\text{Tr}(M)$ is the sum of diagonal elements $\sum M_{i, i}$.

1. Trace of $A^2$ (Total Edges): The diagonal entry $(A^2)_{i, i}$ represents walks of length 2 from $v_i$ to itself ($v_i \to v_j \to v_i$), which equals $\deg(v_i)$. Therefore: $$\text{Tr}(A^2) = \sum_{i=1}^{n} (A^2)_{i, i} = \sum_{i=1}^{n} \deg(v_i) = 2 |E|$$
2. Trace of $A^3$ (Triangle Counting): The diagonal entry $(A^3)_{i, i}$ represents closed walks of length 3 starting and ending at $v_i$ ($v_i \to v_j \to v_k \to v_i$). In a simple graph, any closed walk of length 3 is a triangle ($C_3$).
   • Each triangle $\{u, v, w\}$ can start at 3 different vertices.
   • For each starting vertex, the triangle can be traversed in 2 cyclic directions (clockwise and counterclockwise).
   • Thus, each single triangle contributes $3 \times 2 = 6$ closed walks to $\text{Tr}(A^3)$!
   $$\text{Number of Triangles } (C_3) = \frac{1}{6} \text{Tr}(A^3) = \frac{1}{6} \sum_{i=1}^{n} (A^3)_{i, i}$$

---

🧩 Subgraphs: Spanning, Vertex-Induced & Edge-Induced

📖Definition 9.2: Subgraph Taxonomydefinition

Let $G = (V, E)$ be a graph:

1. Subgraph ($H \subseteq G$): A graph $H = (V', E')$ where $V' \subseteq V$ and $E' \subseteq E$ such that every edge in $E'$ has its endpoints in $V'$.
2. Spanning Subgraph: A subgraph $H$ that contains all vertices of $G$: $$V(H) = V(G) \quad \text{and} \quad E(H) \subseteq E(G)$$ (e.g., A Spanning Tree of $G$ is a spanning subgraph that is a tree).
3. Vertex-Induced Subgraph ($G[S]$): Given a subset of vertices $S \subseteq V$, the subgraph induced by $S$ has vertex set $S$ and contains ALL edges of $G$ whose endpoints both belong to $S$: $$E(G[S]) = \{ \{u, v\} \in E \mid u \in S \land v \in S \}$$
4. Edge-Induced Subgraph ($G[E']$): Given a subset of edges $E' \subseteq E$, the subgraph induced by $E'$ contains $E'$ and all vertices incident to at least one edge in $E'$.

---

🪞 Graph Isomorphism: Structural Equivalence

📖Definition 9.3: Graph Isomorphismdefinition

Two simple graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic (denoted $G_1 \cong G_2$) if there exists a bijective function:

$$f: V_1 \to V_2$$

such that for all pairs of vertices $u, v \in V_1$:

$$\{u, v\} \in E_1 \iff \{f(u), f(v)\} \in E_2$$

The mapping $f$ is called an isomorphism. It preserves adjacency, non-adjacency, and all structural graph invariants.

• Matrix Permutation Test: $G_1 \cong G_2$ if and only if there exists an $n \times n$ permutation matrix $P$ such that: $$A(G_2) = P \cdot A(G_1) \cdot P^T$$

✓ Isomorphic Invariants: |V|=4, |E|=5, Degrees: (3, 3, 2, 2)

Isomorphism Bijection: f(1)=a, f(2)=b, f(3)=c, f(4)=d preserves all 5 adjacency relations despite contrasting planar drawings.

Architecture Flow

The 5-Filter Graph Isomorphism Verification Pipeline

Systematic invariant checklist to prove or disprove structural equivalence

🔢Filter 1

Cardinality Invariants

Verify that |V₁| = |V₂| and |E₁| = |E₂|. If counts differ ⟹ NOT ISOMORPHIC!

→

Pass: Sizes Match

📊Filter 2

Degree Sequence Invariant

Sort degrees of both graphs. Degree sequences must be IDENTICAL. If sequences differ ⟹ NOT ISOMORPHIC!

→

Pass: Degrees Match

🔄Filter 3

Cycle & Subgraph Spectrum

Count cycles of length 3 (triangles), 4, 5... Girth and cycle counts must match identically in both graphs.

→

Pass: Cycles Match

🪞Filter 4

Complement Graph Invariant

If G₁ ≅ G₂, then their complements must also be isomorphic: Ḡ₁ ≅ Ḡ₂.

→

Pass: Complements Match

🎯Filter 5

Construct Bijective Mapping f

Map vertices with matching degrees and verify that every edge in G₁ corresponds to an edge in G₂.

---

📝 Step-by-Step Worked Examples

Example 1: Counting Multi-Hop Walks via Matrix Powers

Problem Statement: Consider a triangle graph $C_3$ with vertices $\{v_1, v_2, v_3\}$ and edges $\{\{1, 2\}, \{2, 3\}, \{1, 3\}\}$.

1. Construct the adjacency matrix $A$.
2. Compute $A^2$ and $A^3$.
3. How many walks of length 3 exist from vertex $v_1$ to itself ($v_1 \to v_1$)? Verify the Triangle Counting Theorem via $\text{Tr}(A^3)$.

Step-by-Step Solution:

1. Step 1: Construct Adjacency Matrix $A$

   $$A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$$

2. Step 2: Compute $A^2$ and $A^3$

   • Compute $A^2 = A \times A$: $$A^2 = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix}$$ (Interpretation: Entry $(1, 1) = 2$ means there are 2 walks of length 2 from $v_1$ to $v_1$: $v_1 \to v_2 \to v_1$ and $v_1 \to v_3 \to v_1$).
   • Compute $A^3 = A^2 \times A$: $$A^3 = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \end{pmatrix}$$

3. Step 3: Closed Walks & Triangle Verification

   • Number of walks of length 3 from $v_1$ to $v_1$: $(A^3)_{1, 1} = 2$.
   • The two walks are the two traversal directions around the triangle:
     1. $v_1 \to v_2 \to v_3 \to v_1$ (clockwise)
     2. $v_1 \to v_3 \to v_2 \to v_1$ (counter-clockwise)
   • Verifying the Triangle Trace Theorem: $$\text{Tr}(A^3) = (A^3)_{1, 1} + (A^3)_{2, 2} + (A^3)_{3, 3} = 2 + 2 + 2 = 6$$ $$\text{Total Triangles} = \frac{1}{6} \text{Tr}(A^3) = \frac{6}{6} = 1 \text{ triangle}$$
   • Matches the graph structure exactly!

Key Takeaway: $(A^k)_{i, j}$ counts walks, not simple paths. The trace $\text{Tr}(A^2) = 2|E|$, and $\frac{1}{6}\text{Tr}(A^3)$ calculates the exact number of triangles in the graph!

---

Example 2: Proving Graph Isomorphism with Bijection Construction

Problem Statement: Refer to the diagram above showing $G_1$ (vertices $\{1, 2, 3, 4\}$) and $G_2$ (vertices $\{a, b, c, d\}$).

• $E(G_1) = \{\{1, 2\}, \{1, 3\}, \{2, 4\}, \{3, 4\}, \{2, 3\}\}$
• $E(G_2) = \{\{b, c\}, \{b, a\}, \{c, d\}, \{b, d\}, \{c, a\}\}$ Prove that $G_1 \cong G_2$ by constructing an explicit isomorphism bijection $f$.

Step-by-Step Solution:

1. Step 1: Check Invariants

   • Vertices: $|V_1| = 4$, $|V_2| = 4$ (Match).
   • Edges: $|E_1| = 5$, $|E_2| = 5$ (Match).
   • Degree sequence in $G_1$: $\deg(2) = 3, \deg(3) = 3, \deg(1) = 2, \deg(4) = 2 \implies (3, 3, 2, 2)$.
   • Degree sequence in $G_2$: $\deg(b) = 3, \deg(c) = 3, \deg(a) = 2, \deg(d) = 2 \implies (3, 3, 2, 2)$.
   • Both graphs contain exactly 2 triangles ($K_3$) and 1 cycle of length 4 ($C_4$).

2. Step 2: Construct Candidate Bijective Mapping $f$

   • High-degree vertices ($\deg = 3$):
     • In $G_1$, $\{2, 3\}$ have degree 3 and are adjacent ($\{2, 3\} \in E_1$).
     • In $G_2$, $\{b, c\}$ have degree 3 and are adjacent ($\{b, c\} \in E_2$).
     • Set $f(2) = b$ and $f(3) = c$.
   • Lower-degree vertices ($\deg = 2$):
     • In $G_1$, vertex $1$ connects to $\{2, 3\}$.
     • In $G_2$, vertex $a$ connects to $\{b, c\}$.
     • Set $f(1) = a$.
     • In $G_1$, vertex $4$ connects to $\{2, 3\}$.
     • In $G_2$, vertex $d$ connects to $\{b, c\}$.
     • Set $f(4) = d$.

3. Step 3: Edge-Preservation Verification

   • $\{1, 2\} \in E_1 \iff \{f(1), f(2)\} = \{a, b\} \in E_2$ (Preserved).
   • $\{1, 3\} \in E_1 \iff \{f(1), f(3)\} = \{a, c\} \in E_2$ (Preserved).
   • $\{2, 3\} \in E_1 \iff \{f(2), f(3)\} = \{b, c\} \in E_2$ (Preserved).
   • $\{2, 4\} \in E_1 \iff \{f(2), f(4)\} = \{b, d\} \in E_2$ (Preserved).
   • $\{3, 4\} \in E_1 \iff \{f(3), f(4)\} = \{c, d\} \in E_2$ (Preserved).
   • Non-edges: $\{1, 4\} \notin E_1 \iff \{a, d\} \notin E_2$ (Preserved).

Conclusion: $f$ is a valid bijection preserving all adjacencies and non-adjacencies. Hence, $G_1 \cong G_2$.

Key Takeaway: To prove isomorphism, establish a candidate mapping between vertices of matching degrees and verify edge-by-edge that all connections are preserved.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: If two graphs have the exact same degree sequence, are they guaranteed to be isomorphic? Key Focus Points: No! Degree sequence equality is a necessary condition, but NOT a sufficient condition. Classic Counterexample:

• Graph $G_1$: Cycle of length 6 ($C_6$). Degree sequence is $(2, 2, 2, 2, 2, 2)$.
• Graph $G_2$: Two disjoint triangles ($2 C_3$). Degree sequence is also $(2, 2, 2, 2, 2, 2)$. Both graphs have $6$ vertices, $6$ edges, and identical degree sequences. However, $G_1$ is connected with girth 6, while $G_2$ is disconnected with 2 triangles. Hence, $G_1 \not\cong G_2$!

Question 2: How does the complement graph help prove or disprove graph isomorphism? Key Focus Points: Two graphs are isomorphic if and only if their complements are isomorphic:

$$G_1 \cong G_2 \iff \bar{G}_1 \cong \bar{G}_2$$

When analyzing dense graphs with many edges (e.g., $|E| \approx \binom{n}{2}$), inspecting the complement graphs $\bar{G}_1$ and $\bar{G}_2$ is vastly simpler because the complements have very few edges ($|E(\bar{G})| = \binom{n}{2} - |E(G)|$), making structural discrepancies instantly visible!

Common Interview Traps: Architectural Trade-Offs

Trap 1: Confusing walks with paths in matrix powers Why it fails: $(A^k)_{i, j}$ counts all walks of length $k$, NOT simple paths! A walk can revisit vertices and re-traverse edges (e.g., $v_1 \to v_2 \to v_1 \to v_2$). If an interview question asks for the number of simple paths, you cannot simply read off $(A^k)_{i, j}$.

Trap 2: Forgetting the 1/6 factor when counting triangles from Tr(A³) Why it fails: In $\text{Tr}(A^3)$, each triangle $\{u, v, w\}$ is counted 6 times (3 choices for the starting vertex $\times$ 2 traversal directions: clockwise and counter-clockwise). Forgetting the $\frac{1}{6}$ factor will overestimate the triangle count by $600\%$!

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic9.1 Graph Formalisms, Degree Sequences & the Handshaking LemmaNext Topic →9.3 Walks, Paths, Cycles, Connectivity & Cut-Vertex Invariants