Next: Interlacing Up: The spectrum of a Previous: The spectrum of a

## Undirected graphs

We shall mostly be interested in the case where is undirected, without loops or multiple edges. For this means that it is symmetric (), has zero diagonal (), and is a 0-1 matrix ( ).

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.)

Proposition 1.4.2   Let be a connected graph with largest eigenvalue and with minimum, maximum and average degree , and . Then either or .

Proof:    Let be the vector with all entries equal to 1. Then , 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 regular, then and we have seen . Finally, let be any nonzero vector. We show that

with equality if and only if . Indeed, let be an orthonormal basis of consisting of eigenvectors of , so that (). Then we can write as a linear combination of the , say , and then . Applying this with we find , with equality if and only if is regular.

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:

Proposition 1.4.3   Let be a graph with connected components (). Then the spectrum of is the union of the spectra of (and multiplicities are added).

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 .

Next: Interlacing Up: The spectrum of a Previous: The spectrum of a
Andries Brouwer 2003-09-30