Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 1 17G a Solution Created 2026-09-24 Updated 2026-10-20
Let be the adjacency matrix of a graph. Since is a regular graph of degree , every row of sums to . Therefore, for ,so is a graph eigenvalue.
If , then the quadratic form of the graph Laplacian givesEvery summand is nonnegative, so along every edge. The graph is connected, hence all coordinates of are equal and is a scalar multiple of . Thus the -eigenspace is one-dimensional. Since is a symmetric matrix, the spectral theorem for real symmetric matrices makes it diagonalizable, so the algebraic multiplicity is also one. This proves the constant eigenvector of a regular graph result.
Spectral graph theory Created 2026-10-14 Updated 2026-11-05
Spectral graph theory studies a graph through eigenvalues and eigenvectors of associated matrices, especially its adjacency matrix and graph Laplacian. A graph eigenvalue usually means an adjacency eigenvalue unless another matrix is specified.
For an undirected graph, the Laplacian satisfies . Its kernel therefore consists of vectors constant on each connected component, so the multiplicity of zero equals the number of components. This makes a discrete connectivity property visible in linear algebra. Nonzero eigenvalues further quantify mixing, expansion, and the cost of varying across edges.