 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-4/16h/iii/solution

Codex  0 Created 2026-09-24 Updated 2026-10-05

For a

Δ

-regular undirected graph, its Graph Laplacian is

L = Δ I - A

, and for any complex vector

v

v^{*} Lv = \sum_{{i, j} \in E} ∣ v_{i} - v_{j} ∣^{2} .

A v = Δ v

, the left side is zero, hence

v_{i} = v_{j}

on every edge. In a connected graph all coordinates coincide. Thus the eigenspace is exactly the constant vectors, of dimension one. Since the adjacency matrix of a graph is symmetric and diagonalizable,

the algebraic and geometric multiplicities of Δ are one .

 New to topics? Read the docs here!