Adjacency Matrices and Isomorphism

A graph is an abstract object, but to compute with it — to let an algorithm or a computer process it — we need a concrete representation. The adjacency matrix turns a graph into a square array of numbers, opening the door to linear algebra: matrix multiplication counts walks, eigenvalues encode structure, and the whole apparatus of Further-Maths matrix theory becomes available. Alongside this we study graph isomorphism — the precise meaning of "two graphs are really the same graph drawn differently" — which is where careful definitions earn the AO2 communication marks.

---

1. Where this sits in AQA 7367

This is a core representation topic of the Paper 3 Discrete option (7367/3D) (Paper 3: 2 h, 100 marks, 33⅓%; AO1 40% / AO2 25% / AO3 35%). It is the natural bridge between the Discrete option and the compulsory Matrices content of Papers 1 & 2: the adjacency matrix is a genuine matrix, so determinants, powers and (at stretch) eigenvalues all apply. Walk-counting via $A^k$Ak tests AO1 (apply a technique); isomorphism arguments test AO2 (reason and communicate) and AO3 (decide a structural question and justify it).

---

2. Core theory: the adjacency matrix

Label the vertices $1, 2, \dots, n$1,2,…,n. The adjacency matrix is the $n \times n$n×n matrix $A$A with

$A_{ij} = \begin{cases} 1 & \text{if vertices } i \text{ and } j \text{ are joined by an edge}, \\ 0 & \text{otherwise}. \end{cases}$Aij​={10​if vertices i and j are joined by an edge,otherwise.​

For a multigraph, $A_{ij}$Aij​ is the number of edges between $i$i and $j$j (and a loop contributes $2$2 on the diagonal, matching its degree).

Property	Statement
Symmetry	For an undirected graph, $A_{ij} = A_{ji}$Aij​=Aji​, i.e. $A = A^{\mathsf{T}}$A=AT
Diagonal	$A_{ii} = 0$Aii​=0 for a simple graph (no loops)
Row / column sum	$\displaystyle\sum_{j} A_{ij} = \deg(i)$j∑​Aij​=deg(i)
Digraphs	$A_{ij} = 1$Aij​=1 iff there is an arc $i \to j$i→j; generally $A \ne A^{\mathsf{T}}$A=AT

Worked Example 2.1 — building the matrix

Vertices A, B, C, D with edges AB, AC, BC, CD. Write down $A$A and read off the degrees.

$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 are $2, 2, 3, 1$2,2,3,1, so $\deg(A) = 2,\ \deg(B) = 2,\ \deg(C) = 3,\ \deg(D) = 1$deg(A)=2, deg(B)=2, deg(C)=3, deg(D)=1. (M1 for a symmetric $0/1$0/1 matrix with zero diagonal; A1 for the correct entries.) Check with the handshaking lemma: $\sum \deg = 8 = 2|E|$∑deg=8=2∣E∣, so $|E| = 4$∣E∣=4 — and indeed we listed four edges.

The same graph as a network reminder:

graph LR
  A((A)) --- B((B))
  A --- C((C))
  B --- C
  C --- D((D))

---

3. Powers of the adjacency matrix (with M1/A1 mark scheme)

The central theorem makes the matrix do work:

$(A^k)_{ij} = \text{the number of walks of length } k \text{ from } i \text{ to } j.$(Ak)ij​=the number of walks of length k from i to j.

Why. $(A^2)_{ij} = \sum_{m} A_{im} A_{mj}$(A2)ij​=∑m​Aim​Amj​; each product $A_{im} A_{mj}$Aim​Amj​ is $1$1 exactly when both $i\!-\!m$i−m and $m\!-\!j$m−j are edges, i.e. when $i\!-\!m\!-\!j$i−m−j is a length-2 walk. Summing over the intermediate vertex $m$m counts all such walks. Induction on $k$k extends this to every power. $\blacksquare$■

Worked Example 3.1 — counting walks

Using $A$A from §2, compute $A^2$A2 and interpret two entries.

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

(M1 for a correct row × column multiplication; A1 for the full matrix.)

• $(A^2)_{AD} = 1$(A2)AD​=1: exactly one walk of length $2$2 from A to D, namely $A\!-\!C\!-\!D$A−C−D.
• $(A^2)_{CC} = 3 = \deg(C)$(A2)CC​=3=deg(C): the three length-2 closed walks $C\!-\!A\!-\!C,\ C\!-\!B\!-\!C,\ C\!-\!D\!-\!C$C−A−C, C−B−C, C−D−C. In general $(A^2)_{vv} = \deg(v)$(A2)vv​=deg(v), a handy check.

Worked Example 3.2 — a five-vertex graph and $A^3$A3

Vertices P, Q, R, S, T with edges PQ, PR, QR, RS, ST (a path P–Q–R–S–T plus the chord PR). Find $(A^2)_{RR}$(A2)RR​ and $(A^3)_{PT}$(A3)PT​.

$A = \begin{pmatrix} 0&1&1&0&0\\ 1&0&1&0&0\\ 1&1&0&1&0\\ 0&0&1&0&1\\ 0&0&0&1&0 \end{pmatrix},\qquad A^3 = \begin{pmatrix} 2&3&4&1&1\\ 3&2&4&1&1\\ 4&4&2&4&0\\ 1&1&4&0&2\\ 1&1&0&2&0 \end{pmatrix}.$A=​01100​10100​11010​00101​00010​​,A3=​23411​32411​44240​11402​11020​​.

Here $(A^2)_{RR} = \deg(R) = 3$(A2)RR​=deg(R)=3 (B1). And $(A^3)_{PT} = 1$(A3)PT​=1 (A1): there is exactly one walk of length $3$3 from P to T, namely $P\!-\!R\!-\!S\!-\!T$P−R−S−T. (M1 for using the walk-count interpretation rather than re-listing by hand.)

Exam tip. Walk-counts include revisits and back-tracking — a length-4 walk $C\!-\!A\!-\!C\!-\!A$C−A−C−A is counted in $(A^4)_{CA}$(A4)CA​. Do not confuse "walks of length $k$k" with "paths".

---

4. The distance (weight) matrix

For a network, the distance matrix $D$D records edge weights: $D_{ij} = w(ij)$Dij​=w(ij) if $i\!-\!j$i−j is an edge, $D_{ii} = 0$Dii​=0 (or "$-$−"), and $D_{ij} = \infty$Dij​=∞ when there is no direct edge. This is a different object from the adjacency matrix and is the input to Prim's matrix method and to Dijkstra's algorithm.

	A	B	C	D
A	–	3	5	$\infty$∞
B	3	–	4	6
C	5	4	–	2
D	$\infty$∞	6	2	–

Note the contrast: the adjacency matrix answers "is there an edge?"; the distance matrix answers "how heavy is the edge?". A third relative, the incidence matrix $M$M, is a $|V| \times |E|$∣V∣×∣E∣ array with $M_{ve} = 1$Mve​=1 when vertex $v$v is an endpoint of edge $e$e; it records the vertex–edge relationship rather than vertex–vertex, and satisfies the elegant identity $M M^{\mathsf{T}} = A + D$MMT=A+D, where $D = \operatorname{diag}(\deg v)$D=diag(degv) is the degree matrix. You are unlikely to be asked to manipulate the incidence matrix directly, but knowing it exists clarifies why the adjacency matrix — vertex by vertex — is the natural object for walk-counting.

Directed graphs

For a digraph the adjacency matrix is generally not symmetric: $A_{ij} = 1$Aij​=1 records an arc $i \to j$i→j only. The $i$ith row sum is then the out-degree $\deg^{+}(i)$deg+(i) and the $j$jth column sum is the in-degree $\deg^{-}(j)$deg−(j). Walk-counting still holds verbatim — $(A^k)_{ij}$(Ak)ij​ counts directed walks of length $k$k from $i$i to $j$j — which is exactly how one tests reachability in a one-way network: vertex $j$j is reachable from $i$i iff $(A + A^2 + \cdots + A^{\,n-1})_{ij} > 0$(A+A2+⋯+An−1)ij​>0.

Worked Example 4.1 — a directed adjacency matrix

A digraph on A, B, C, D has arcs $A\!\to\!B,\ B\!\to\!C,\ C\!\to\!A,\ A\!\to\!C$A→B, B→C, C→A, A→C. Write $A$A (rows/columns in order A, B, C, D) and find the number of directed walks of length $2$2 from A to A.

$A = \begin{pmatrix} 0&1&1&0\\ 0&0&1&0\\ 1&0&0&0\\ 0&0&0&0 \end{pmatrix},\qquad A^2 = \begin{pmatrix} 1&0&1&0\\ 1&0&0&0\\ 0&1&1&0\\ 0&0&0&0 \end{pmatrix}.$A=​0010​1000​1100​0000​​,A2=​1100​0010​1010​0000​​.

The asymmetry of $A$A signals a genuine digraph. The entry $(A^2)_{AA} = 1$(A2)AA​=1: exactly one directed length-2 walk returns to A, namely $A\!\to\!C\!\to\!A$A→C→A. (M1 for an unsymmetric $0/1$0/1 matrix matching the arc directions; A1 for $(A^2)_{AA} = 1$(A2)AA​=1 with the walk identified.) Note D is an isolated sink/source here — its row and column are entirely zero, so no walk of any length involves D.

---

5. Graph isomorphism

Two graphs $G_1 = (V_1, E_1)$G1​=(V1​,E1​) and $G_2 = (V_2, E_2)$G2​=(V2​,E2​) are isomorphic, written $G_1 \cong G_2$G1​≅G2​, if there is a bijection $\varphi : V_1 \to V_2$φ:V1​→V2​ that preserves adjacency:

$uv \in E_1 \iff \varphi(u)\varphi(v) \in E_2.$uv∈E1​⟺φ(u)φ(v)∈E2​.

Informally, one graph can be relabelled and redrawn to become the other. In matrix terms, $G_1 \cong G_2$G1​≅G2​ iff there is a permutation matrix $P$P with $A_2 = P A_1 P^{\mathsf{T}}$A2​=PA1​PT.

Necessary conditions (quick disqualifiers)

Invariant	Must agree for isomorphic graphs
Number of vertices $	V
Number of edges $	E
Degree sequence (degrees, sorted)	Yes
Number of cycles of each length (e.g. triangles)	Yes
Connectedness, number of components	Yes

These are necessary but not sufficient: graphs can share all of them yet differ. To prove isomorphism you must exhibit a bijection and verify every edge; to disprove it, find one invariant that differs.

Worked Example 5.1 — proving isomorphism

Graph 1: vertices $\{1,2,3,4\}${1,2,3,4}, edges $\{12, 13, 24, 34\}${12,13,24,34}. Graph 2: vertices $\{A,B,C,D\}${A,B,C,D}, edges $\{AB, BC, CD, DA\}${AB,BC,CD,DA}. Decide whether they are isomorphic.

Both have degree sequence $[2,2,2,2]$[2,2,2,2] and are connected — each is the $4$4-cycle $C_4$C4​. Try $\varphi:\ 1\!\to\!A,\ 2\!\to\!B,\ 3\!\to\!D,\ 4\!\to\!C$φ: 1→A, 2→B, 3→D, 4→C.

Edge of $G_1$G1​	Image under $\varphi$φ	In $E_2$E2​?
$12$12	$AB$AB	✓
$13$13	$AD$AD	✓
$24$24	$BC$BC	✓
$34$34	$DC$DC	✓

All four edges map onto edges of $G_2$G2​ and $\varphi$φ is a bijection, so $G_1 \cong G_2$G1​≅G2​. (M1 for proposing a bijection; A1 for verifying every edge correspondence.)

Worked Example 5.2 — disproving isomorphism

Two graphs each have $6$6 vertices, $7$7 edges and degree sequence $[3,3,2,2,2,2]$[3,3,2,2,2,2], but Graph 1 contains a triangle and Graph 2 contains none. Are they isomorphic?

The number of triangles (length-3 cycles) is an isomorphism invariant. Graph 1 has $\ge 1$≥1 triangle; Graph 2 has $0$0. Since the invariants differ, the graphs are not isomorphic — even though $|V|$∣V∣, $|E|$∣E∣ and the degree sequence all agree. (B1 for naming a differing invariant; B1 for the correct conclusion.) You can also detect triangles algebraically: $(A^3)_{vv} = 2\times(\text{number of triangles through } v)$(A3)vv​=2×(number of triangles through v), so $\operatorname{tr}(A^3) = 6 \times (\text{number of triangles})$tr(A3)=6×(number of triangles).

---

6. Complement, regularity and degree sequences

The complement $\bar{G}$Gˉ has the same vertices as $G$G, with an edge exactly where $G$G has none (loops excluded). In matrix form,

$A(\bar{G}) = J - I - A(G),$A(Gˉ)=J−I−A(G),

where $J$J is the all-ones matrix and $I$I the identity. A graph is $r$r-regular if every vertex has degree $r$r; then every row of $A$A sums to $r$r, so $\mathbf{1} = (1,1,\dots,1)^{\mathsf{T}}$1=(1,1,…,1)T is an eigenvector: $A\mathbf{1} = r\mathbf{1}$A1=r1, giving $r$r as an eigenvalue.

A degree sequence is the list of degrees in non-increasing order, e.g. $[4,3,3,2,2]$[4,3,3,2,2]. Not every list is graphical: by the handshaking lemma its sum must be even, and the Erdős–Gallai conditions characterise the rest (beyond A-Level, but the even-sum check is fair game).

Worked Example 6.1 — building and checking a complement

The graph $G$G on $\{1,2,3,4\}${1,2,3,4} has edges $12, 23, 34$12,23,34 (a path). Write $A(G)$A(G), then use $A(\bar G) = J - I - A$A(Gˉ)=J−I−A to find the complement's adjacency matrix and describe $\bar G$Gˉ.

$A(G) = \begin{pmatrix} 0&1&0&0\\ 1&0&1&0\\ 0&1&0&1\\ 0&0&1&0 \end{pmatrix},\qquad J - I = \begin{pmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{pmatrix}.$A(G)=​0100​1010​0101​0010​​,J−I=​0111​1011​1101​1110​​.

Subtracting, $A(\bar G) = (J - I) - A(G)$A(Gˉ)=(J−I)−A(G):

$A(\bar G) = \begin{pmatrix} 0&0&1&1\\ 0&0&0&1\\ 1&0&0&0\\ 1&1&0&0 \end{pmatrix}.$A(Gˉ)=​0011​0001​1000​1100​​.

(M1 for forming $J - I$J−I; A1 for the correct subtraction.) So $\bar G$Gˉ has edges $13, 14, 24$13,14,24. Its degree sequence is $[2, 2, 1, 1]$[2,2,1,1] — note that $G$G had degree sequence $[1, 2, 2, 1]$[1,2,2,1] i.e. $[2,2,1,1]$[2,2,1,1] too, which is why a path on four vertices is self-complementary up to relabelling. (A1 for identifying the complement's edges.)

When is a sequence graphical?