The spectrum is not the graph

Every method in this field reads a spectrum and answers a question about a graph. A component count, a conductance bound, a mixing time, a partition, a centrality — all of them are functions of eigenvalues and eigenvectors, and all of them are therefore functions of the graph only to the extent that the spectrum determines the graph.

It does not.

The pair, and how it is checked #

On the left, a triangle and a square sharing a vertex. On the right, K₂,₃ — three vertices each joined to both of two others — with one extra vertex hanging off. Six vertices and seven edges each.

Their Laplacian characteristic polynomials are

x⁶ − 14x⁵ + 73x⁴ − 176x³ + 192x² − 72x

for both, and that is checked as an integer polynomial rather than by comparing computed eigenvalues. The coefficients are computed by the Faddeev–LeVerrier recurrence in BigInt rationals, so the claim is that two sequences of seven integers are equal, which they are, exactly.

That distinction matters more here than almost anywhere on the site. Two computed spectra agreeing to 5.3·10⁻¹⁵ would be consistent with the graphs being cospectral and also with their being different by less than the eigensolver can see — and the whole point of the pair is to distinguish “the same” from “indistinguishable”. An exact check settles it and a numerical one cannot.

They are not the same graph, by two independent readings #

Degree sequences. Sorted, the left graph’s is 4, 2, 2, 2, 2, 2 and the right’s is 3, 3, 3, 2, 2, 1. One has a vertex of degree four and no vertex of degree one; the other has neither.

Bipartiteness. The left graph contains a triangle, so it has an odd cycle and is not bipartite — and a bipartite graph is also the case where a random walk on it never mixes, so the property has consequences well beyond this pair. The right is K₂,₃ with a pendant edge, which is bipartite by construction.

Either fact alone proves the graphs are not isomorphic. Both are properties any reader can check by looking, and neither is visible in the spectrum.

They agree on more than the spectrum, too. Both have twelve spanning trees — which follows from cospectrality, since the count is the product of the non-zero eigenvalues divided by n, so a count that comes out of a determinant cannot separate them either.

Where the pair came from #

The pair was not taken from a table; it was found by enumeration, and the search is short enough to describe.

Every graph on six vertices is a subset of the fifteen possible edges, so there are 32,768 of them. Discarding the disconnected ones and those with fewer than five edges leaves a few thousand. Group them by their exact Laplacian characteristic polynomial — a vector of seven integers — and look for a group containing two graphs with different degree sequences, which guarantees non-isomorphism without having to test for it.

There are 110 distinct polynomials among the connected six-vertex graphs, and two of those groups contain graphs with different degree sequences. The pair above is the first, and the second is a larger pair on eight edges.

Two things about that are worth recording. Six vertices is the smallest size where this happens — below it, every connected graph is determined by its Laplacian spectrum, which the same enumeration confirms. And the grouping is exact: the polynomials are integer vectors compared for equality, so no threshold decides which graphs are cospectral, which would be the obvious way to get this wrong.

That is the same distinction a threshold on singular values forces, and here it is avoided entirely. A search that grouped by computed eigenvalues within a tolerance would have found the pair and would also have found spurious ones — graphs whose spectra differ in the twelfth digit — and no tolerance separates the two cases, because the differences between genuinely distinct spectra on six vertices go all the way down to zero.

What follows for every method in this field #

The consequence is not that spectral methods are unsound. It is that they answer a question about an equivalence class, and it is worth going through what that means case by case.

A component count is safe. The number of zero eigenvalues is a genuine invariant and cospectral graphs have the same one, correctly — so the count and the threshold that reads it behave identically on both.

A spanning-tree count is safe, and exactly so. The number of spanning trees is a determinant of the grounded Laplacian, hence a function of the spectrum, so cospectral graphs have the same count — twelve each for this pair. That is an invariant a caller can rely on and also one that cannot distinguish the two.

The two figures are there to make a point about what “safe” means. The tree count is safe as an invariant — it is genuinely a function of the spectrum, and it agrees on the pair — and it is safe as a computation only up to fifteen vertices, past which the format runs out and the integer stops being representable. Two different senses of the word, and a method can satisfy one and not the other.

A conductance bound is safe, since both halves of it are functions of the spectrum alone. Cheeger’s inequality bounds a graph’s conductance in terms of its spectrum, so cospectral graphs have conductances in the same bracket — and they may have different conductances inside it, which the bound permits and does not detect.

A partition is not determined. The Fiedler vector depends on eigenvectors, not only eigenvalues, and cospectral graphs have different eigenvectors — so the sweep that rounds one can return different answers on two graphs a spectrum cannot separate. So two graphs a spectral method cannot tell apart can be partitioned differently, correctly, by the same method.

And a similarity search is unsound. Any pipeline that compares graphs by comparing spectra — a common technique, because a spectrum is a short vector and a graph is not — will report these two as identical. They are not, and the difference is large: one is bipartite and one has a triangle.

The other matrix separates them at once #

The second Laplacian, which an earlier essay argued is a genuinely different object, tells them apart immediately:

                 normalised spectrum
triangle+square  0, 0.376510, 1, 1.222521, 1.500000, 1.900969
K₂,₃ + pendant   0, 0.528595, 1, 1.000000, 1.471405, 2.000000

The second eigenvalues differ by 0.152, which is not a rounding of anything, and the largest eigenvalue of the right-hand graph is exactly 2.

That last entry is the whole mechanism. The normalised Laplacian’s spectrum lies in [0, 2] for every graph, and 2 is attained if and only if the graph is bipartite. So the normalised spectrum detects bipartiteness, the combinatorial one does not, and the two matrices built from one object answer different questions — which was the earlier essay’s claim, and this is the sharpest available instance of it.

It is worth noticing what has happened. The information distinguishing these graphs was present in the object the whole time; the combinatorial matrix threw it away and the normalised one did not. “The spectrum of a graph” is not a well-formed phrase, and which matrix is meant decides what can be concluded.

How the polynomial is computed, and why not by the eigenvalues #

The characteristic polynomial could be obtained by multiplying out (x − λᵢ) over the computed eigenvalues, and that is the route this essay could not use.

Multiplying six computed eigenvalues, each accurate to 10⁻¹⁴, gives coefficients accurate to about 10⁻¹³ relative — which for a coefficient of 176 means an absolute error of 10⁻¹¹, so the integers would have to be recovered by rounding, and the claim “these two polynomials are equal” would become “these two rounded polynomials are equal”, which is a claim about a tolerance.

Faddeev–LeVerrier avoids it entirely. The recurrence builds the coefficients from traces of powers of the matrix:

M₀ = 0,   Mₖ = A(Mₖ₋₁ + cₖ₋₁I),   cₖ = −tr(Mₖ)/k

and every operation in it is a multiplication or addition of rationals. On an integer matrix the intermediate entries stay rational with small denominators, the trace divisions come out whole, and the coefficients arrive as exact integers with no rounding at any step.

The recurrence is famously unstable in floating point — the divisions by k against traces that grow like ‖A‖ᵏ lose digits fast, and nobody would use it numerically. In exact arithmetic that instability does not exist, which is a clean instance of a distinction this site makes often: numerical stability is a property of an algorithm in an arithmetic, not of the algorithm. A method that is unusable in binary64 can be the right one in rationals, and the reason to reach for it here is that the claim being made is exact.

And the normalised one is not enough either #

The obvious next move is to conclude that the normalised Laplacian is the right invariant. It is not.

Normalised-cospectral pairs exist as well, and so do pairs that are cospectral for both matrices at once. There is no single matrix built from a graph whose spectrum determines it — the whole subject of graph isomorphism would be a two-line eigenvalue computation if there were.

What is true is a hierarchy of partial results. Almost all graphs are determined by their spectrum, in the sense that the fraction of cospectral pairs falls as the number of vertices grows; the smallest Laplacian-cospectral pair has six vertices; adding invariants (the number of triangles, the degree sequence, the spectrum of a complement) rules out more pairs. None of that produces a complete invariant, and none of it is a numerical statement.

How common is this #

The pair above is the smallest, which invites the question of whether it is a curiosity or a hazard, and the answer depends on which end of the size range the graphs come from.

On six vertices, the enumeration finds two cospectral groups out of 110 polynomials — so a couple of per cent of the connected six-vertex graphs share a spectrum with a non-isomorphic one. That is small.

It rises before it falls. The fraction of graphs on n vertices that are not determined by their adjacency spectrum peaks somewhere in the teens — a substantial fraction at n = 10 to 12 by published enumerations — and then falls as n grows, with the conjecture, unproven, that it tends to zero.

So the risk profile is unusual: the graphs most likely to collide are the small ones, and small graphs are exactly the ones a spectral fingerprint would be used on, because a large graph’s spectrum is expensive and a small graph’s is not.

There is a second reason the count understates the hazard, and it is the one the measurement below turns out to be about. The enumeration above is over all graphs, weighted uniformly, and a random graph on many vertices is highly irregular and almost never cospectral with anything. Real graphs are not random: they have symmetry, repeated motifs, and substructures that appear more than once — and every one of those raises the chance of a collision, because cospectral pairs are usually built from exactly such structure. The construction that generates most known pairs, Godsil–McKay switching, needs a set of vertices with a particular regularity in how they attach to the rest, which is common in engineered graphs and rare in random ones.

What this field’s habit says to do about it #

The site’s rule is that a claim should be given a test it could fail. Applied here it produces something concrete and cheap.

Report the invariants the spectrum does not carry. The degree sequence costs one pass, and it is the same quantity that decides where to ground a solve.

That advice is worth a hit rate rather than a recommendation, because the number decides whether it is worth taking. Random graphs at edge probability 0.45, deduplicated by brute-force canonical form so a repeat is a genuine repeat, then grouped by adjacency spectrum:

Every collision is caught. Not most; all of them, at both sizes. So on a graph that arrives without structure the advice is not a partial mitigation but a complete one, for one pass over the edges.

And it catches none of the collisions this section is warning about, by definition. Two cospectral d-regular graphs have identical degree sequences, because every vertex has degree d — there is nothing for the invariant to see. Regular graphs are exactly the symmetric, engineered, repeated-motif graphs named above, and Godsil–McKay switching preserves regularity when the switching set is regular.

Which makes the honest version one sentence rather than two: the degree sequence is a complete defence against an accidental collision and no defence at all against a constructed one. A code that reports it has covered the case where a spectral fingerprint would probably have been fine anyway, and has done nothing about the case the construction literature is about. That is still worth doing — it is one pass — but it should be reported as what it is, and a claim about a symmetric graph needs something else.

Whether the graph is bipartite costs a breadth-first search. The number of triangles costs a sparse matrix product. Any of them would have separated the pair above, and all three together are less work than the eigendecomposition that did not.

Do not compare graphs by spectra alone. A pipeline that fingerprints a graph by its eigenvalues has a collision rate that is small and is not zero, and the collisions are not near-misses — they are graphs with different topology reported as identical.

And say which matrix. A result quoted about “the graph Laplacian” is ambiguous between two matrices that disagree about bipartiteness, about conditioning, and about the theorem Cheeger’s inequality is stated for.

The adjacency spectrum is a third object, and it disagrees too #

The site’s refusal for this essay is about a different cospectrality, and it is worth unpacking because it shows that the phenomenon is not one phenomenon.

Begin with the pair already on the page. Its combinatorial Laplacian cannot tell the two graphs apart and its normalised Laplacian can. The third matrix a graph has — the adjacency matrix, which carries no degrees at all, neither on a diagonal nor in a scaling — can as well, and by a mechanism worth naming exactly.

The coefficient that differs is the one on x³, and it is −2 for the graph on the left and 0 for the one on the right. That is not an accident of this pair. For any simple graph the coefficient of xⁿ⁻³ in the adjacency characteristic polynomial is −2 times the number of triangles, because the only closed walk of length three is a triangle traversed in two directions; equivalently Σλ³ = 6·(triangles), which reads 6 here against 0. The adjacency spectrum can see the triangle. The combinatorial Laplacian spectrum, on the same two graphs, cannot.

The obvious mechanism is the wrong one, and it is worth saying which. The natural guess is the second moment: Σλ² is the sum of the squared entries of the adjacency matrix, which is twice the edge count, so it looks like the quantity that would notice two graphs are different. It is not. These two graphs have seven edges each, so their second moments are 14 and 14 — equal by construction, and equal on any pair with the same edge count, which every Laplacian-cospectral pair must be, because the edge count is a Laplacian invariant. The second moment could never have separated them. It is the third that does, and the third is the triangle, which is the property every other figure in this essay has been pointing at.

The converse fails too, and showing it needs a different pair — the one the refusal at the top of this page is stated about.

This is the example in every textbook, and it is cospectral in the same exact sense the six-vertex pair is: not to fourteen digits, but as integer polynomials. It is also plainly two different graphs, and by a cruder reading than a triangle — one of them is disconnected. The badge counts the components rather than the spanning trees, because a disconnected graph has no spanning tree and the determinant that would count them is zero.

That disconnection is exactly what the Laplacian sees and the adjacency matrix does not.

So adjacency-cospectral does not imply Laplacian-cospectral. The assertion behind this page’s refusal is fed exactly that pair and required to reject the claim that it does, which is why the refusal is published rather than asserted in a sentence.

Two pairs and three matrices make six figures, and only five of them exist. The normalised Laplacian of C₄ ∪ K₁ is not a matrix: the isolated vertex has degree zero, so D^(−1/2) has no entry for it, and anything drawn under that heading would have to be a pseudo-inverse standing in for it — a different object, about which none of the theorems here say anything. The sixth figure refuses to be drawn, for the same reason a bound is not plotted outside its own range.

So there are at least three spectra a graph has — adjacency, combinatorial Laplacian, normalised Laplacian — and they are cospectral in three different equivalence relations, none of which implies another. A statement of the form “these graphs are cospectral” is incomplete without saying in which, and the five drawings of these two pairs give the whole table. Asked “cospectral?” of the adjacency matrix, the combinatorial Laplacian and the normalised one, the six-vertex pair answers no, yes, no; the five-vertex pair answers yes, no, and the question does not arise.

Why this is the field’s last word #

The graph field has been about a continuous computation producing a discrete answer, and the failures have all had the same shape: a rounding decides a partition, a threshold decides a count, a format decides an integer. Every one of them was a property of the arithmetic meeting a property of the question.

This one is different and it is the reason it comes last. Nothing here is about the arithmetic at all. The exact characteristic polynomials are equal, in exact arithmetic, on a machine with infinite precision. No improvement to a solver, no change of matrix, no increase in precision separates these two graphs by their combinatorial spectrum, because the information is not there.

That is the boundary of the whole field. Everything before it says the arithmetic decides more than it should; this says that even a perfect arithmetic decides less than a reader assumes. A spectral method answers what the spectrum determines, and that is a smaller thing than the graph — measurable, on six vertices, exactly.

One consolation #

It would be wrong to end without the useful half, because the pair above can be read as evidence against spectral methods and it is not.

Everything these two graphs share, they share correctly. They have the same number of components, the same number of spanning trees, the same sum of degrees, the same number of edges, and conductances inside the same Cheeger bracket. A spectral method asked any of those questions returns the right answer for both, and would be wrong only if it were asked to distinguish them — which is a question about isomorphism rather than about any quantity in this field.

The scope of the caution is therefore narrow and precise. Do not use a spectrum as an identity. Use it for the quantities it determines, which is most of what this field computes, and add a cheap combinatorial invariant whenever the question is whether two graphs are the same one.