Skip to main content

Graph Representations, Isomorphism, and Matrix Viewpoints

What This Concept Is​

The same graph can be represented in several physical forms, each with different strengths:

  • drawing -- a diagram with vertices as dots and edges as curves. Good for intuition; dangerous for proofs because the same graph admits infinitely many drawings.
  • edge list -- $E = { {u_1, v_1}, {u_2, v_2}, \ldots }$. Compact for sparse graphs; fast to stream; slow to query "is $u$ adjacent to $v$?"
  • adjacency list -- each vertex $v$ stores a list (or set) of its neighbors. Standard for most algorithmic work on sparse graphs. Query "are $u, v$ adjacent?" is $O(\deg(u))$ or $O(1)$ with a hash set.
  • adjacency matrix $A \in {0, 1}^{|V| \times |V|}$ -- $A_{ij} = 1$ iff $ij \in E$. $O(1)$ edge queries; $O(|V|^2)$ memory whether the graph is sparse or dense.

Two graphs $G$ and $H$ are isomorphic (written $G \cong H$) if there exists a bijection $f: V(G) \to V(H)$ preserving adjacency: $uv \in E(G) \iff f(u)f(v) \in E(H)$. Isomorphism is the formal statement that graphs are the same structure up to relabeling of vertices.

The adjacency matrix bridges discrete graph structure and linear algebra. Its powers, eigenvalues, and spectral decomposition encode surprising amounts of structural information:

  • $(A^k)_{ij}$ counts walks of length $k$ from $i$ to $j$.
  • Eigenvalues of $A$ govern expansion, mixing time of random walks, and chromatic-number bounds.
  • $\operatorname{tr}(A^3) / 6$ = number of triangles (for simple graphs).

Why It Matters Here​

Representation matters because different questions become easier in different forms:

  • adjacency lists are good for sparse exploration (BFS/DFS)
  • adjacency matrices reveal walk-count structure and enable spectral reasoning
  • isomorphism reminds you that labels are not structure; any property worth naming is invariant under relabeling

This is one of the first places where discrete combinatorics and computation visibly interact. Isomorphism also introduces a deep computational question: the graph isomorphism problem is not known to be in $P$ nor known to be $NP$-complete -- it sits in a rare intermediate complexity class. Practical testing uses invariants (degree sequence, cycle spectrum) to quickly rule out isomorphism, falling back to more expensive search only when invariants match.

Concrete Examples​

Example 1: walk counts via $A^2$. Let $G = P_4$ (path on $4$ vertices: $1 - 2 - 3 - 4$). Its adjacency matrix is

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

Compute $A^2$:

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

The entry $(A^2){22} = 2$ tells us there are $2$ walks of length $2$ starting and ending at vertex $2$: go to $1$ and back, or go to $3$ and back. ✓ The entry $(A^2){13} = 1$ says one walk from $1$ to $3$ of length $2$: $1 \to 2 \to 3$.

Example 2: isomorphism invariants. Consider two graphs on $4$ vertices:

  • $G$: ${ {1,2}, {2,3}, {3,4}, {4,1} }$ -- a $4$-cycle $C_4$.
  • $H$: ${ {a,b}, {a,c}, {a,d}, {b,c} }$.

Degree sequences: $G$ has $(2,2,2,2)$; $H$ has $(3, 2, 2, 1)$. Different degree sequences immediately prove they are not isomorphic. We never need to search for a bijection.

Now consider $C_6$ (cycle on $6$ vertices) versus the graph $K_{3,3}$. Both have $6$ vertices and both are $2$-regular... wait, $K_{3,3}$ is $3$-regular, not $2$-regular -- so they differ in degree sequence. A cleaner pair: $C_6$ vs. two disjoint triangles ($C_3 + C_3$). Both have $(2,2,2,2,2,2)$ degree sequence, but $C_6$ is connected and $C_3 + C_3$ is not. Connectedness is another invariant that rules out isomorphism.

Example 3: invariants do not suffice. The pair of graphs below have identical degree sequences, cycle counts, and component counts, yet are not isomorphic. (Strongly regular graph pairs like the shrikhande and the $4 \times 4$ rook graph are the canonical example: both are $6$-regular on $16$ vertices with the same small-cycle counts, but they differ in subtle structural invariants visible only to more detailed analyses.) Equal invariants are necessary evidence, not sufficient proof.

Common Confusion / Misconceptions​

  • Different labels = different graphs. Wrong. Graph structure ignores vertex names. If I draw $K_4$ with vertices labeled ${1, 2, 3, 4}$ and you draw it with ${A, B, C, D}$, those are isomorphic -- the same graph.
  • Same degree sequence $\Rightarrow$ isomorphic. Wrong. Equal degree sequences are a necessary invariant, not a sufficient one. Many non-isomorphic pairs share degree sequences.
  • The picture determines the graph. Two pictures of the same graph can look wildly different (e.g., $K_4$ drawn planar vs. with crossings).
  • Adjacency matrix is canonical. Wrong. The matrix depends on the labeling order of vertices; isomorphic graphs have adjacency matrices related by a permutation matrix: $A_G = P^T A_H P$ for some permutation $P$. Canonical forms (e.g., lexicographically smallest under relabeling) are a hard problem -- the crux of the graph isomorphism problem.

How To Use It​

Ask, in order:

  1. Do I need a computation-friendly form or a proof-friendly form? (Sparse BFS argues for adjacency lists; spectral proofs argue for matrices.)
  2. Is the question label-sensitive or structure-sensitive? If the latter, all arguments should be invariant under relabeling.
  3. Would matrix powers reveal walk information faster than manual enumeration? ($A^k$ is $O(n^\omega \log k)$; manual walk enumeration is exponential.)
  4. Can I rule out isomorphism by a cheap invariant before attempting a bijection search?
  5. Am I silently assuming the graph is simple / undirected / connected? State assumptions.

Common invariants (cheap to compute, powerful for ruling out isomorphism):

  • number of vertices
  • number of edges
  • degree sequence (sorted)
  • number of connected components
  • counts of short cycles (triangles $= \operatorname{tr}(A^3)/6$, $4$-cycles derivable similarly)
  • eigenvalues of the adjacency matrix (spectrum)

If any invariant differs, the graphs are non-isomorphic. If all match, search for an explicit bijection.

Transfer / Where This Shows Up Later​

  • Semester 2 algorithms: adjacency list vs matrix choice drives the complexity of BFS, DFS, Dijkstra, and all other core graph algorithms. Matrix multiplication underlies transitive closure (Warshall) and APSP (Floyd-Warshall).
  • Semester 3 data structures: sparse-matrix representations for huge graphs (CSR, CSC) are the default in numerical and graph-analytic libraries.
  • Semester 4 linear algebra (Module 4 this semester): adjacency-matrix spectra, PageRank's principal eigenvector, spectral clustering -- all depend on the matrix viewpoint introduced here.
  • Semester 5 concurrency / 6 distributed systems: process interaction graphs and replica communication graphs use isomorphism-style invariants to decide symmetry-breaking protocols.
  • Semester 7 architecture: fitness functions detecting architectural anti-patterns (e.g., layer violations) operate on isomorphism classes of subgraphs of the call graph.
  • Machine learning (later): graph neural networks (GNNs) are isomorphism-respecting; their expressive power is bounded by the Weisfeiler-Lehman isomorphism test, a direct descendant of the invariant-based approach described above.

Check Yourself​

  1. What does graph isomorphism preserve, precisely? Give the formal definition.
  2. Why does equal degree sequence not prove isomorphism? Give a small counterexample.
  3. What does $A^2$ tell you about a graph? State the walk interpretation and apply it to $C_3$.
  4. Compute the adjacency matrix of $K_4$ and $A^2$. What does the diagonal of $A^2$ tell you?
  5. Is the graph-isomorphism decision problem known to be in $P$? Known to be $NP$-complete? State the current complexity status.
  6. Why is the spectrum of $A$ an isomorphism invariant?

Mini Drill or Application​

  1. Convert a small graph of your choice (at least $5$ vertices) into an edge list, adjacency list, and adjacency matrix. Verify they encode the same graph.
  2. Give two non-isomorphic graphs on $4$ vertices with the same number of edges but different degree sequences. Then give two with the same degree sequence that are still non-isomorphic (hint: connected vs disconnected).
  3. Compute $A^2$ and $A^3$ for $K_4$ and interpret the diagonal entries as walk counts.
  4. For a graph on $n$ vertices with average degree $\bar d$, how many entries in the adjacency matrix are zero? What is the matrix density?
  5. Use the triangle count formula $\operatorname{tr}(A^3)/6$ on $K_4$: compute and compare to $\binom{4}{3} = 4$ triangles.

Read This Only If Stuck​