Robustness in Graph Theory through Spectral Properties — Epoche C2
Two graphs on a million vertices Take two graphs on the same vertex set of $n = 10^6$ vertices. The first is a pair of complete graphs on half a million vertices each, joined by a single edge; it has $2\binom{500000}{2} + 1 = 249{,}999{,}500{,}001$ edges, almost exactly half as many as the complete graph $K_n$ on the same vertices, and deleting one particular edge splits it into two equal halves. The second is $3$-regular with second adjacency eigenvalue at most $2\sqrt{2} \approx 2.828$; it has $3n/2 = 1{,}500{,}000$ edges, about six parts in a million of the first graph's total, and no set of fewer than roughly $42{,}900$ edges can be removed to split it into two halves. Every figure in that sentence is derived below rather than quoted. That pair is the whole thesis of this review in one line: the count of edges does not determine what it costs to break a graph, and the quantity that does is spectral. What follows sets out why, and in doing so corrects four things in the earlier version of this text — a misstatement of the Cheeger inequality, a parenthesis that reverses the direction of the spectral gap, a definition of $(n,d,\lambda)$-graphs that conflates two inequivalent notions, and a robustness claim about "exponential decay of the probability of disconnection" that is not a theorem in any form in which it can be checked. One notational point first, because the literature makes it easy to write nonsense here. The symbol $\lambda$ is used classically for edge connectivity and also for adjacency eigenvalues, and the earlier version used it for both within three paragraphs. Throughout this text, $\kappa(G)$ is vertex connectivity and $\kappa'(G)$ is edge connectivity — the minimum number of vertices, respectively edges, whose deletion disconnects the graph or reduces it to a single vertex — while $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$ are the adjacency eigenvalues and $\lambda(G) = \max_{i \ge 2} |\lambda_i|$. What the classical connectivity measures record, and what they miss The intuition under examination is that raising the edge count $m$ raises resilience. Stated in terms of $\kappa$ and $\kappa'$ the intuition is not wrong, merely uninformative, and it is worth seeing why. For the dumbbell of the opening, $\kappa = \kappa' = 1$: the single bridging edge is a cut edge, and either of its endpoints is a cut vertex. For any $d$-regular graph, $\kappa \le \kappa' \le d$, since deleting the $d$ edges at a vertex isolates it, so the cubic graph has $\kappa \le 3$. By these measures the cubic graph is barely better than the dumbbell — 3 against 1 — and the dumbbell has about a hundred and sixty-seven thousand times as many edges. Yet the dumbbell falls apart into two halves of half a million vertices each, while removing three well-chosen edges from the cubic graph strands at worst a single vertex. The defect is structural, not a matter of tightening constants. Both $\kappa$ and $\kappa'$ are minima over all separating sets, so both are pinned by the worst local configuration in the graph, and neither records anything about the sizes of the pieces that the cheapest cut produces. What matters for a network is how much of it survives in one piece, which is a claim about all cuts at once, weighted by the size of the side each isolates. The spectral quantity enters the classical picture through Fiedler's theorem (1973): for any graph other than the complete graph, the second-smallest eigenvalue $\mu_2$ of the Laplacian is at most the vertex connectivity, $\mu_2 \le \kappa(G)$. For a $d$-regular graph the Laplacian is $L = dI - A$, so $\mu_2 = d - \lambda_2$ and the theorem reads $\kappa(G) \ge d - \lambda_2$. This already settles the density question in one line. Take a $102$-regular graph on $n = 10^6$ vertices with $\lambda_2 \le 2\sqrt{101} \approx 20.0998$ — such graphs exist, for reasons given below. It has $102n/2 = 5.1 \times 10^7$ edges, about a five-thousandth of the dumbbell's, and Fiedler's bound forces $\kappa \ge 102 - 20.0998 = 81.90$, hence $\kappa \ge 82$, against the dumbbell's $\kappa = 1$. Edge expansion and the Cheeger inequality, in its correct form Fiedler's inequality gives a bound on the cheapest cut but still nothing on the sizes. The quantity that supplies the missing information is the edge expansion, or Cheeger constant, $$h(G) = \min_{0 where $\partial S$ is the set of edges with exactly one endpoint in $S$. Because the denominator is the size of the side being separated, $h$ penalises cheap cuts in proportion to how much they cut off, which is exactly the property $\kappa'$ lacks. For the dumbbell, taking $S$ to be one clique gives $|\partial S| = 1$ and $|S| = 5 \times 10^5$, so $h = 2 \times 10^{-6}$; and no other choice does better. The Cheeger inequality relates $h$ to the spectral gap $d - \lambda_2$. Its correct statement for a $d$-regular graph, due in its two directions to Alon and Milman (1985) and to Alon (1986), and proved in this normalisation in the survey of Hoory, Linial and Wigderson (2006), is $$\frac{d - \lambda_2}{2} \;\le\; h(G) \;\le\; \sqrt{2d\,(d - \lambda_2)}.$$ The earlier version of this text gave the upper bound as $\sqrt{d^2 - \lambda_2^2}$. That is a different and strictly stronger claim: since $\sqrt{d^2 - \lambda_2^2} = \sqrt{(d - \lambda_2)(d + \lambda_2)}$ and $\lambda_2 \le d$, the quantity printed there never exceeds $\sqrt{2d(d - \lambda_2)}$, so asserting it asserts more than the theorem delivers. A second correction in the same passage matters more, because everything downstream depends on getting the direction right. The earlier version glossed a large spectral gap as "$d - \lambda_2$ small". The spectral gap is $d - \lambda_2$; a large gap means that quantity is large, and it is a large gap that forces $h$ to be large, by the left-hand inequality. Both directions are worth having in outline, since the essay leans on the first. For the lower bound, use the variational characterisation $\mu_2 = \min\{x^{\top}Lx