A number is eigenvalue of if and only if it is a zero of the polynomial . Since is real and symmetric, all its eigenvalues are real. Also, for each eigenvalue , its algebraic multiplicity (that is, its multiplicity as a root of the polynomial ) coincides with its geometric multiplicity (that is, the dimension of the eigenspace ), so that we may omit the adjective and just speak about `multiplicity'. Conjugate algebraic integers have the same multiplicity.
Two very useful properties of this matrix representation of a graph are:
(i) is regular (of degree ) if and only if (where is the matrix with all entries equal to 1);
(ii) is the number of paths of length from to . In particular, is the degree of the vertex , and equals twice the number of edges of ; similarly, is six times the number of triangles in .
By Perron-Frobenius theory, we know something about the largest eigenvalue of a connected graph. (Indeed, is irreducible if and only if is connected.)
Proof: Let be the vector with all entries equal to 1.
, and by (iv) of
Perron-Frobenius we have
with equality if and only if
that is, if and only if is regular of degree .
This settles the case where is regular. If is not
and we have seen
let be any nonzero vector. We show that
Remark Choosing the vector in the previous proof more subtly, we may obtain better bounds on .
Exercise Use interlacing (see below) to show that . When does equality hold?
The spectrum of a disconnected graph is easily found from the spectra of its components:
So, for not necessarily connected graphs, we have , and if and only if is regular, but if then we only know that has a regular component with this valency, but need not be regular itself.
Exercise Show that no (undirected) graph has eigenvalue .