An interactive notebook

Spectral Graph Explorer

How does a collection of edges become a rate of agreement? Build a graph, give its vertices a signal, and follow the connection through its Laplacian.

Edges · m: 8
Components: 1
Connectivity · λ₂: 0.5858

Color shows eigenmode 2, relative to its mean.

Preserve edge count

Choose two vertices to add or remove their edge.

01 / Structure

The spectrum of L

Each bar is an eigenvalue. Choose one to see an associated eigenvector on the graph.

Selected modeλ₂ = 0.5858

The number of zero eigenvalues is the number of connected components. λ₂ is positive exactly when the graph is connected.

Eigenvector signs are arbitrary. Repeated eigenvalues admit many valid eigenvector bases; the displayed vector is one choice, not a canonical partition.

Inspect the Laplacian matrix L = D − A

Rows and columns use the graph’s vertex labels. Diagonal entries are degrees; −1 indicates an edge.
L	1	2	3	4	5	6	7	8
1	2	-1	0	0	0	0	0	-1
2	-1	2	-1	0	0	0	0	0
3	0	-1	2	-1	0	0	0	0
4	0	0	-1	2	-1	0	0	0
5	0	0	0	-1	2	-1	0	0
6	0	0	0	0	-1	2	-1	0
7	0	0	0	0	0	-1	2	-1
8	-1	0	0	0	0	0	-1	2

Simple, undirected, unweighted graphs. Values are numerical approximations, rounded for display. Editing evaluates the chosen graph; it does not certify a global optimum.

Behind the controls

One graph, three descriptions

The graph records who interacts. Its quadratic form measures disagreement. Its eigenvalues tell us how fast different patterns of disagreement disappear.

Definition

From edges to eigenvalues

For a simple, undirected, unweighted graph, $A$ is the adjacency matrix and $D$ records vertex degrees. The second-smallest eigenvalue of $L$ is its algebraic connectivity. It is positive exactly when the graph is connected.

L=D-A,\qquad 0=\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_n.

Classical spectral graph theory; Fiedler (1973).

Identity

A signal measures disagreement across edges

Assign a real value $x_i$ to each vertex. An edge contributes more energy when its endpoints disagree. Subtracting the mean leaves every edge difference unchanged; write $z=x-\bar{x}\mathbf{1}$ .

E(x)=x^{\mathsf T}Lx=\sum_{\{i,j\}\in E}(x_i-x_j)^2,\qquad \lambda_2=\min_{\substack{z\ne0\\z\perp\mathbf{1}}}\frac{E(z)}{\|z\|_2^2}.

Proof / derivation

Expand each squared edge difference and collect the terms at each vertex. The diagonal terms give $D$ and the cross terms give $-A$ .

Choose an orthonormal eigenbasis with $q_1=\mathbf{1}/\sqrt{n}$ . A centered signal has no $q_1$ component, so its Rayleigh quotient is a weighted average of the remaining eigenvalues. This also works for a disconnected graph, where more zero eigenvalues occur.

z=\sum_{k=2}^{n}c_kq_k\quad\Longrightarrow\quad \frac{z^{\mathsf T}Lz}{\|z\|_2^2} =\frac{\sum_{k=2}^{n}\lambda_k c_k^2}{\sum_{k=2}^{n}c_k^2}\geq\lambda_2.

Every nonconstant signal, after centering, gives an upper bound on the current graph's λ₂. It does not certify optimality among graphs.

Lemma

The slowest mode controls diffusion

Let every edge exchange signal at unit rate. The global mean stays fixed. For a connected graph, disagreement with that mean decays at least as fast as the envelope below; starting in a $\lambda_2$ eigenmode attains it.

\begin{aligned} \dot{x}&=-Lx,\qquad x(t)=\sum_{k=1}^{n}e^{-\lambda_k t}q_kq_k^{\mathsf T}x(0),\\[6pt] \|x(t)-\bar{x}\mathbf{1}\|_2&\leq e^{-\lambda_2t}\|x(0)-\bar{x}\mathbf{1}\|_2. \end{aligned}

Proof / derivation

Since $\mathbf{1}^{\mathsf T}L=0$ , the mean is constant. Diagonalizing $L$ turns the differential equation into independent scalar decays. Every nonconstant mode of a connected graph has eigenvalue at least $\lambda_2$ ; squaring its coefficient and summing proves the bound.

For a disconnected graph, each component keeps its own average. The same inequality holds with $\lambda_2=0$ , but it no longer guarantees convergence to a single global value.

An elementary consequence of the spectral decomposition. Time is dimensionless in this explorer.

A connection to the project

An extremal example you can inspect

The complete bipartite preset joins each of two vertices to all the others. Its spectrum, counted with multiplicity, is

\operatorname{spec} L(K_{2,n-2})=\{0,\underbrace{2,\ldots,2}_{n-3},n-2,n\},\qquad n\geq4.

The public theorem proves that no simple graph on the same number of vertices and exactly $2(n-2)$ edges has algebraic connectivity greater than 2. This makes $K_{2,n-2}$ a maximizer; it does not establish uniqueness. The numerical explorer lets you inspect this example, while the paper supplies the proof.

Read about the theorem study →

Constructions & connections

Build a graph from smaller pieces

Cartesian products combine graphs; Cayley graphs turn group operations into edges. Hypercubes connect the two constructions. Their spectra make these relationships explicit.

Definitions and spectral formulas

Identity

Cartesian products add spectra

The vertices of $G\square H$ are pairs $(u,v)$ . An edge changes exactly one coordinate along an edge of its factor. For simple, undirected graphs, the Laplacian is a Kronecker sum. Products of paths give grids; products of cycles give discrete tori.

\begin{aligned} L_{G\square H}&=L_G\otimes I_H+I_G\otimes L_H,\\[4pt] \mu_{ij}&=\lambda_i(G)+\lambda_j(H). \end{aligned}

Proof / derivation

If $L_Gu_i=\lambda_i(G)u_i$ and $L_Hv_j=\lambda_j(H)v_j$ , then $u_i\otimes v_j$ is a product eigenvector with eigenvalue $\mu_{ij}$ . These tensor products form a basis.

When both factors are connected and each has at least two vertices, the first positive sum is $\min\{\lambda_2(G),\lambda_2(H)\}$ . Thus the slower factor determines the product's algebraic connectivity.

Fiedler (1973), property 3.4. Pairwise sums must be sorted to obtain the ordered spectrum.

Identity

Cyclic Cayley graphs turn symmetry into Fourier modes

On $\mathbb Z_n$ with $n\geq2$ , choose $S=-S$ excluding zero and connect $x$ to $x+s$ modulo $n$ . The controls add both signs of each step, counting the half-turn $n/2$ once. This is the cyclic subfamily; Cayley graphs also exist on other groups.

\chi_k(x)=e^{2\pi i kx/n},\qquad \mu_k=|S|-\sum_{s\in S}\cos\!\left(\frac{2\pi ks}{n}\right), \quad k=0,\ldots,n-1.

Proof / derivation

Translation multiplies $\chi_k$ by a phase, giving adjacency eigenvalue $\sum_{s\in S}e^{2\pi i ks/n}$ . Subtract from degree $|S|$ and pair inverses to obtain the formula. These characters are one-dimensional group representations.

Paths reach the subgroup generated by $S$ . For nonempty $S$ , there are $\gcd(n,\{s:s\in S\})$ components: the graph is connected when this is 1. An empty set gives $n$ isolated vertices.

Godsil, Duality, §3.2. Frequencies k are not sorted; the explorer orders eigenvalues numerically.

Identity

The hypercube belongs to both constructions

For $d\geq1$ , the graph $Q_d$ joins binary strings differing in one bit. It is both a Cartesian product of $d$ copies of $K_2$ and a Cayley graph on $(\mathbb Z_2)^d$ , using the coordinate vectors as steps.

Q_d=\underbrace{K_2\square\cdots\square K_2}_{d\text{ factors}}, \qquad \lambda=2k\ \text{with multiplicity}\ \binom{d}{k},\quad 0\leq k\leq d.

Proof / derivation

Each $K_2$ factor contributes either 0 or 2 to a product eigenvalue. Choosing the nonconstant mode in exactly $k$ coordinates gives $2k$ , in $\binom{d}{k}$ ways.

Equivalently, the characters $\chi_a(x)=(-1)^{a\cdot x}$ are eigenvectors with eigenvalue $2|a|$ , where $|a|$ counts the nonzero bits of $a$ . This identifies the product eigenbasis with the group characters.

Elementary product-spectrum consequence; see Pirazzini's Yale notes (2025), Example 6 and Theorem 8, for the Cayley interpretation.

Reading & interpretation

The graph editor uses simple, undirected, unweighted graphs. Values are computed numerically for the graph on screen; the tool does not search for a globally optimal graph. An eigenvector can change sign, and a repeated eigenvalue has many valid choices of eigenbasis. The colors therefore illustrate one choice of mode, rather than a unique partition.

Miroslav Fiedler, Algebraic connectivity of graphs (1973) — classical definitions and variational properties.
Zhu, Li, Ren & Liu, arXiv:2608.07360v2 — the public extremal theorem, including the bipartite spectrum.

L	1	2	3	4	5	6	7	8
1	2	-1	0	0	0	0	0	-1
2	-1	2	-1	0	0	0	0	0
3	0	-1	2	-1	0	0	0	0
4	0	0	-1	2	-1	0	0	0
5	0	0	0	-1	2	-1	0	0
6	0	0	0	0	-1	2	-1	0
7	0	0	0	0	0	-1	2	-1
8	-1	0	0	0	0	0	-1	2

L	1	2	3	4	5	6	7	8
1	2	-1	0	0	0	0	0	-1
2	-1	2	-1	0	0	0	0	0
3	0	-1	2	-1	0	0	0	0
4	0	0	-1	2	-1	0	0	0
5	0	0	0	-1	2	-1	0	0
6	0	0	0	0	-1	2	-1	0
7	0	0	0	0	0	-1	2	-1
8	-1	0	0	0	0	0	-1	2

L	1	2	3	4	5	6	7	8
1	2	-1	0	0	0	0	0	-1
2	-1	2	-1	0	0	0	0	0
3	0	-1	2	-1	0	0	0	0
4	0	0	-1	2	-1	0	0	0
5	0	0	0	-1	2	-1	0	0
6	0	0	0	0	-1	2	-1	0
7	0	0	0	0	0	-1	2	-1
8	-1	0	0	0	0	0	-1	2