Undirected graphs

We shall mostly be interested in the case where $\Gamma$ is undirected, without loops or multiple edges. For $A$ this means that it is symmetric ($A = A^\top$), has zero diagonal ($a_{xx} = 0$), and is a 0-1 matrix ( $a_{xy} \in \{0,1\}$).

A number $\theta$ is eigenvalue of $A$ if and only if it is a zero of the polynomial $p_A$. Since $A$ is real and symmetric, all its eigenvalues are real. Also, for each eigenvalue $\theta$, its algebraic multiplicity (that is, its multiplicity as a root of the polynomial $p_A$) coincides with its geometric multiplicity (that is, the dimension of the eigenspace $V_\theta = \{ v \mid Av = \theta v \}$), 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) $\Gamma$ is regular (of degree $k$) if and only if $AJ = kJ$ (where $J$ is the matrix with all entries equal to 1);

(ii) $(A^h )_{xy}$ is the number of paths of length $h$ from $x$ to $y$. In particular, $(A^2 )_{xx}$ is the degree of the vertex $x$, and ${\rm tr}A^2$ equals twice the number of edges of $\Gamma$; similarly, ${\rm tr}A^3$ is six times the number of triangles in $\Gamma$.

By Perron-Frobenius theory, we know something about the largest eigenvalue of a connected graph. (Indeed, $A$ is irreducible if and only if $\Gamma$ is connected.)

Proposition 1.4.2   Let $\Gamma$ be a connected graph with largest eigenvalue $\theta_1$ and with minimum, maximum and average degree $k_{\min}$, $k_{\max}$ and $\bar{k}$. Then either $k_{\min} < \bar{k} < \theta_1 < k_{\max}$ or $k_{\min} = \bar{k} = \theta_1 = k_{\max}$.

Proof:    Let ${\bf 1}$ be the vector with all entries equal to 1. Then $A {\bf 1} \le k_{\max} {\bf 1}$, and by (iv) of Perron-Frobenius we have $\theta_1 \le k_{\max}$ with equality if and only if $A {\bf 1} = \theta_1 {\bf 1}$, that is, if and only if $\Gamma$ is regular of degree $\theta_1$. This settles the case where $\Gamma$ is regular. If $\Gamma$ is not regular, then $k_{\min} < \bar{k} < k_{\max}$ and we have seen $\theta_1 < k_{\max}$. Finally, let $u$ be any nonzero vector. We show that

$$\theta_1 \ge {{ u^\top A u } \over { u^\top u }}$$

with equality if and only if $Au = \theta_1 u$. Indeed, let $u_1 , ... , u_v$ be an orthonormal basis of $V$ consisting of eigenvectors of $A$, so that $A u_j = \theta_j u_j$ ($1 \le j \le v$). Then we can write $u$ as a linear combination of the $u_j$, say $u = \sum_i a_i u_i$, and then $u^\top A u = \sum_i a_i^2 \theta_i \le \theta_1 \sum_i a_i^2 = \theta_1 u^\top u$. Applying this with $u = {\bf 1}$ we find $\theta_1 \ge {{\bar{k} v } \over v} = \bar{k}$, with equality if and only if $\Gamma$ is regular. $\Box$

Remark    Choosing the vector $u$ in the previous proof more subtly, we may obtain better bounds on $\theta_1$.

Exercise    Use interlacing (see below) to show that $\theta_1 \ge \sqrt{k_{\max}}$. When does equality hold?

The spectrum of a disconnected graph is easily found from the spectra of its components:

Proposition 1.4.3   Let $\Gamma$ be a graph with connected components $\Gamma_i$ ($1 \le i \le s$). Then the spectrum of $\Gamma$ is the union of the spectra of $\Gamma_i$ (and multiplicities are added). $\Box$

So, for not necessarily connected graphs, we have $\bar{k} \le \theta_1 \le k_{\max}$, and $\bar{k} = \theta_1$ if and only if $\Gamma$ is regular, but if $\theta_1 = k_{\max}$ then we only know that $\Gamma$ has a regular component with this valency, but $\Gamma$ need not be regular itself.

Exercise    Show that no (undirected) graph has eigenvalue $\sqrt{2 + \sqrt 5}$.