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

graphmmean degmin deglambda2kvke
barbell 1 bridge315.16750.2583411
barbell 3 bridges335.50050.8377233
ring lattice C12(1,2)244.00041.2679544
circulant C12(1,5)244.00042.0000044
Mobius ladder183.00031.0000033
star K1,11111.83311.0000011
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