Introduction to Algebraic Graph Theory

The adjacency matrix, the Laplacian $L = D - A$, the matrix tree theorem, eigenvalues and connectivity, and a proof that the $(i,j)$-entry of $A^k$ counts the number of walks of length $k$.

Folio Official

March 1, 2026

1 The Adjacency Matrix

Definition 1 (Adjacency matrix).

For a simple graph

G = (V, E)

n

vertices

V = {v_{1}, \dots, v_{n}}

, the adjacency matrix

A = A (G)

is the

n \times n

matrix defined by

A_{ij} = {10 {v_{i}, v_{j}} \in E, otherwise.

When

G

is undirected,

A

is a real symmetric matrix.

Example 2.

The path graph

P_{3}

on vertices

v_{1} - v_{2} - v_{3}

has adjacency matrix

A = 010101010 .

2 Powers of the Adjacency Matrix and Walk Counting

Theorem 3 (Combinatorial interpretation of

A^{k}

Let

A

be the adjacency matrix of a graph

G

. The

(i, j)

-entry of

A^{k}

equals the number of walks of length

k

from

v_{i}

v_{j}

Proof.

We proceed by induction on

k

Base case ( $k = 1$ ).

(A)_{ij} = 1

if and only if

v_{i}

and

v_{j}

are adjacent, which corresponds to a single walk of length

1

. If

(A)_{ij} = 0

, there is no such walk.

Inductive step. Assume

(A^{k - 1})_{i ℓ}

counts the walks of length

k - 1

from

v_{i}

v_{ℓ}

for every

ℓ

. Then

(A^{k})_{ij} = ℓ = 1 \sum n (A^{k - 1})_{i ℓ} \cdot A_{ℓ j} .

The term

(A^{k - 1})_{i ℓ} \cdot A_{ℓ j}

is nonzero only when

v_{ℓ}

and

v_{j}

are adjacent (

A_{ℓ j} = 1

), in which case it counts the walks of length

k - 1

from

v_{i}

v_{ℓ}

, each of which extends to a walk of length

k

from

v_{i}

v_{j}

by appending the edge

{v_{ℓ}, v_{j}}

. Summing over all possible intermediate vertices

v_{ℓ}

gives the total number of walks of length

k

from

v_{i}

v_{j}

. □

Example 4.

The triangle

K_{3}

has adjacency matrix

A = 011101110

and

A^{2} = 211121112

. The entry

(A^{2})_{11} = 2

reflects the two walks of length

2

from

v_{1}

to itself:

v_{1} v_{2} v_{1}

and

v_{1} v_{3} v_{1}

3 The Laplacian Matrix

Definition 5 (Degree matrix and Laplacian).

The degree matrix

D

G

is the diagonal matrix with

D_{ii} = de g (v_{i})

. The Laplacian of

G

L = L (G) = D - A .

Each row of $L$ sums to zero ( $\sum_{j} L_{ij} = D_{ii} - \sum_{j} A_{ij} = de g (v_{i}) - de g (v_{i}) = 0$ ), so $L 1 = 0$ : the all-ones vector $1$ is an eigenvector of $L$ with eigenvalue $0$ .

Theorem 6 (Positive semidefiniteness of the Laplacian).

L (G)

is positive semidefinite:

x^{T} L x \geq 0

for every

x \in R^{n}

Proof.

x^{T} L x = i \sum D_{ii} x_{i}^{2} - i, j \sum A_{ij} x_{i} x_{j} = {v_{i}, v_{j}} \in E \sum (x_{i} - x_{j})^{2} \geq 0.

The last equality is obtained by expanding the contributions of each edge

{v_{i}, v_{j}}

to both the diagonal (

D

) and off-diagonal (

A

) terms. □

4 Eigenvalues and Connectivity

Since $L$ is real symmetric and positive semidefinite, its eigenvalues can be arranged as $0 = λ_{1} \leq λ_{2} \leq \dots \leq λ_{n}$ .

Theorem 7 (Connected components and the multiplicity of eigenvalue

0

The number of connected components of

G

equals the multiplicity of

0

as an eigenvalue of

L (G)

Proof.

G

has

c

connected components

G_{1}, \dots, G_{c}

, reordering the vertices by component makes

L

block-diagonal:

L = L (G_{1}) \oplus \dots \oplus L (G_{c})

. Each

L (G_{k})

is positive semidefinite with

L (G_{k}) 1_{k} = 0

, so each has eigenvalue

0

with multiplicity at least

1

To see that the multiplicity is exactly

1

for each block: if

L (G_{k}) x = 0

, then

x^{T} L (G_{k}) x = \sum_{{v_{i}, v_{j}} \in E (G_{k})} (x_{i} - x_{j})^{2} = 0

, forcing

x_{i} = x_{j}

for all adjacent pairs. Since

G_{k}

is connected, all components of

x

are equal, so

ker L (G_{k})

is one-dimensional.

Therefore the total multiplicity of eigenvalue

0

c

. □

Definition 8 (Algebraic connectivity).

For a connected graph

G

, the second-smallest eigenvalue

λ_{2} (L (G))

is called the algebraic connectivity (or Fiedler value) of

G

Remark 9.

λ_{2} > 0

is equivalent to

G

being connected. A larger

λ_{2}

indicates stronger connectivity, making algebraic connectivity an important measure in spectral graph partitioning and clustering.

5 The Matrix Tree Theorem

Theorem 10 (Matrix tree theorem (Kirchhoff, 1847)).

Let

G

be a connected graph on

n

vertices with Laplacian

L = L (G)

. Let

L_{ii}

denote any cofactor of

L

obtained by deleting row

i

and column

i

. Then the number

τ (G)

of spanning trees of

G

τ (G) = L_{ii} = \frac{1}{n} λ_{2} λ_{3} \dots λ_{n},

where

λ_{1} = 0 < λ_{2} \leq \dots \leq λ_{n}

are the eigenvalues of

L

Proof.

We outline the argument. Let

\hat{L}

be the

(n - 1) \times (n - 1)

matrix obtained by deleting row

i

and column

i

from

L

. By the Cauchy–Binet formula,

det \hat{L} = ∣ S ∣ = n - 1 \sum (det B_{S})^{2},

where

B

is the oriented incidence matrix of

G

with row

i

deleted, and

S

ranges over all

(n - 1)

-element subsets of the edge set. One shows that

det B_{S} \neq = 0

if and only if

S

forms a spanning tree, in which case

det B_{S} = \pm 1

. Thus the sum counts spanning trees.

The eigenvalue formula

det \hat{L} = \frac{1}{n} \prod_{k = 2}^{n} λ_{k}

follows from analysis of the characteristic polynomial of

L

. □

Example 11.

The Laplacian of

K_{4}

has eigenvalues

0, 4, 4, 4

, giving

τ (K_{4}) = \frac{1}{4} \cdot 4^{3} = 16

. More generally,

τ (K_{n}) = n^{n - 2}

, recovering Cayley's formula.

Graph Theory Discrete Mathematics Textbook Adjacency Matrix Laplacian Matrix Tree Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·105 articles

Introduction to Algebraic Graph Theory

1 The Adjacency Matrix

2 Powers of the Adjacency Matrix and Walk Counting

3 The Laplacian Matrix

4 Eigenvalues and Connectivity

5 The Matrix Tree Theorem

Share your expertise with the world

More from Folio Official

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry