Diameter

Proposition 1.9.1   Let $\Gamma$ be a connected graph of diameter $d$. Then $\Gamma$ has at least $d + 1$ distinct eigenvalues.

Proof:    Let the distinct eigenvalues of the adjacency matrix $A$ of $\Gamma$ be $\theta_1 , ... , \theta_t$. Then $(A - \theta_1 I) ... (A - \theta_t I) = 0$, so that $A^t$ is a linear combination of $I, A, ... , A^{t-1}$. But if $d(x,y) = t$ for two vertices $x,y$ of $\Gamma$, then $(A^i )_{xy} = 0$ for $0 \le i \le t - 1$ and $(A^t )_{xy} > 0$, contradiction. Hence $t > d$. $\Box$