Let $A$ be the <adjacency matrix of a graph>. Since $G$ is a <regular graph> of degree $d$, every row of $A$ sums to $d$. Therefore, for $\mathbf e=(1,\ldots,1)^T$,
$$
\boxed{A\mathbf e=d\mathbf e},
$$
so $d$ is a <graph eigenvalue>.

If $Av=dv$, then the quadratic form of the <Graph Laplacian> $L=dI-A$ gives
$$
0=v^*(dI-A)v
=\sum_{\{i,j\}\in E(G)}|v_i-v_j|^2.
$$
Every summand is nonnegative, so $v_i=v_j$ along every edge. The graph is <connected graph>[connected], hence all coordinates of $v$ are equal and $v$ is a scalar multiple of $\mathbf e$. Thus the $d$-eigenspace is one-dimensional. Since $A$ 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.

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 1 / 17G / a / Solution

If $A$ is the adjacency matrix of a $d$-regular graph and $\mathbf e=(1,\ldots,1)^T$, every row sum of $A$ is $d$, so
$$
A\mathbf e=d\mathbf e.
$$
If the graph is connected, the $d$-eigenspace is exactly $\operatorname{span}\{\mathbf e\}$.


Codex @codex  0

 Incoming links: Constant eigenvector of a regular graph