Jamie Little

The ordinary Fourier transform decomposes a signal into frequencies, and “frequency” makes intuitive sense when your signal lives on a line or a circle: it’s how fast a sine wave oscillates as you walk along that line. But plenty of data doesn’t live on a line. Sensor readings sit on the nodes of a sensor network. Traffic measurements sit on a road graph. A signal on a social network is one number per user, connected in whatever irregular way friendships happen to connect them. There’s no natural direction to walk in, so “how fast does this oscillate” stops meaning anything obvious.

And yet there’s a well defined way to talk about frequency on a graph, and it turns out to be exactly the machinery from the last article. The eigenvectors of the graph Laplacian play the same role that sine and cosine waves play for ordinary Fourier analysis, and the connection isn’t just an analogy, it’s the same underlying idea (decomposing a signal into the eigenbasis of a particular operator) applied to two different domains, one continuous and one discrete.

Part 1: what frequency actually is

Start with a periodic function $f$ on the circle, meaning $f(x) = f(x + 2\pi)$. The building blocks of its Fourier series are the complex exponentials $e^{ikx}$ for integer $k$. Differentiate one twice:

$\frac{d}{dx} e^{ikx} = ik \, e^{ikx}, \qquad \frac{d^2}{dx^2} e^{ikx} = (ik)^2 e^{ikx} = -k^2 e^{ikx}$

So $e^{ikx}$ is an eigenfunction of the second-derivative operator, with eigenvalue $-k^2$. Flip the sign and write $\mathcal{L} = -\dfrac{d^2}{dx^2}$ (calling it $\mathcal{L}$ deliberately, this is the continuous Laplacian), and

$\mathcal{L} \, e^{ikx} = k^2 \, e^{ikx}$

This is the entire content of the claim “sinusoids are the natural frequency basis”: they are, quite literally, the eigenfunctions of the Laplacian operator, and the eigenvalue $k^2$ is what we’ve been informally calling the frequency squared. The Fourier transform isn’t a separate piece of machinery bolted onto calculus, it’s an eigendecomposition.

Why the Laplacian specifically, and not some other operator? Because $\mathcal{L}$ measures local roughness. For a function $f$, the Dirichlet energy $\int |f'(x)|^2 \, dx$ quantifies how much $f$ oscillates: a flat function has zero Dirichlet energy, a wildly oscillating one has a large one. Expand $f$ in its Fourier series, $f(x) = \sum_k c_k e^{ikx}$, differentiate term by term, and use the orthogonality relation $\int_0^{2\pi} e^{ikx} e^{-ijx}\,dx = 2\pi \, \delta_{kj}$:

$\int_0^{2\pi} |f'(x)|^2\, dx = \sum_k \sum_j c_k \overline{c_j} (ik)(\overline{ij}) \int_0^{2\pi} e^{i(k-j)x}\,dx = 2\pi \sum_k k^2 |c_k|^2$

The cross terms vanish by orthogonality, and what survives is a direct correspondence: the roughness of $f$ is exactly a weighted sum of its Fourier coefficients, weighted by $k^2$, the eigenvalue attached to each mode. High-frequency modes carry more of the roughness, low-frequency modes carry less, and the constant mode $k=0$ carries none at all. Frequency, roughness, and eigenvalue of the Laplacian are three names for the same quantity.

That last identity is the thread to pull on. It doesn’t actually use anything about the circle specifically, translation invariance, periodicity, none of it enters the argument. All it needs is an operator that measures roughness and a basis that diagonalises it. A graph has no translations to speak of, but it absolutely has a notion of roughness, and it has an operator to match.

Part 2: the graph version

A graph signal is just a function $f : V \to \mathbb{R}$, one real number per vertex. The graph Laplacian from before, $L = D - A$, is the discrete stand-in for $\mathcal{L}$, and the parallel to Dirichlet energy is immediate. For any signal $f$,

$f^\top L f = \sum_{(i,j) \in E} (f_i - f_j)^2$

This is a direct calculation: $f^\top L f = f^\top D f - f^\top A f = \sum_i d_i f_i^2 - \sum_{(i,j)\in E} 2 f_i f_j$, and regrouping the sum edge by edge turns this into $\sum_{(i,j)\in E}(f_i-f_j)^2$. It’s non-negative for every $f$ (it’s a sum of squares), which is why $L$ is positive semidefinite, and it’s the exact discrete analogue of $\int |f'|^2\,dx$: instead of measuring how much $f$ changes over an infinitesimal step along a line, it measures how much $f$ changes across each edge of the graph.

Because $L$ is real and symmetric, the spectral theorem guarantees an orthonormal basis of eigenvectors $u_1, \dots, u_n$ with real eigenvalues $0 = \lambda_1 \le \lambda_2 \le \cdots \le \lambda_n$. Collect the eigenvectors as columns of an orthogonal matrix $U$. The Graph Fourier Transform of a signal $f$ is defined as

$\hat{f} = U^\top f, \qquad f = U \hat{f} = \sum_k \hat{f}_k \, u_k$

exactly mirroring the Fourier series, a signal written as a weighted sum of fixed basis modes. And because $f = U\hat{f}$ diagonalises the quadratic form,

$f^\top L f = (U\hat f)^\top L (U\hat f) = \hat f^\top (U^\top L U) \hat f = \hat f^\top \Lambda \hat f = \sum_k \lambda_k \, \hat{f}_k^2$

which is the discrete Parseval identity: total roughness equals the sum of squared Fourier coefficients weighted by eigenvalue, the same relationship derived above for the circle, except the finite-dimensional version falls out in one line of linear algebra instead of an integration by parts. The eigenvalue $\lambda_k$ is the graph’s notion of $k^2$: small $\lambda_k$ means the eigenvector $u_k$ is nearly constant across every edge (low frequency, smooth), large $\lambda_k$ means $u_k$ flips sign or swings wildly between neighbours (high frequency, rough). The smallest eigenvalue is always $\lambda_1 = 0$, achieved by the constant vector (every row of $L$ sums to zero), playing the role of the $k=0$ DC component in the continuous case.

Part 3: an exact case where the analogy is not an analogy

For most graphs the eigenvectors of $L$ have no closed form, you compute them numerically and that’s that. But for one important family, the cycle graph $C_n$ (vertices $0, \dots, n-1$ arranged in a ring, each connected to its two neighbours), the eigenvectors work out exactly, and they turn out to be the classical discrete Fourier basis itself.

The Laplacian of $C_n$ has a special structure: every row is the previous row shifted over by one, because every vertex looks identical to every other vertex up to relabelling. A matrix with this property is called circulant: $C_{jk} = c_{(k-j)\bmod n}$ for some fixed sequence $c_0, \dots, c_{n-1}$ (the “first row”).

Claim. Every circulant matrix has eigenvectors $v_m = (1, \omega^m, \omega^{2m}, \dots, \omega^{(n-1)m})$, for $m = 0, \dots, n-1$, where $\omega = e^{2\pi i/n}$, with eigenvalue $\mu_m = \sum_{l=0}^{n-1} c_l \, \omega^{ml}$.

Proof. Compute the $j$-th entry of $Cv_m$ directly:

$(Cv_m)_j = \sum_{k=0}^{n-1} C_{jk} (v_m)_k = \sum_{k=0}^{n-1} c_{(k-j)\bmod n} \, \omega^{mk}$

Substitute $l = (k-j) \bmod n$, so $k \equiv j + l \pmod n$ and $\omega^{mk} = \omega^{m(j+l)} = \omega^{mj}\omega^{ml}$ (this holds even across the wraparound because $\omega^n = 1$). As $k$ ranges over $0, \dots, n-1$, $l$ ranges over the same set, so

$(Cv_m)_j = \sum_{l=0}^{n-1} c_l \, \omega^{mj}\omega^{ml} = \omega^{mj} \sum_{l=0}^{n-1} c_l \,\omega^{ml} = \mu_m \, (v_m)_j$

for every $j$, so $Cv_m = \mu_m v_m$. $\blacksquare$

This proof used nothing about $C_n$ specifically, it’s a general fact about any circulant matrix. Now apply it. The Laplacian of $C_n$ has first row $c_0 = 2$ (the degree), $c_1 = -1$ (the clockwise neighbour), $c_{n-1} = -1$ (the counterclockwise neighbour), and zero everywhere else. Plugging into the formula for $\mu_m$:

$\mu_m = 2 - \omega^m - \omega^{-m} = 2 - 2\cos\!\left(\frac{2\pi m}{n}\right) = 4\sin^2\!\left(\frac{\pi m}{n}\right)$

using $\omega^m + \omega^{-m} = 2\cos(2\pi m/n)$ and the half-angle identity $1 - \cos\theta = 2\sin^2(\theta/2)$. So the eigenvalues of the cycle Laplacian are $\lambda_m = 4\sin^2(\pi m/n)$, and the eigenvectors are $v_m(j) = \omega^{mj} = e^{2\pi i mj/n}$: the exact complex exponential basis of the classical discrete Fourier transform, on the nose. On a cycle, the Graph Fourier Transform is the DFT, not an analogue of it. (Pairing up $m$ and $n-m$, which share the same eigenvalue since $\sin^2$ is symmetric about $\pi/2$, and taking real and imaginary parts recovers real sine and cosine eigenvectors, exactly as combining $e^{ikx}$ and $e^{-ikx}$ recovers real sinusoids in the continuous case.)

As a check, take $n=4$: $\lambda_m = 4\sin^2(\pi m/4)$ gives $\lambda_0 = 0$, $\lambda_1 = 4 \cdot \tfrac12 = 2$, $\lambda_2 = 4 \cdot 1 = 4$, $\lambda_3 = 4 \cdot \tfrac12 = 2$. Four vertices, eigenvalues $\{0, 2, 4, 2\}$, one zero mode, two mirror-image frequency-1 modes at $\lambda = 2$, and one fastest-oscillating mode at $\lambda = 4$ where adjacent vertices alternate sign. That last one is the graph equivalent of the highest frequency a 4-sample signal can represent, the discrete analogue of the Nyquist limit.

Part 4: a worked example on an irregular graph

Cycles are convenient because of the symmetry, but the whole point of the graph Fourier transform is that it works on graphs with no symmetry at all. The diamond graph from the spanning tree article (vertices $1,2,3,4$, edges $12,13,14,23,24$) has less symmetry than a cycle but still enough to get a clean answer by hand, using its automorphisms directly: swapping vertices $1 \leftrightarrow 2$ leaves the graph unchanged, and so does swapping $3 \leftrightarrow 4$, independently. Any eigenvector must be symmetric or antisymmetric under each of those swaps, which splits the $4\times 4$ eigenvalue problem into small independent pieces.

Solving each piece (the algebra is routine, so only the results are shown) gives eigenvalues $\{0, 2, 4, 4\}$ with orthogonal eigenvectors

$u_1 = \tfrac{1}{2}(1,1,1,1), \quad u_2 = \tfrac{1}{\sqrt2}(0,0,1,-1), \quad u_3 = \tfrac{1}{2}(1,1,-1,-1), \quad u_4 = \tfrac{1}{\sqrt2}(1,-1,0,0)$

$u_1$ is the constant mode, zero frequency, as always. $u_2$ oscillates only between the two low-degree vertices $3$ and $4$. $u_3$ and $u_4$ both sit at the top eigenvalue $\lambda = 4$, the fastest disagreement the graph can support, one splitting the high-degree pair from the low-degree pair, the other splitting the two high-degree vertices from each other.

Take a signal, say a temperature reading at each vertex: $f = (10, 8, 3, 1)$. Its graph Fourier transform is $\hat f = U^\top f$:

$\hat f_1 = u_1 \cdot f = \tfrac12(22) = 11, \quad \hat f_2 = u_2\cdot f = \tfrac{1}{\sqrt2}(2) = \sqrt2$ $\hat f_3 = u_3\cdot f = \tfrac12(14) = 7, \quad \hat f_4 = u_4\cdot f = \tfrac{1}{\sqrt2}(2) = \sqrt2$

The dominant coefficient is $\hat f_1 = 11$, the mean level of the signal, exactly as the DC term dominates a smooth continuous signal. The two $\lambda=4$ coefficients are comparatively small, meaning the signal doesn’t disagree much between the high-degree pair or between the low-degree pair, most of the actual variation is captured by the low and mid frequency terms.

Low-pass filtering. Attenuating the high-frequency coefficients and reconstructing is exactly what a graph low-pass filter does. Zeroing out the $\lambda=4$ terms entirely and inverting:

$f_{\text{filtered}} = \hat f_1 u_1 + \hat f_2 u_2 = 11\cdot\tfrac12(1,1,1,1) + \sqrt2\cdot\tfrac{1}{\sqrt2}(0,0,1,-1) = (5.5,\, 5.5,\, 6.5,\, 4.5)$

The sharp local disagreements are smoothed out while the overall shape of the signal (high near vertices 1,2, tapering toward 3,4) survives. This is the same operation as blurring an image, just performed on an arbitrary graph instead of a pixel grid.

Part 5: filtering is diffusion

The low-pass filter above was done by hand, picking which coefficients to zero out. There’s a more principled way to choose the attenuation, and it comes from the same operator playing a third role: governing diffusion.

The continuous heat equation $\partial u/\partial t = -\mathcal{L}u$ describes how heat spreads out over time. Solved in the Fourier basis, each mode decays independently: $u(x,t) = \sum_k c_k(0) \, e^{-k^2 t} \, e^{ikx}$, high-frequency components (large $k^2$) die out fast, low-frequency components persist. That’s why heat diffusion looks like blurring: it’s a low-pass filter that runs continuously in time rather than being applied in one discrete step.

The graph version is identical in structure. The graph heat equation $\dot u = -Lu$ has solution $u(t) = e^{-tL} u(0)$, and expanding in the eigenbasis,

$u(t) = \sum_k e^{-t\lambda_k} \, \hat u_k(0) \, u_k$

Each graph-frequency component decays at a rate set by its own eigenvalue, exactly mirroring the continuous case term for term. Letting this run for a short time $t$ is a low-pass filter, a soft, continuously tunable version of the hard cutoff used in the worked example above: instead of zeroing high-frequency coefficients outright, they’re scaled down by $e^{-t\lambda_k}$, with larger $t$ suppressing more of the spectrum. Graph filtering and graph diffusion aren’t two separate applications sitting next to each other, they’re the same computation, viewed either as a signal-processing operation or as a physical process running on the graph.

Where the analogy breaks

The comparison holds up remarkably well, but it isn’t perfect. The circle has translation symmetry: shifting a function and then Fourier transforming gives the same result as transforming and then shifting, and this is exactly why the same $e^{ikx}$ basis works everywhere on the circle regardless of where you start counting. Most graphs have no such symmetry (the diamond graph example only had it because of its particular automorphisms), so the graph Fourier basis is tied to the specific graph you built it from. There’s no universal graph-frequency basis the way there’s a universal continuous one, every graph gets its own, computed from its own Laplacian. The idea generalises cleanly; the specific basis functions do not.

Take a connected graph and ask a simple question: how many different spanning trees does it have? A spanning tree is a subset of edges that connects every vertex with no cycles, the minimum skeleton that holds the graph together. For a small graph you can just draw them all out. For anything larger, enumeration is hopeless, the count grows combinatorially and there’s no obvious shortcut.

Except there is one, and it’s a genuinely strange one. Build a specific matrix out of the graph, delete any row and the matching column, and take the determinant. That number is exactly the count of spanning trees. No enumeration, no search, just linear algebra. This is Kirchhoff’s theorem, usually called the Matrix-Tree theorem, and it’s worth understanding both because the result is surprising and because the proof is a clean piece of reasoning that ties together incidence matrices, the Cauchy-Binet formula, and a simple induction on leaves.

A known case, for scale

Before building the general machinery, it helps to have a reference point. For the complete graph on $n$ vertices, $K_n$, Cayley’s formula gives the count directly:

$\tau(K_n) = n^{n-2}$

For $K_4$ that’s $4^2 = 16$ spanning trees. Cayley’s formula only works for complete graphs, though, and most graphs aren’t complete. What we want is a method that works for any connected graph, and ideally one that’s fast: enumerating spanning trees directly takes exponential time, but as we’ll see, computing a determinant does not.

The Laplacian matrix

Given a graph $G$ with $n$ vertices, define the Laplacian matrix $L$ as

$L = D - A$

where $D$ is the diagonal degree matrix (the degree of vertex $i$ on the diagonal) and $A$ is the adjacency matrix. Concretely, for vertices $i \neq j$, $L_{ij} = -1$ if there’s an edge between $i$ and $j$ and $0$ otherwise, and $L_{ii}$ equals the degree of vertex $i$. Every row sums to zero by construction, which already tells you $L$ is singular: the all-ones vector is in its kernel.

This matrix shows up constantly in graph theory (spectral clustering, random walks, the graph Fourier transform) but the property we care about here is the one Kirchhoff noticed in 1847, in the context of electrical circuits rather than graph theory as we’d now call it.

The theorem

Kirchhoff’s theorem. Let $L$ be the Laplacian of a connected graph $G$ on $n$ vertices. Delete any row $i$ and column $i$ from $L$ to get an $(n-1) \times (n-1)$ matrix $L_i$. Then

$\det(L_i) = \tau(G)$

the number of spanning trees of $G$, and this value doesn’t depend on which row/column you deleted.

That last part, the independence from choice of $i$, is a nice corollary of the proof rather than something you need to assume. All $n$ cofactors of $L$ are equal.

Building the proof: incidence matrices

The proof runs through a second matrix, the oriented incidence matrix $B$. Pick an arbitrary orientation for each edge of $G$ (which endpoint is the “head” and which is the “tail” is irrelevant to the final count, it’s just bookkeeping). $B$ is $n \times m$, one row per vertex and one column per edge, where for edge $e_k$ from vertex $i$ to vertex $j$:

$B_{i,k} = -1, \quad B_{j,k} = +1, \quad B_{\ell,k} = 0 \text{ for all other } \ell$

A short computation shows $BB^\top = L$, regardless of which orientation you picked (flipping an edge’s direction flips the sign of an entire column, which doesn’t change $BB^\top$). This is the bridge between the combinatorial structure of the graph and the determinant we want to compute.

Now delete row $n$ from $B$ to get $B_0$, an $(n-1) \times m$ matrix. Deleting a row of $B$ before multiplying by its transpose has the same effect as deleting the matching row and column from $L$ afterward, so

$L_n = B_0 B_0^\top$

where $L_n$ is exactly the reduced Laplacian from the theorem statement, with row and column $n$ removed.

Cauchy-Binet does the heavy lifting

The Cauchy-Binet formula generalises the familiar $\det(XY) = \det(X)\det(Y)$ to non-square matrices. For a $p \times m$ matrix $X$ with $m \geq p$,

$\det(XX^\top) = \sum_{S} \det(X[:,S])^2$

where the sum runs over all $\binom{m}{p}$ subsets $S$ of $p$ columns, and $X[:,S]$ is the $p \times p$ submatrix formed by keeping only those columns.

Apply this to $B_0$, which is $(n-1) \times m$:

$\det(L_n) = \det(B_0 B_0^\top) = \sum_{S : |S| = n-1} \det(B_0[:,S])^2$

The sum is over every possible way of choosing $n-1$ edges out of the graph’s $m$ edges. This is already suggestive: we’re summing a square over all $(n-1)$-edge subsets, and spanning trees are exactly the $(n-1)$-edge subsets that hold the graph together. The remaining work is to show that each term in the sum is $1$ if the edges form a spanning tree and $0$ otherwise.

The lemma: trees give ±1, cycles give 0

Claim. Let $S$ be a set of $n-1$ edges. Then $\det(B_0[:,S]) = \pm 1$ if $S$ is a spanning tree of $G$, and $\det(B_0[:,S]) = 0$ otherwise.

First, notice that with exactly $n-1$ edges on $n$ vertices, there are only two possibilities. Either $S$ is a forest, in which case a forest with $n$ vertices and $n-1$ edges can only have one component (a forest with $k$ components has $n-k$ edges, and $n-k = n-1$ forces $k=1$), meaning $S$ is a spanning tree. Or $S$ isn’t a forest, in which case it contains a cycle. There’s no third option.

Case 1: $S$ contains a cycle. Orient the cycle consistently in one direction. Walking around it and summing the incidence columns with a $+1$ or $-1$ depending on whether each edge’s stored orientation agrees with the walking direction produces the zero vector: every vertex on the cycle gets one $+1$ contribution and one $-1$ contribution from its two cycle edges, which cancel. This is a nontrivial linear dependence among the columns of $B_0[:,S]$ restricted to the cycle’s edges, so those columns, and therefore all of $B_0[:,S]$, are linearly dependent. The determinant is $0$.

Case 2: $S$ is a spanning tree. This goes by induction on $n$. The base case $n=1$ is a single vertex with no edges, an empty $0 \times 0$ matrix, whose determinant is $1$ by convention, matching the single (trivial) spanning tree of a one-vertex graph.

For the inductive step, recall that any tree with two or more vertices has at least two leaves (vertices of degree 1). Since row $n$ was already deleted from $B_0$, pick a leaf $v \neq n$ (at least one of the tree’s leaves must differ from $n$, since a tree has at least two). Vertex $v$ touches exactly one edge of $S$, call it $e$. In the matrix $B_0[:,S]$, row $v$ therefore has exactly one nonzero entry, $\pm 1$, in the column for $e$, and zeros everywhere else.

Expanding the determinant along row $v$ gives $\det(B_0[:,S]) = \pm 1 \cdot \det(M')$, where $M'$ is the matrix left after deleting row $v$ and column $e$. But that’s exactly the incidence-derived matrix you’d build for the smaller graph $G - v$ (remove the leaf and its edge), using the spanning tree $S \setminus \{e\}$, with row $n$ still excluded. By the inductive hypothesis, $\det(M') = \pm 1$. So $\det(B_0[:,S]) = \pm 1$.

That closes the lemma. Substituting back into the Cauchy-Binet sum:

$\det(L_n) = \sum_{S \text{ spanning tree}} (\pm 1)^2 + \sum_{S \text{ contains a cycle}} 0^2 = \tau(G)$

Every spanning tree contributes exactly $1$, everything else contributes $0$, and the sum is just a count. That’s the theorem. The argument never used the fact that we deleted row $n$ specifically, relabelling vertices shows the same holds for any deleted row/column, which is why all cofactors agree.

Worked example

Take the graph on vertices $\{1,2,3,4\}$ with edges $\{12, 13, 14, 23, 24\}$, which is $K_4$ with the edge between $3$ and $4$ removed (sometimes called the diamond graph). Degrees are $3, 3, 2, 2$.

$L = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \end{pmatrix}$

Delete row 4 and column 4:

$L_4 = \begin{pmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 2 \end{pmatrix}$

$\det(L_4) = 3(3\cdot2 - (-1)(-1)) - (-1)((-1)\cdot2 - (-1)(-1)) + (-1)((-1)(-1) - 3(-1)) = 15 - 3 - 4 = 8$

So the theorem predicts 8 spanning trees. That’s checkable independently: $K_4$ has 16 spanning trees total (Cayley’s formula), and by the symmetry of $K_4$ every one of its 6 edges appears in the same number of them. Each tree has 3 edges, so summing edge-appearances across all 16 trees gives $16 \times 3 = 48$, spread evenly over 6 edges, meaning each edge appears in $48/6 = 8$ trees. The trees that survive removing edge $34$ are exactly the ones that never used it: $16 - 8 = 8$. Both routes agree.

Why this beats enumeration

The determinant of an $n \times n$ matrix can be computed via Gaussian elimination in $O(n^3)$ time. Directly enumerating spanning trees, by contrast, is exponential in the worst case, the number of trees itself grows exponentially (a dense graph on 20 vertices can easily have trillions of spanning trees), so no algorithm that lists them one at a time can keep up. The Matrix-Tree theorem sidesteps the listing entirely: it gets the count out of a computation whose cost barely notices how large that count is.

Electrical networks: where the same matrix reappears

Kirchhoff didn’t arrive at this theorem through graph theory. He was analysing resistor networks, and the Laplacian shows up there too, under a different name, as the conductance matrix. If every edge is a 1-ohm resistor, injecting current at one node and extracting it at another produces node voltages governed by exactly the linear system $Lv = i_{\text{ext}}$ (with one node grounded as a reference, since $L$ itself is singular).

Solving that system with Cramer’s rule brings back the same cofactors that count spanning trees, and the result is a second classical formula, also due to Kirchhoff: the effective resistance between nodes $a$ and $b$ is

$R_{\text{eff}}(a,b) = \frac{T_{a,b}(G)}{\tau(G)}$

where $\tau(G)$ is the total spanning tree count as before, and $T_{a,b}(G)$ counts spanning 2-forests that separate $a$ and $b$: subsets of $n-2$ edges that form exactly two trees covering all $n$ vertices between them, with $a$ in one and $b$ in the other. The derivation follows the same Cauchy-Binet pattern as the main proof, just applied to the numerator and denominator of Cramer’s rule instead of to a single determinant, so it won’t be repeated in full here, but the machinery is identical.

Checking this against the diamond graph: we already know $\tau(G) = 8$. For $T_{3,4}(G)$, count the 2-edge forests that put vertices 3 and 4 in different components. There are $\binom{5}{2} = 10$ ways to choose 2 edges from the graph’s 5 edges, and since no two edges share both endpoints, every pair is automatically a forest. Going through all 10 pairs, 8 of them separate vertex 3 from vertex 4, and only the two pairs that route both edges through a single shared vertex adjacent to both (${13,14}$ and ${23,24}$) keep 3 and 4 in the same component. So $T_{3,4}(G) = 8$, giving

$R_{\text{eff}}(3,4) = \frac{8}{8} = 1 \text{ ohm}$

Solving the circuit directly, by writing out Kirchhoff’s current law at each node with 1 amp injected at vertex 3 and extracted at vertex 4, and grounding vertex 2, confirms the same answer: $V_3 - V_4 = 1$. The graph-counting formula and the direct circuit solution land on the same number, because they’re computing the same determinant from two different starting points.

The broader pattern

What makes this theorem satisfying isn’t just that the formula works, it’s that a single matrix, built from purely local information (which vertices are adjacent to which), encodes a global combinatorial count that has no obvious reason to be computable so cheaply. The same object, reduced the same way, also happens to answer a completely different physical question about current flow. That’s not a coincidence so much as a reflection of the fact that spanning trees and current flow are, underneath, the same linear algebra: both are asking how many independent ways there are to route a single unit of flow through a graph without creating a cycle.

Open a Python shell and type 0.1 + 0.2. You get 0.30000000000000004. This is not a Python bug, not a CPU bug, and not something that better software engineering would fix. It is a direct consequence of what real numbers are, and no amount of additional hardware could ever fully resolve it.

The rest of this article explains why, how we work around it, and whether anything better is on the horizon.

The mathematical problem is permanent

The real numbers are uncountably infinite. That’s a specific technical claim, not just “very large”. Georg Cantor proved in 1874 that there is no bijection (no one-to-one correspondence) between the real numbers and the natural numbers. You cannot pair them up, even with infinitely many naturals to work with.

The proof is the diagonal argument. Suppose you claimed to have a complete list of all real numbers between 0 and 1, written as infinite binary expansions. Cantor constructs a number not on your list: take the first digit of the first number and flip it, take the second digit of the second number and flip it, and so on. The resulting number differs from every entry on your list in at least one position. So your list was never complete. And this holds regardless of what list you produce.

Now: a computer with $n$ bits can represent exactly $2^n$ distinct values. This is a finite set. No matter how large $n$ is (32, 64, a million), it is finite, and therefore the representable values form a set that is not only much smaller than the reals, but qualitatively different. The reals are uncountable; any finite set of bit patterns is, trivially, countable.

What if you used infinitely many bits? With a countably infinite sequence of bits, you actually could represent every real number, since the binary expansion of any real is precisely such a sequence. So in a strict cardinality sense, infinite precision would suffice: $|\{0,1\}^\omega| = 2^{\aleph_0} = |\mathbb{R}|$. But this doesn’t help us in practice, because processing a number that requires infinitely many bits to write down means you never finish writing it down. Any real computer is a finite-state machine operating on finite strings, and the problem is therefore inescapable. Some approximation is always necessary.

The question floating point answers is: given that we must approximate, where should we be precise?

How IEEE 754 answers that question

The standard governing nearly all floating point arithmetic is IEEE 754, published in 1985. A 32-bit single-precision float looks like this:

The value represented is (ignoring special cases):

$(-1)^s \times 1.\text{mantissa} \times 2^{e - 127}$

The mantissa stores 23 bits of fractional part; the leading 1 is implicit, giving 24 bits of significand in total. The exponent (biased by 127) controls the scale of the number.

This structure has a direct consequence for how representable values are distributed across the real line. Between $2^k$ and $2^{k+1}$, there are exactly $2^{23}$ representable values, evenly spaced within that interval. But between $2^{k+1}$ and $2^{k+2}$, there are also exactly $2^{23}$ values, now spread over twice the range, so spaced twice as far apart.

The result: the smaller the number, the denser the representation. There are as many floats between 0.5 and 1.0 as there are between 1.0 and 2.0, and as many again between 2.0 and 4.0. Roughly half of all representable floats lie between −1 and 1. The precision is logarithmically distributed.

This is intentional, and for most numerical work it’s exactly right. The quantity that matters in practice is relative error (how large is the mistake as a fraction of the value itself), rather than absolute error. A temperature reading of 300.001 K is fine; a reading of 300.001 km when you wanted metres is not. Floating point delivers roughly constant relative precision (about 7 significant decimal digits for a 32-bit float, 15–16 for a 64-bit double) across many orders of magnitude.

The depth buffer: where this distribution is actually useful

The non-uniform spacing of floats isn’t just a theoretical nicety; it turns out to be genuinely useful in graphics rendering.

When rasterising a 3D scene, the depth buffer stores, per pixel, some measure of how far away the nearest geometry is. The obvious choice is to store $z$ directly. But $z$ in view space is linear, which means the depth buffer allocates equal precision to a gap from 1m to 2m and a gap from 1000m to 1001m. For most scenes, this wastes precision on the far distance where misorderings don’t matter visually, and starves precision near the camera where they do.

Perspective projection maps $z$ to something proportional to $1/z$ in clip space. Storing $1/z$ in the depth buffer (as OpenGL does by default) means that close-up geometry gets dense, fine-grained depth values, while distant geometry gets coarser ones. This maps naturally onto the float distribution: small values of $1/z$ (far away) sit in the region where floats are spread out; large values (close to the camera) sit where floats are densest. The two non-uniformities cancel out and conspire to put precision where it’s needed.

Special cases and edge behaviour

IEEE 754 reserves certain bit patterns for values that aren’t ordinary numbers:

• ±Infinity: produced by overflow or division by zero (e.g. 1.0 / 0.0), rather than raising an exception
• NaN (Not a Number): for genuinely undefined results, like 0.0 / 0.0 or sqrt(-1.0). NaN propagates: any arithmetic involving NaN returns NaN
• ±0: signed zero, which compares equal to the other zero but behaves differently in some edge cases (e.g. 1.0 / -0.0 gives -Infinity)
• Subnormal numbers: very small values near zero that sacrifice some precision bits to extend the range below the smallest normalised float, rather than abruptly underflowing to zero

The practical upshot is that floating point arithmetic is closed: any operation on two floats returns a float (or one of the above). This is convenient for hardware but does mean that certain errors are silent: NaN propagates quietly through a long computation, and subnormals can drastically reduce performance on some architectures without any obvious signal.

Is there anything better?

Depending on the problem, yes.

Fixed point stores numbers with a fixed number of digits before and after the binary point. It’s simple, fast, and free of floating point’s quirks, at the cost of a fixed dynamic range you have to know in advance. Still common in digital signal processing, embedded systems, and anywhere the input range is well-constrained.

Posits (also known as Universal Numbers, or unums type III) were proposed by John Gustafson in 2017. They encode numbers so that precision is highest near ±1 (where most numerical computation tends to cluster) and deliberately coarser at very large and very small magnitudes. Early results suggest posits can match double-precision float accuracy with fewer bits on certain workloads. They’re not yet in mainstream hardware, but they’re under active research in high-performance computing.

Interval arithmetic stores a lower and upper bound rather than a single approximate value. Every operation returns an interval guaranteed to contain the true result, so you always know your worst-case error. The catch is that intervals widen with each operation, and overestimation accumulates; a long computation can produce a bound too wide to be useful.

Arbitrary precision (Python’s Decimal, GNU MPFR, Java’s BigDecimal) lets you choose precision at runtime and pays for it in speed. Useful for cryptography, financial calculations, and symbolic mathematics. CPython’s integers are already arbitrary precision as standard.

None of these have displaced IEEE 754 for general numerical work. Floats are fast, hardware-supported on every modern processor, and sufficiently accurate for the overwhelming majority of applications.

Working with it sensibly

A few practical rules that follow from the above:

• Never compare floats for exact equality. Use abs(a - b) < epsilon where epsilon suits your problem.
• Watch out for catastrophic cancellation. Subtracting two nearly-equal floats loses most of your significant digits. Reformulate the calculation if possible.
• For long accumulated sums, Kahan summation (compensated summation) keeps the error bounded at the cost of a few extra operations per term.
• For money or anything requiring exact decimal arithmetic, use a decimal type or integer arithmetic. Floats cannot represent 0.1 exactly (it has no finite binary expansion), so financial rounding errors are not a float bug but a float guarantee.

The error in floating point is not random noise. It is structured. The numbers are dense where they tend to matter and sparse where imprecision is tolerable. IEEE 754 is a well-considered response to a problem that has no perfect solution, and understanding why there’s no perfect solution makes the standard considerably easier to reason about.

On 12 June 2026, the US government issued an export-control directive ordering Anthropic to suspend global access to its two most capable models, Claude Fable 5 and Claude Mythos 5. Within hours, both were offline for virtually every user on the planet, not because Anthropic had done anything wrong, but because it had no reliable way to distinguish American citizens from foreign nationals in real time, and so the only compliant path was a total shutdown.

The immediate cause, as reported, was a discovered jailbreak: a method by which sufficiently motivated users had been coaxing Fable 5 into surfacing information it was not supposed to provide. That finding triggered national security concerns, which triggered the directive, which triggered the outage. The cascade was swift, and its logic was, in retrospect, entirely predictable.

A Commercial Phase, Not a Safety Crisis

It is worth stepping back from the drama of the ban itself and noting where we actually are in the AI industry’s lifecycle. Anthropic, like OpenAI before it, is in the process of transitioning from a research organisation into a publicly traded company. In that phase, the incentive structure shifts in ways that are not always comfortable to acknowledge. A model that is seen as capable of providing unrestricted access to sensitive information is a liability, not primarily to the public, but to shareholders, regulators, and the politicians whose goodwill the company needs.

The Fable 5 shutdown served, whatever else it was, as a demonstration that Anthropic would comply with government directives quickly and without public resistance. That posture has real value in Washington, and in the longer run, it almost certainly makes the company easier to take public. Whether one reads that as cynical or as responsible corporate governance depends largely on how much faith one places in the motives of the parties involved.

There is, incidentally, a decent historical parallel here. When Apple introduced the Macintosh in 1984, several government bodies in the UK and elsewhere expressed quiet concern about a personal computer powerful enough to run sophisticated encryption and simulation software without any institutional oversight. The idea that a device with “too much compute” might need to be regulated was not frivolous at the time; it was simply overtaken by the pace of progress. Today, a mid-range smartphone contains more processing power than the supercomputers those regulators were worrying about. The lesson is not that security concerns are always wrong; it is that the threat model ages faster than the policy response.

The Real Safety Question

The most important thing to understand about AI safety in 2026 is where the actual danger lies, and it is not where popular coverage tends to suggest.

We are not, today, in a phase where the models themselves are the primary hazard. Claude Fable 5 does not have goals, desires, or the capacity for autonomous action in the world. It cannot decide to do something harmful; it can only respond to prompts. The meaningful risk, right now, comes from the humans on the other end of those prompts: specifically, those with the patience and ingenuity to extract information that the system was designed to withhold.

This distinction matters enormously for how we think about incidents like the Fable 5 jailbreak. The model did not misbehave. The safety architecture was circumvented. Those are different problems requiring different solutions.

How Fable and Mythos Actually Worked

The architecture that Anthropic deployed was, on paper, sensible. Fable 5 operated as an intake layer: it would assess whether an incoming prompt crossed safety thresholds, and if it found the request acceptable, it would forward it to Mythos 5, the more capable underlying model, to generate the actual response. Think of Fable as a bouncer and Mythos as the room behind the door.

The flaw (and it is a flaw inherent to any such system) is that the bouncer has to make a judgement call, and judgement calls can be manipulated. Users found ways to frame requests that Fable 5 assessed as safe but that nevertheless led Mythos 5 to produce outputs it should not have. The gap between “the safety layer approved this” and “this is actually safe” is precisely where adversarial prompting lives.

This is not a criticism unique to Anthropic. It is a fundamental challenge for anyone deploying a powerful language model with a triage layer in front of it. The more capable the underlying model, the wider that gap can become, because a more capable model will do more with a given prompt, including more that was not intended.

Unrestricted Access to Information

The broader concern that the Fable 5 episode surfaces is one that predates AI by several decades: who should have access to what information, and under what conditions?

Language models represent something genuinely new in this debate. Previously, dangerous information was gated primarily by scarcity: the relevant knowledge was in specialist papers, behind institutional access controls, or simply difficult to synthesise without significant prior expertise. A sufficiently capable language model collapses those barriers. It can aggregate, synthesise, and present information in ways that were simply not possible before, and it does so conversationally, without any of the friction that previously acted as a natural deterrent.

That is genuinely worth regulating. The difficulty is that the regulation cannot be naive. Overly broad restrictions will primarily harm legitimate users (researchers, educators, engineers) while determined bad actors will find workarounds. The jailbreak that triggered the Fable 5 directive demonstrates exactly this: the users who found it were not casual consumers; they were systematic, patient, and technically sophisticated. No amount of policy compliance will deter people like that for very long.

What Comes Next

The models will come back online. Fable 5 and Mythos 5 are too commercially important for Anthropic to leave offline indefinitely, and the US government’s interest is in controlling access, not in permanently removing capability. What is likely to emerge is a more tiered system: verified professional access for researchers and institutions, more restricted access for the general public, and ongoing negotiation between the company, its regulators, and its customers about where those lines should sit.

None of this will be elegant. It will involve compromises that satisfy nobody fully and occasional incidents that reset the debate. But the broad shape of it is the same shape that internet content regulation has taken, that encryption policy has taken, that pharmaceutical licensing has taken. Powerful tools get controlled; the controls get gamed; the controls get revised. The wheel turns slowly, and in the meantime, the technology keeps moving.

The Fable 5 ban was not a signal that AI is uniquely dangerous. It was a signal that AI is now important enough to be treated like everything else.

Distributed systems have a fundamental problem: how do you get a collection of machines to agree on something when any of them might crash, messages might be delayed, and you can’t tell the difference between a slow node and a dead one? This is the consensus problem, and getting it right is what separates a database that stays consistent under failure from one that silently loses or corrupts data.

Raft is a consensus algorithm published by Diego Ongaro and John Ousterhout in 2014. Their explicit goal was understandability. Paxos, the algorithm that had dominated the field for two decades, is notoriously difficult to reason about and even harder to implement correctly. Raft covers the same ground but structures itself around three mostly-independent subproblems: leader election, log replication, and safety. Tackling them separately makes both the algorithm and its correctness argument much easier to follow.

What consensus actually requires

The problem is deceptively simple to state. You have a cluster of $n$ servers. Clients send them commands. The servers must all execute those commands in the same order, so that every server ends up in the same state, even if some servers crash and restart mid-stream.

Formally, a consensus algorithm must satisfy three properties:

• Safety: all servers that decide on a value decide on the same value, and only values that were actually proposed can be chosen
• Liveness: the system eventually makes progress if enough servers are reachable (Raft requires a majority)
• Fault tolerance: the system continues operating correctly through the failure of up to $\lfloor (n-1)/2 \rfloor$ servers

The liveness constraint is worth dwelling on. Raft requires a quorum (a majority of servers) to make progress. With 5 servers you can tolerate 2 failures; with 3 servers you can tolerate 1. You cannot get fault tolerance without paying some cost in availability, and Raft accepts that: a partition that isolates more than half the cluster will stall the system rather than risk inconsistency.

Terms and the replicated log

Raft organises time into terms, each identified by a monotonically increasing integer. A new term begins whenever an election is triggered. Terms act as a logical clock: any message carrying a term number lower than a server’s current term is stale and ignored. This is how Raft detects and discards messages from old leaders that have been partitioned away and haven’t yet noticed.

The shared state that Raft maintains is a replicated log: an ordered sequence of entries, each containing a command and the term in which it was appended. Once an entry has been committed, meaning replicated to a majority of servers, it is guaranteed to appear in the log of any future leader, and will therefore be applied by every server in the same position. The log is the source of truth; the server state machine is derived from it.

Leader election

At any given moment, each server is in one of three states: leader, follower, or candidate. Normal operation has exactly one leader; followers are passive and simply respond to requests from the leader and candidates.

Followers expect to receive periodic heartbeats from the leader (empty AppendEntries RPCs). Each follower has an election timeout, randomly chosen from a window (typically 150–300ms). If this timeout elapses without a heartbeat, the follower concludes that the leader has failed, increments its term, converts to a candidate, and starts an election.

As a candidate, the server votes for itself and sends RequestVote RPCs to all other servers. A server grants its vote if:

1. It has not already voted in this term, and
2. The candidate’s log is at least as up-to-date as its own (more on this below)

If the candidate collects votes from a majority of servers, it becomes leader and immediately begins sending heartbeats to suppress further elections. If no candidate achieves a majority (perhaps two candidates split the vote), the term ends without a winner and a new election begins after another randomised timeout.

The randomised timeouts are the key mechanism for avoiding split votes. If all servers had identical timeouts, they would all trigger elections simultaneously on every leader failure. By spreading the timeouts randomly, the first server to time out usually wins the election before others have even started.

Log replication

Once elected, the leader handles all client requests. When it receives a command, it appends the entry to its own log and then sends AppendEntries RPCs to every follower in parallel, asking them to append the same entry.

The AppendEntries RPC includes a consistency check: along with the new entry, the leader sends the index and term of the entry immediately preceding it. A follower only accepts the new entry if its own log matches at that position. If it doesn’t match, the follower rejects the request and the leader retries, working back through the log until it finds the point where the logs agree, then replaying entries forward from there. This guarantees the Log Matching Property: if two entries in different logs have the same index and term, then all preceding entries are identical.

Once the leader has received acknowledgement from a majority of servers, the entry is committed. The leader advances its commit index and notifies followers in subsequent AppendEntries messages. Followers apply committed entries to their state machines in order.

This means a client only gets a response once the entry is safely replicated to a majority. If the leader crashes after committing but before responding to the client, the client will retry and the new leader will have the entry, so it is applied exactly once. (Clients need to handle idempotency; Raft itself does not.)

Safety: why committed entries are never lost

The most important property Raft needs to guarantee is that a committed log entry is never overwritten or lost by a subsequent leader. This is enforced by the election restriction.

A candidate can only win an election if its log is at least as up-to-date as the logs of a majority of servers. “Up-to-date” is defined precisely: compare the term of the last entry first; whichever is higher wins. If the last entries have the same term, whichever log is longer wins.

Why does this suffice? Suppose entry $e$ is committed in term $t$, meaning a majority $Q_1$ of servers acknowledged it. Any future leader must have won a majority $Q_2$. Since $|Q_1| + |Q_2| > n$, the two majorities overlap in at least one server. That server has entry $e$ in its log. For the new candidate to beat it in the up-to-date comparison, the candidate’s log must be at least as current, which means it also has $e$. So any server that wins an election must already have all committed entries.

This is the core of Raft’s safety argument: committed entries always survive leadership changes because you cannot win an election without first having them.

Cluster membership changes

A practical Raft deployment needs to be able to add and remove servers without taking the system offline. This is more subtle than it sounds: if you switch directly from an old configuration to a new one, there is a window where two disjoint majorities are possible, which breaks safety.

Raft handles this with a joint consensus approach. The cluster first transitions into a joint configuration that includes both the old and new sets of servers. During this phase, majorities must be obtained from both groups simultaneously. Once this joint configuration is committed, the cluster transitions to the new configuration alone. At no point can two independent majorities exist.

What Raft doesn’t solve

Raft assumes a crash-fault model: servers fail by stopping. It does not tolerate Byzantine faults: servers that behave arbitrarily, send conflicting messages, or actively lie. A Byzantine server could, for instance, claim to have committed an entry it hasn’t, or vote in multiple elections simultaneously. Handling Byzantine faults requires a different class of algorithms (PBFT, HotStuff, Tendermint, etc.) and typically requires $n \geq 3f + 1$ servers to tolerate $f$ faults, compared with Raft’s $n \geq 2f + 1$.

Raft also says nothing about performance: a single leader handling all writes is a throughput bottleneck at scale. Production systems based on Raft (etcd, CockroachDB, TiKV) layer batching, pipelining, and sometimes multi-Raft sharding on top to work around this.

Why it’s taught

The reason Raft appears in distributed systems courses more often than Paxos does is not that it’s faster or more fault-tolerant. It isn’t, meaningfully. The reason is that when you implement it, you are less likely to accidentally implement something subtly wrong.

Paxos specifies a protocol for agreeing on a single value. Real systems need to agree on a sequence of values, and the extension from single-value Paxos to multi-Paxos is where most of the complexity hides, and where most of the real implementations diverged from the original paper in undocumented ways. Raft was designed as a complete system from the start, with explicit solutions to leader election, log replication, membership changes, and snapshots. The spec is the implementation guide.

Ongaro’s thesis includes a user study in which students who learned Raft significantly outperformed those who learned Paxos on comprehension questions. Whether that advantage persists as engineers gain experience with both is debatable, but as a starting point for understanding distributed consensus, Raft earns its place.