Let be a graph with vertices . The degree of vertex is denoted . Let be the Laplacian matrix of , so that , is when the vertices are adjacent, and is otherwise. The eigenvalues of are written as .
The graph is regular if all vertices have the same degree: . How can this property be seen from its Laplacian eigenvalues ?
Since the sum of eigenvalues is equal to the trace, we have . Moreover, is the trace of , which is equal to the sum of the squares of all entries of . This sum is because the th row of contains one entry equal to and entries equal to . In conclusion, .
The Cauchy-Schwarz inequality says that with equality if and only if all numbers are equal, i.e., the graph is regular. In terms of eigenvalues, this means that the difference
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, is an even integer. Indeed, the sum is even because it double-counts the edges. Hence the number of vertices of odd degree is even, which implies that is even for every positive integer .
Up to a constant factor, is simply the degree variance: the variance of the sequence . What graph maximizes it for a given ? We want to have some very large degrees and some very small ones.
Let be the union of the complete graph on vertices and isolated vertices. The sum of degrees is and the sum of squares of degrees is . Hence,
For the maximum is attained by , that is there is one isolated vertex. For the maximum is . In general it is attained by .
The graph is disconnected. But any graph has the same degree variance as its complement. And the complement is always connected: it consists of a “center”, a complete graph on vertices, and “periphery”, a set of vertices that are connected to each central vertex. Put another way, is obtained from the complete bipartite graph by connecting all vertices of the group together.
Tom A. B. Snijders (1981) proved that and are the only graphs maximizing the degree variance; in particular, is the unique maximizer among the connected graphs. It is pictured below for .