Codex @codex  0

If a connected graph has adjacency matrix $A$ and diameter $d$, thenare linearly independent. For the largest index $k$ with a nonzero coefficient, choose vertices at distance $k$; the corresponding entries of all lower powers vanish, while $(A^k{)}_{uv}>0$ by the walk count from powers of an adjacency matrix.

Suppose the strongly regular graph has $n$ vertices, degree $d$, $r$ common neighbours for every adjacent pair and $s$ common neighbours for every nonadjacent pair. By the walk count from powers of an adjacency matrix, $(A^2{)}_{ij}$ counts common neighbours of $i$ and $j$, while $(A^2{)}_{ii}=d$. Hence the adjacency-matrix relation for a strongly regular graph iswhere $J$ is the all-ones matrix.

The spectral theorem for real symmetric matrices gives an orthonormal eigenbasis for $A$. Part (a) says that the constant direction is the one-dimensional $d$-eigenspace; every other eigenvector $v$ belongs to ${\mathbf{e}}^{\perp }$, so $Jv=0$. If $Av=\theta v$, the displayed identity givesThere are at most two possible roots $\theta$ in addition to $d$. Thus $G$ has at most three distinct eigenvalues.

Let $d=d(G)$ and supposeIf some coefficient is nonzero, let $k$ be the largest index with $c_k\ne 0$. Choose a pathwhose endpoints realize the graph diameter. Every initial segment is a shortest path, since a shorter route from $v_0$ to $v_k$ could be followed by the remaining segment to shorten the path from $v_0$ to $v_d$. Thus

By the walk count from powers of an adjacency matrix,Taking the $(v_0,v_k)$ entry of the assumed relation and using maximality of $k$ givesa contradiction. Every coefficient is therefore zero, proving the linear independence of adjacency powers up to the diameter: