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​​