# Measuring the regularity of a graph by its Laplacian eigenvalues

Let ${G}$ be a graph with vertices ${1, 2, \dots, n}$. The degree of vertex ${i}$ is denoted ${d_i}$. Let ${L}$ be the Laplacian matrix of ${G}$, so that ${L_{ii}=d_i}$, ${L_{ij}}$ is ${-1}$ when the vertices ${i, j}$ are adjacent, and is ${0}$ otherwise. The eigenvalues of ${L}$ are written as ${\lambda_1\le \dots \le \lambda_n}$.

The graph is regular if all vertices have the same degree: ${d_1=\cdots = d_n}$. How can this property be seen from its Laplacian eigenvalues ${\lambda_1, \dots, \lambda_n}$?

Since the sum of eigenvalues is equal to the trace, we have ${\sum \lambda_i = \sum d_i}$. Moreover, ${\sum \lambda_i^2}$ is the trace of ${L^2}$, which is equal to the sum of the squares of all entries of ${L}$. This sum is ${\sum d_i^2 + \sum d_i}$ because the ${i}$th row of ${L}$ contains one entry equal to ${d_i}$ and ${d_i}$ entries equal to ${-1}$. In conclusion, ${\sum d_i^2 = \sum \lambda_i^2 - \sum\lambda_i}$.

The Cauchy-Schwarz inequality says that ${n\sum d_i^2 \ge \left(\sum d_i \right)^2}$ with equality if and only if all numbers ${d_i}$ are equal, i.e., the graph is regular. In terms of eigenvalues, this means that the difference $D =n\sum d_i^2 - \left(\sum d_i \right)^2 = n\sum (\lambda_i^2 - \lambda_i) - \left( \sum\lambda_i \right)^2$
is always nonnegative, and is equal to zero precisely when the graph is regular. This is how one can see the regularity of a graph from its Laplacian spectrum.

As an aside, ${D }$ is an even integer. Indeed, the sum ${\sum d_i}$ is even because it double-counts the edges. Hence the number of vertices of odd degree is even, which implies that ${\sum d_i^k }$ is even for every positive integer ${k }$.

Up to a constant factor, ${D}$ is simply the degree variance: the variance of the sequence ${d_1, \dots, d_n}$. What graph maximizes it for a given ${n}$? We want to have some very large degrees and some very small ones.

Let ${G_{m, n}}$ be the union of the complete graph ${K_m}$ on ${m}$ vertices and ${(n-m)}$ isolated vertices. The sum of degrees is ${m(m-1)}$ and the sum of squares of degrees is ${m(m-1)^2}$. Hence, ${D = nm(m-1)^2 - (m(m-1))^2 = m(m-1)^2(n-m)}$

For ${n=3, 4, 5, 6}$ the maximum is attained by ${m=n-1}$, that is there is one isolated vertex. For ${n=7, 8, 9, 10}$ the maximum is ${m=n-2}$. In general it is attained by ${m^*=\lfloor (3n+2)/4 \rfloor}$.

The graph ${G_{m, n}}$ is disconnected. But any graph has the same degree variance as its complement. And the complement ${G^c(m, n)}$ is always connected: it consists of a “center”, a complete graph on ${n-m}$ vertices, and “periphery”, a set of ${m}$ vertices that are connected to each central vertex. Put another way, ${G^c(m, n)}$ is obtained from the complete bipartite graph ${K_{m, n-m}}$ by connecting all vertices of the ${n-m}$ group together.

Tom A. B. Snijders (1981) proved that ${G(m^*, n)}$ and ${G^c(m^*, n)}$ are the only graphs maximizing the degree variance; in particular, ${G^c(m^*, n)}$ is the unique maximizer among the connected graphs. It is pictured below for ${n=4, \dots, 9}$.