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

The triangle $K_{3}$ on three vertices:

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.

The following graph has $τ (G) = 8$ spanning trees, which can be verified via any cofactor of its Laplacian:

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·107 articles

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

The triangle $K_{3}$ on three vertices:

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.

The following graph has $τ (G) = 8$ spanning trees, which can be verified via any cofactor of its Laplacian:

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·107 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

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

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

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences