Exercise 2144Combinatorics › Graph theoryM1Added 3 Nov 2026

Spectral graph theory (statement)

#spectral graph#eigenvalues#adjacency

Statement

State the relationship between the eigenvalues of the adjacency matrix and the structure of the graph.

Hint

$G$ is $d$ -regular iff $d$ is the largest eigenvalue of $A_G$ with all-ones eigenvector.

Show solutionHide solution

Solution

Adjacency matrix. $A_G$ symmetric with $0/1$ entries.

Properties.
- $G$ is $d$ -regular $\Rightarrow$ $\lambda_{\max}=d$ with eigenvector $\mathbf{1}$ .
- $\lambda_{\max}$ equals the spectral radius.
- $G$ bipartite iff its spectrum is symmetric about $0$ .

Application. The Alon–Boppana bound limits expansion of regular graphs.

Conclusion. Spectral methods relate eigenvalues to combinatorial structure.

Spectral graph theory (statement)

Statement

Solution

More problems in Graph theory