This is a collection of entirely unoriginal remarks about Laplacian spectrum of graphs. For an accessible overview of the subject I recommend the M.S. thesis The Laplacian Spectrum of Graphs by Michael William Newman. It also includes a large table of graphs with their spectra. Here I will avoid introducing matrices and enumerating vertices.
Let be the vertex set of a graph. Write
if
are adjacent vertices. Given a function
, define
.
This is a linear operator (the graph Laplacian) on the Euclidean space of all functions
with the norm
. It is symmetric:
and positive semidefinite:
. Since equality is attained for constant
, 0 is always an eigenvalue of
.
This is the standard setup, but I prefer to change things a little and replace by the smaller space
of functions with zero mean:
. Indeed,
maps
to
anyway, and since it kills the constants, it makes sense to focus on
. It is a vector space of dimension
where
.
One advantage is that the smallest eigenvalue is 0 if and only if the graph is disconnected: indeed, is equivalent to
being constant on each connected component. We also gain better symmetry between
and the Laplacian of the graph complement, denoted
. Indeed, since
, it follows that
for every
. So, the identity
holds on
(it does not hold on
). Hence the eigenvalues of
are obtained by subtracting the eigenvalues of
from
. As a corollary, the largest eigenvalue of
is at most
, with equality if and only if the graph complement is disconnected. More precisely, the multiplicity of eigenvalue
is one less than the number of connected components of the graph complement.
Let denote the diameter of the graph. Then the number of distinct Laplacian eigenvalues is at least
. Indeed, let
be two vertices at distance
from each other. Define
and
elsewhere. Also let
for
. Note that
for all
. One can prove by induction that
when the distance from
to
is greater than
, and
when the distance from
to
is equal to
. In particular,
when
and
. This shows that
is not a linear combination of
. Since
, it follows that
is not a linear combination of
. Hence the minimal polynomial of
has degree at least
, which implies the claim.
Let’s consider a few examples of connected graphs.
3 vertices
There are two connected graphs: the 3-path (D=2) and the 3-cycle (D=1). In both cases we get D distinct eigenvalues. The spectra are [1, 3] and [3, 3], respectively.
4 vertices
- One graph of diameter 3, the path. Its spectrum is
.
- One graph of diameter 1, the complete graph. Its spectrum is
. This pattern continues for other complete graphs: since the complement is the empty graph (
components), all
eigenvalues are equal to
.
- Four graphs of diameter 2, which are shown below, with each caption being the spectrum.




Remarks:
- The graph [1, 3, 4] has more distinct eigenvalues than its diameter.
- The graph [2, 2, 4] is regular (all vertices have the same degree).
- The smallest eigenvalue of graphs [1, 1, 4] and [2, 2, 4] is multiple, due to the graphs having a large group of automorphisms (here rotations); applying some of these automorphisms to an eigenfunctions for the smallest eigenvalue yields another eigenfunction.
- [1, 3, 4] and [2, 4, 4] also have automorphisms, but their automorphisms preserve the eigenfunction for the lowest eigenvalue, up to a constant factor.
5 vertices
- One graph of diameter 4, the path. Its spectrum is related to the golden ratio: it consists of
.
- One graph of diameter 1, the complete one: [5, 5, 5, 5]
- Five graphs of diameter 3. All have connected complement, with the highest eigenvalue strictly between 4 and 5. None are regular. Each has 4 distinct eigenvalues.
- 14 graphs of diameter 2. Some of these are noted below.
Two have connected complement, so their eigenvalues are less than 5 (spectrum shown on hover):
One has both integers and non-integers in its spectrum, the smallest such graph. Its eigenvalues are .

Two have eigenvalues of multiplicity 3, indicating a high degree of symmetry (spectrum shown on hover).
Two have all eigenvalues integer and distinct:
The 5-cycle and the complete graph are the only regular graphs on 5 vertices.
6 vertices
This is where we first encounter isospectral graphs: the Laplacian spectrum cannot tell them apart.
Both of these have spectrum but they are obviously non-isomorphic (consider the vertex degrees):
Both have these have spectrum and are non-isomorphic.
Indeed, the second pair is obtained from the first by taking graph complement.
Also notable are regular graphs on 6 vertices, all of which have integer spectrum.





Here [3, 3, 3, 3, 6] (complete bipartite) and [2, 3, 3, 5, 5] (prism) are both regular of degree 3, but the spectrum allows us to tell them apart.
The prism is the smallest regular graph for which the first eigenvalue is a simple one. It has plenty of automorphisms, but the relevant eigenfunction (1 on one face of the prism, -1 on the other face) is compatible with all of them.
7 vertices
There are four regular graphs on 7 vertices. Two of them are by now familiar: 7-cycle and complete graph. Here are the other two, both regular of degree 4 but with different spectra.


There are lots of isospectral pairs of graphs on 7 vertices, so I will list only the isospectral triples, of which there are five.
Spectrum 0.676596, 2, 3, 3.642074, 5, 5.681331:
Spectrum 0.726927, 2, 3.140435, 4, 4, 6.132637:
Spectrum 0.867363, 3, 3, 3.859565, 5, 6.273073:
Spectrum 1.318669, 2, 3.357926, 4, 5, 6.323404:
All of the triples mentioned so far have connected complement: for example, taking the complement of the triple with the spectrum [0.676596, 2, 3, 3.642074, 5, 5.681331] turns it into the triple with the spectrum [1.318669, 2, 3.357926, 4, 5, 6.323404].
Last but not least, an isospectral triple with an integer spectrum: 3, 4, 4, 6, 6, 7. This one has no counterpart since the complement of each of these graphs is disconnected.
8 vertices
Regular graphs, excluding the cycle (spectrum 0.585786, 0.585786, 2, 2, 3.414214, 3.414214, 4) and the complete one.
Degree 3 regular:




5.414214

5.414214
Degree 4 regular






Degree 5 regular



Degree 6 regular

Credits: the list of graphs by Brendan McKay and NetworkX library specifically the methods read_graph6 (to read the files provided by Prof. McKay), laplacian_spectrum, diameter, degree, and draw.