What does Spectral Gaps and Bottleneck Cuts conclude, in numbers, about “Algebraic Connectivity: Why a High Degree Is Not Robustness”?
Answer: Chapter 1 computes the algebraic connectivity by Jacobi rotation and shows that a one-bridge barbell with a higher mean degree has an algebraic connectivity of only 0.25834, against 2.00000 for a circulant, a factor of 7.74.
Scope of the numbers: The parameters are illustrative; all calculations are generated by the book's programs; the book is not individual business advice, and any change to a production system or a real supply chain must be reviewed and released by hand by the person in charge. Marked boxes separate published evidence, runnable Python calculations (18 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.25834, 2.00000, 7.74
| graph | m | mean deg | min deg | lambda2 | kv | ke |
| barbell 1 bridge | 31 | 5.167 | 5 | 0.25834 | 1 | 1 |
| barbell 3 bridges | 33 | 5.500 | 5 | 0.83772 | 3 | 3 |
| ring lattice C12(1,2) | 24 | 4.000 | 4 | 1.26795 | 4 | 4 |
| circulant C12(1,5) | 24 | 4.000 | 4 | 2.00000 | 4 | 4 |
| Mobius ladder | 18 | 3.000 | 3 | 1.00000 | 3 | 3 |
| star K1,11 | 11 | 1.833 | 1 | 1.00000 | 1 | 1 |
| lambda2 <= kv <= ke <= min degree in every row: yes | ||||||
| barbell mean degree / circulant mean degree: 1.2917 | ||||||
| circulant lambda2 / barbell lambda2: 7.74 |
Show the full program
# Chapter 1. p12: degree is not robustness. Six 12-node graphs compared
# by mean degree, lambda2, vertex and edge connectivity.
# Model: Fiedler (1973) proved lambda2 <= vertex connectivity <= edge
# connectivity <= minimum degree for a non-complete graph. Connectivities
# are computed exactly by unit-capacity max flow (Menger's theorem;
# vertices are split in two for vertex connectivity). The six graphs are
# textbook constructions; no parameter is estimated from data.
import collections
import math
def laplacian(n, edges):
lap = [[0.0] * n for _ in range(n)]
for i, j in edges:
lap[i][j] -= 1.0
lap[j][i] -= 1.0
lap[i][i] += 1.0
lap[j][j] += 1.0
return lap
def jacobi(mat, tol=1e-22):
n = len(mat)
a = [row[:] for row in mat]
for _ in range(60):
off = math.fsum(a[i][j] ** 2 for i in range(n)
for j in range(i + 1, n))
if off < tol:
break
for p in range(n - 1):
for q in range(p + 1, n):
if abs(a[p][q]) < 1e-300:
continue
th = (a[q][q] - a[p][p]) / (2.0 * a[p][q])
t = math.copysign(1.0, th) / (abs(th) + math.hypot(th, 1.0))
c = 1.0 / math.sqrt(t * t + 1.0)
s = t * c
for k in range(n):
akp, akq = a[k][p], a[k][q]
a[k][p] = c * akp - s * akq
a[k][q] = s * akp + c * akq
for k in range(n):
apk, aqk = a[p][k], a[q][k]
a[p][k] = c * apk - s * aqk
a[q][k] = s * apk + c * aqk
return sorted(a[i][i] for i in range(n))
def maxflow(cap, s, t):
flow = 0
res = collections.defaultdict(int)
for (u, w), c in cap.items():
res[(u, w)] += c
adj = collections.defaultdict(list)
for (u, w) in list(res):
adj[u].append(w)
adj[w].append(u)
while True:
prev = {s: None}
dq = collections.deque([s])
while dq and t not in prev:
u = dq.popleft()
for w in adj[u]:
if w not in prev and res[(u, w)] > 0:
prev[w] = u
dq.append(w)
if t not in prev:
return flow
w = t
while prev[w] is not None:
u = prev[w]
res[(u, w)] -= 1
res[(w, u)] += 1
w = u
flow += 1
def edge_conn(n, edges):
cap = {}
for i, j in edges:
cap[(i, j)] = 1
cap[(j, i)] = 1
return min(maxflow(cap, 0, t) for t in range(1, n))
def vertex_conn(n, edges):
es = set(edges) | {(j, i) for i, j in edges}
best = n - 1
for s in range(n):
for t in range(s + 1, n):
if (s, t) in es:
continue
cap = {}
for v in range(n):
cap[(2 * v, 2 * v + 1)] = n
if v not in (s, t):
cap[(2 * v, 2 * v + 1)] = 1
for i, j in edges:
cap[(2 * i + 1, 2 * j)] = n
cap[(2 * j + 1, 2 * i)] = n
best = min(best, maxflow(cap, 2 * s + 1, 2 * t))
return best
def clique(nodes):
return [(a, b) for k, a in enumerate(nodes) for b in nodes[k + 1:]]
def circulant(n, steps):
es = set()
for i in range(n):
for d in steps:
j = (i + d) % n
es.add((min(i, j), max(i, j)))
return sorted(es)
left, right = list(range(6)), list(range(6, 12))
graphs = [
("barbell 1 bridge", clique(left) + clique(right) + [(5, 6)]),
("barbell 3 bridges", clique(left) + clique(right)
+ [(3, 9), (4, 10), (5, 11)]),
("ring lattice C12(1,2)", circulant(12, (1, 2))),
("circulant C12(1,5)", circulant(12, (1, 5))),
("Mobius ladder", circulant(12, (1, 6))),
("star K1,11", [(0, j) for j in range(1, 12)]),
]
print("graph m mean deg min deg lambda2 kv ke")
all_ok = True
lams = {}
for name, es in graphs:
deg = [0] * 12
for i, j in es:
deg[i] += 1
deg[j] += 1
lam = jacobi(laplacian(12, es))[1]
kv, ke = vertex_conn(12, es), edge_conn(12, es)
ok = lam <= kv + 1e-9 and kv <= ke <= min(deg)
all_ok = all_ok and ok
lams[name] = lam
print("%-21s %3d %6.3f %4d %8.5f %2d %2d %s"
% (name, len(es), 2 * len(es) / 12, min(deg), lam, kv, ke,
"" if ok else "FIEDLER BOUND FAILS"))
print()
print("lambda2 <= kv <= ke <= min degree in every row: %s"
% ("yes" if all_ok else "no"))
print("barbell mean degree / circulant mean degree: %.4f"
% ((31 / 6) / 4.0))
print("circulant lambda2 / barbell lambda2: %.2f"
% (lams["circulant C12(1,5)"] / lams["barbell 1 bridge"]))Single source and citation
Fan, Y. (2026). Graph-Laplacian Spectral Gaps and Cheeger Constants: Single-Point Bottleneck Cuts in Multi-Agent Workflows and Cross-Border Supply Chains (Version 1.0.0), Chapter 1: Algebraic Connectivity: Why a High Degree Is Not Robustness. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-243 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026243,
author = {Fan, Yafu},
title = {Graph-Laplacian Spectral Gaps and Cheeger Constants: Single-Point Bottleneck Cuts in Multi-Agent Workflows and Cross-Border Supply Chains},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 2 · The Cheeger Constant: How Narrow the Neck Is, Clamped from Both Sides by the Spectrum
- Chapter 3 · Where to Add One Link: Greedy Addition, the Fiedler Score and the Illusion of Quantity
- Chapter 4 · Multi-Agent Workflows: Consensus Speed, the Orchestrating Hub and Single Points of Hand-off
- Chapter 5 · Cross-Border Supply Chains: Effective Resistance, Maximum Flow and the Weight of One Port
- Chapter 6 · Opposing Evidence and Boundaries: Where the Algebraic Connectivity Misleads
- Chapter 7 · Eastern and Western Sources: the Changshan Snake of Sunzi's "Nine Grounds" and Kirchhoff's Circuit Equations of 1847
- Chapter 8 · The Empirical Loop: a Quarterly Checkup of the Workflow Graph, Link Advice and a Plan for Refutation