Adjacency matrix
Spectrum

The adjacency matrix of an undirected simple graph is symmetric, and therefore has a complete set of real eigenvalues and an orthogonal eigenvector basis. The set of eigenvalues of a graph is the spectrum of the graph. It is common to denote the eigenvalues by λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n. {\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}.}

The greatest eigenvalue λ 1 {\displaystyle \lambda _{1}} is bounded above by the maximum degree. This can be seen as result of the Perron–Frobenius theorem, but it can be proved easily. Let v be one eigenvector associated to λ 1 {\displaystyle \lambda _{1}} and x the component in which v has maximum absolute value. Without loss of generality assume v is positive since otherwise you simply take the eigenvector − v {\displaystyle -v}, also associated to λ 1 {\displaystyle \lambda _{1}}. Then

For d -regular graphs, d is the first eigenvalue of A for the vector v = (1, …, 1) (it is easy to check that it is an eigenvalue and it is the maximum because of the above bound). The multiplicity of this eigenvalue is the number of connected components of G, in particular λ 1 > λ 2 {\displaystyle \lambda _{1}>\lambda _{2}} for connected graphs. It can be shown that for each eigenvalue λ i {\displaystyle \lambda _{i}}, its opposite − λ i = λ n + 1 − i {\displaystyle -\lambda _{i}=\lambda _{n+1-i}} is also an eigenvalue of A if G is a bipartite graph. In particular − d is an eigenvalue of any d -regular bipartite graph.

The difference λ 1 − λ 2 {\displaystyle \lambda _{1}-\lambda _{2}} is called the spectral gap and it is related to the expansion of G. It is also useful to introduce the spectral radius of A {\displaystyle A} denoted by λ (G) = max | λ i | < d | λ i | {\displaystyle \lambda (G)=\max _{\left|\lambda _{i}\right|<d}|\lambda _{i}|}. This number is bounded by λ (G) ≥ 2 d − 1 − o (1) {\displaystyle \lambda (G)\geq 2{\sqrt {d-1}}-o(1)}. This bound is tight in the Ramanujan graphs, which have applications in many areas.
detectable_content:postscript