Adjacency Matrices and Isomorphism

This lesson covers how to represent graphs as matrices and how to determine when two graphs are structurally identical (isomorphic). Matrix representations allow graphs to be processed by computers and provide a way to calculate path counts.

---

The Adjacency Matrix

For a graph with $n$n vertices, the adjacency matrix is an $n \times n$n×n matrix $A$A where:

$A_{ij} = \begin{cases} 1 & \text{if there is an edge between vertices } i \text{ and } j \\ 0 & \text{otherwise} \end{cases}$Aij​={10​if there is an edge between vertices i and jotherwise​

Properties

Property	Detail
Symmetric	For undirected graphs, $A_{ij} = A_{ji}$Aij​=Aji​
Diagonal	$A_{ii} = 0$Aii​=0 for simple graphs (no loops)
Row/column sum	Equals the degree of the vertex

Worked Example

Consider a graph with vertices A, B, C, D and edges AB, AC, BC, CD.

$A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$A=​0110​1010​1101​0010​​

Row sums: A = 2, B = 2, C = 3, D = 1. These are the vertex degrees.

---

Powers of the Adjacency Matrix

The entry $(A^k)_{ij}$(Ak)ij​ gives the number of walks of length $k$k from vertex $i$i to vertex $j$j.

Worked Example

Using the matrix above:

$A^2 = \begin{pmatrix} 2 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 3 & 0 \\ 1 & 1 & 0 & 1 \end{pmatrix}$A2=​2111​1211​1130​1101​​

$(A^2)_{AD} = 1$(A2)AD​=1: there is exactly 1 walk of length 2 from A to D (A-C-D).

$(A^2)_{CC} = 3$(A2)CC​=3: there are 3 walks of length 2 from C back to C (C-A-C, C-B-C, C-D-C).

Exam Tip: The diagonal entries of $A^2$A2 give the degree of each vertex (the number of walks of length 2 from a vertex back to itself equals its degree). This provides a useful check.

---

The Distance Matrix

For a weighted graph, the distance matrix records the weight of the edge between each pair of vertices (or $\infty$∞ if there is no direct edge).

This is different from the adjacency matrix and is used in shortest path algorithms.

---

Graph Isomorphism

Two graphs $G_1$G1​ and $G_2$G2​ are isomorphic if there is a bijection (one-to-one correspondence) between their vertex sets that preserves edges.

Informally: two graphs are isomorphic if one can be redrawn to look exactly like the other.

Necessary Conditions for Isomorphism