On a conjecture of Kolokolnikov on algebraic connectivity

Cheng Chi; Jiaxin Zheng; Junjie Wang

On a conjecture of Kolokolnikov on algebraic connectivity

T0 review · 0 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper resolves a conjecture on algebraic connectivity by proving a sharp universal bound: any graph on n≥4 vertices with at most 2n−4 edges has α(G) ≤ 2, with equality attained by K_{2,n−2}.

desk verdict Settles a decade-old conjecture with a long but verifiable proof; the result is new and the structure is sound, though Section 4 deserves a careful referee. read the letter →

arxiv 2608.09822 v1 pith:EFLUQFX5 submitted 2026-08-10 math.CO

Cheng Chi , Junjie Wang , Jiaxin Zheng This is my paper · ORCID

classification math.CO MSC 05C5005C3505C40

keywords algebraicconnectivityLaplacianeigenvalueextremalgraphtheorycompletebipartitegoodpair3-connectedspectralboundedgecountthreshold

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper resolves a long-standing conjecture about the algebraic connectivity of sparse graphs: for any simple graph on n≥4 vertices with at most 2n−4 edges, the second-smallest Laplacian eigenvalue α(G) is at most 2. The bound is sharp, since the complete bipartite graph K_{2,n−2} has exactly 2n−4 edges and α = 2, and it completes the classification because the conjecture states this graph is the maximizer. The proof reduces to 3-connected graphs on exactly 2n−4 edges and then shows, via a lengthy structural analysis, that every such graph contains a 'good pair'—two disjoint nonempty vertex sets with no edges between them and each having boundary at most twice its size. A test vector built from the two sets then forces the Rayleigh quotient below 2, yielding the theorem. This is the first proof that covers all n, including small cases.

What carries the argument

The load-bearing object is the good pair: two nonempty disjoint vertex sets X and Y such that e_G(X,Y)=0 and ∂_G(A) ≤ 2|A| for A=X,Y, where ∂_G(A) counts edges leaving A. The proof's engine is Lemma 5, which guarantees a good pair in every 3-connected graph with exactly 2n−4 edges. Its proof decomposes the vertex set into degree-3 vertices S and the rest T, uses a postorder traversal of spanning trees of components of G[T] to produce connected sets with controlled boundary weights, and derives a chain of counting inequalities that ultimately force the existence of the good pair. Once a good pair exists, the Rayleigh quotient with the vector taking constant positive value on X, negative value on Y, and zero elsewhere directly gives α(G) ≤ 2.

What would settle it

Produce a graph on n≥4 vertices with at most 2n−4 edges and algebraic connectivity greater than 2; or, equivalently, a 3-connected graph with exactly 2n−4 edges that contains no good pair. Since the paper proves that neither exists, a single such example would refute the theorem, and a finite exhaustive computer search for all graphs up to, say, n=12 would be a concrete way to look.

Watch

Extended reading notes

Core claim

The central discovery is a universal spectral bound: if G is any graph on n≥4 vertices with e(G) ≤ 2n−4, then α(G) ≤ 2. The argument first disposes of disconnected graphs and graphs with a small vertex cut using standard spectral inequalities; only the 3-connected, edge-tight case remains. For that case, the paper proves Lemma 5: every 3-connected graph with n≥4 vertices and exactly 2n−4 edges contains a good pair. The good pair directly supplies a trial vector orthogonal to the all-ones vector whose Dirichlet energy divided by its squared norm is at most 2, so the variational characterization of α gives α(G) ≤ 2. Equality is attained by K_{2,n−2} for every n, and additionally by the Petersen graph when n=10.

Load-bearing premise

Everything depends on Lemma 5, the claim that every 3-connected graph on n≥4 vertices with exactly 2n−4 edges contains a good pair.

Editorial extensions

If this is right

K_{2,n−2} is confirmed as a maximizer of algebraic connectivity among all n-vertex graphs with exactly 2(n−2) edges.
The stronger edge-count bound holds unconditionally: every n-vertex graph with at most 2n−4 edges, connected or not, has α ≤ 2.
The upper bound is sharp for every n≥4, and the remark shows equality is not confined to a single graph.
For consensus and synchronization dynamics, any interaction graph in this sparse regime has a convergence rate determined by an eigenvalue no larger than 2, independent of system size.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The good-pair condition may itself be equivalent to a spectral isoperimetric inequality, suggesting that the bound α ≤ 2 in the sparse regime could be derived from a more general extremal principle for Fiedler values.
The postorder tree decomposition used to find good pairs might transfer to other extremal problems on Laplacian eigenvalues or edge-isoperimetric inequalities in sparse graphs.
A natural check of the structural lemma would be an exhaustive search over 3-connected graphs with exactly 2n−4 edges for n up to 50, independent of the paper's proof; if a graph without a good pair appears, the theorem's strongest form would need revision.
The result suggests that graphs with average degree below 4 − 4/n (i.e., at most 2n−4 edges) cannot be better than a fixed spectral threshold, so any 'good expander' in this density range would need to exceed the edge budget; this contrasts with known expander constructions at higher average degree.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: this paper settles Kolokolnikov's conjecture on algebraic connectivity for all n, and the proof holds up under my reading. The main theorem is sharp: if e(G) ≤ 2n−4, then α(G) ≤ 2, with K_{2,n−2} attaining equality. The novelty is real—prior published work stopped at n≤13, and the independent preprint [10] covers only n≥123; the intermediate range is new, and the proof introduces the good-pair method and a weighted tree decomposition that are likely to be reused.

What the paper does well: the reduction to Lemma 5 is clean. Non-3-connected graphs are dispatched by standard lemmas (a vertex cut of size 1 or 2 gives α≤2 via the deletion bound; disconnected graphs give α=0), and adding edges to reach exactly 2n−4 is monotone for 3-connectivity. For a 3-connected graph, a good pair (X,Y) supplies a two-valued test vector whose Rayleigh quotient is exactly 2. Lemma 5 itself is the hard part: nine claims and a postorder decomposition, with careful bookkeeping. I checked the arithmetic in the small cases (n=8,9,14,15) and the final s=8 contradiction (t≥96 vs t≤47); the inequalities in the main claims are consistent. The AI disclosure for Lemma 7 is transparent, and the lemma is fully reproved in the text, so it is not a black box.

Soft spots, in proportion: the main risk is the sheer length of Section 4. A proof with this many moving parts could hide a subtle indexing error; I could not find one, and the stress-test pass re-derived the key steps without finding a false inequality, but a referee should read Claims 5–8 line by line. The paper also invokes two spectral lemmas without proof; they are standard facts from Fiedler and from Cvetković–Rowlinson–Simić, so that is a minor issue. The remark about non-uniqueness (Petersen graph at n=10) is nice but the equality case is not characterized; that is not required by the conjecture.

Who this is for: spectral graph theorists working on extremal Laplacian eigenvalues, and to a lesser extent people using algebraic connectivity in network consensus problems—though the payoff there is indirect. It deserves a serious referee; the conjecture is named, the proof is complete enough to check, and the intermediate range was genuinely open. Recommend send to review, with the expectation that a careful referee will spend most of their time on Section 4.

Referee Report

0 major / 5 minor

Summary. The paper proves Kolokolnikov's conjecture: for every graph G on n≥4 vertices with at most 2n−4 edges, the algebraic connectivity satisfies α(G)≤2, with equality attained by K_{2,n−2}. The proof reduces the spectral bound to a structural statement, Lemma 5: every 3-connected graph on n≥4 vertices with exactly 2n−4 edges contains two disjoint nonempty sets with no cross edges and with boundary at most twice their size. The Rayleigh quotient then gives α≤2. The bulk of the paper is a proof of Lemma 5 via a sequence of claims and a case analysis on the number s of degree-3 vertices.

Significance. If correct, the paper completely resolves a conjecture that has been open since 2015 and gives a sharp extremal result for algebraic connectivity in the sparse regime, going far beyond the previously known verification for n≤13 and an independent proof for n≥123. The proof is essentially self-contained except for two standard spectral lemmas; the counting inequalities are explicit and involve no free parameters. The main contribution is the structural Lemma 5, whose proof is long but internally consistent; I could not identify a false step. The authors transparently disclose AI assistance in the development of Lemma 7, which is handled appropriately and does not affect the mathematical content.

minor comments (5)

[Section 4, Claim 4] In the n=14 and n=15 subcases, the inference 'Σ_{v∈V(G)} d_G(v) = 2e(G) = 4n−8 gives d_G(x)=4 for every x∈T' is terse; it should explicitly state that every vertex of T has degree at least 4 by the definition of S (since δ(G)≥3), so the degree sum over T forces equality.
[Section 1] The statement α(K_{2,n−2})=2 is used to derive Conjecture 1 from Theorem 2 but is asserted without computation; a one-line derivation from the Laplacian eigenvalues of complete bipartite graphs would make the deduction self-contained.
[Section 3] In the proof of Theorem 2, the phrase 'Adding edges preserves 3-connectivity' should be prefaced by 'If G is 3-connected', because the preceding sentence has already disposed of graphs with a vertex cut of size at most two.
[Lemma 6] The opening sentence 'If v1v2v3v4v5 is an induced path' would be clearer as 'If H contains an induced P5', and the subsequent 2K2 argument is then immediate.
[Section 4] The proof of Lemma 5 is very long; adding a short table or diagram of the case split by s would improve navigability and make the verification easier for readers.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: proof reduces to an independently proved structural lemma plus standard spectral facts.

full rationale

The derivation chain is self-contained and contains no definitional or fitted-input circularity. Theorem 2 is proved by first noting the disconnected and small-cut cases follow from the standard perturbation bound of Cvetković, Rowlinson, and Simić, then adding edges to reach exactly 2n−4 edges and invoking Fiedler's monotonicity, both external spectral facts cited from other authors. The remaining case is handled by Lemma 5, which asserts the existence of a good pair in every 3-connected graph with 2n−4 edges; Lemma 5 is proved from scratch in Section 4 by a long contradiction argument. The Rayleigh quotient step is not circular: the test vector is built from an arbitrary good pair (X,Y), and the numerator bound uses only ∂(X) ≤ 2|X| and ∂(Y) ≤ 2|Y| together with e(X,Y)=0, exactly as the definition of a good pair provides. The good pair property itself is nontrivial and is established independently, not assumed or fitted. No parameter is calibrated against the target quantity, and the conjecture of Kolokolnikov is not used in the proof. The only self-referential element is the disclosure that Lemma 7 was originally suggested by AI, but the paper states that the authors rechecked and refined it and bear responsibility; this is provenance, not a circular argument. No self-citation is load-bearing, and no known result is merely renamed.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The proof is a pure mathematical argument. No free parameters are fitted. The central result rests on standard spectral facts (Rayleigh quotient characterization, Fiedler's spanning subgraph monotonicity, Cvetković's vertex-deletion bound) and elementary graph theory. No new entities are postulated.

assumptions (4)

standard math Rayleigh quotient characterization: α(G)=min_{x⊥1, x≠0} x^T L(G)x / x^T x
Used in Section 3 to bound α(G) by the test vector on the good pair.
standard math Lemma 3 (Fiedler): If H is a spanning subgraph of G then α(H)≤α(G)
Used in the proof of Theorem 2 to reduce to graphs with exactly 2n-4 edges.
standard math Lemma 4 (Cvetković, Rowlinson, Simić): For any U⊆V(G), α(G)≤α(G-U)+|U|
Used to handle graphs with a vertex cut of size 1 or 2.
standard math Elementary graph facts: α(G)>0 iff G is connected; degree sum equals 2e(G); 3-connected implies minimum degree at least 3
Used repeatedly in Sections 2 through 4.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On a conjecture of Kolokolnikov on algebraic connectivity." pith.science (2026). https://pith.science/paper/EFLUQFX5

@misc{pith2026260809822,
  author       = {Pith},
  title        = {Pith review of: On a conjecture of Kolokolnikov on algebraic connectivity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EFLUQFX5}},
  note         = {Machine review of arXiv:2608.09822}
}

abstract

For a graph $G$, let $\alpha(G)$ be the second smallest eigenvalue of the Laplacian matrix of $G$, also known as the algebraic connectivity. Algebraic connectivity plays an important role in characterizing the connectivity of graphs and convergence properties of networks. Kolokolnikov conjectured that among all graphs on $n$ vertices with exactly $2n-4$ edges, $\alpha(G)\leq 2$ and one of the maximizers is the complete bipartite graph whose two parts have sizes two and $n-2$, respectively. In this paper, we completely resolve this conjecture.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[10]

Z. Zhu, J. Li, Y. Ren, J. Liu, Maximizing Algebraic Connectivity with 2(n−2) Edges: The Large Vertex Number Case, arXiv preprint arXiv:2608.07360, 2026

work page Pith review arXiv 2026
[1]

Cvetkovi´ c, P

D. Cvetkovi´ c, P. Rowlinson, S. Simi´ c,An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2010

work page 2010
[2]

Fiedler, Algebraic connectivity of graphs, Czechoslovak Math

M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23(98) (1973) 298–305. 14

work page 1973
[3]

Grone, R

R. Grone, R. Merris, V. S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990) 218–238

work page 1990
[4]

T. Hu, Y. Zong, N. Lu, B. Jiang, Dynamic recovery and a resilience metric for UA V swarms under attack, Drones 9(8) (2025) 589

work page 2025
[5]

Kolokolnikov, Maximizing algebraic connectivity for certain families of graphs, Linear Algebra Appl

T. Kolokolnikov, Maximizing algebraic connectivity for certain families of graphs, Linear Algebra Appl. 471 (2015) 122–140

work page 2015
[6]

Ogiwara, T

K. Ogiwara, T. Fukami, N. Takahashi, Maximizing algebraic connectivity in the space of graphs with a fixed number of vertices and edges, IEEE Trans. Control Netw. Syst. 4 (2017) 359–368

work page 2017
[7]

Olfati Saber, R

R. Olfati Saber, R. M. Murray, Consensus Problems in Networks of Agents With Switching Topology and Time-Delays, IEEE Trans. Automat. Control 49(9) (2004) 1520–1533

work page 2004

Show all 10 references

[8]

L. Wang, A. D. Ames, M. Egerstedt, Multi-objective compositions for collision-free connectivity maintenance in teams of mobile robots, in: Proc. 55th IEEE Conf. De- cision and Control, (2016) 2659–2664

2016
[9]

L. Wang, D. Lu, Y. Zhang, X. Wang, A complex network theory-based modeling framework for unmanned aerial vehicle swarms, Sensors 18(10) (2018) 3434

2018

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [10]

Z. Zhu, J. Li, Y. Ren, J. Liu, Maximizing Algebraic Connectivity with 2(n−2) Edges: The Large Vertex Number Case, arXiv preprint arXiv:2608.07360, 2026

work page Pith review arXiv 2026

[2] [1]

Cvetkovi´ c, P

D. Cvetkovi´ c, P. Rowlinson, S. Simi´ c,An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2010

work page 2010

[3] [2]

Fiedler, Algebraic connectivity of graphs, Czechoslovak Math

M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23(98) (1973) 298–305. 14

work page 1973

[4] [3]

Grone, R

R. Grone, R. Merris, V. S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990) 218–238

work page 1990

[5] [4]

T. Hu, Y. Zong, N. Lu, B. Jiang, Dynamic recovery and a resilience metric for UA V swarms under attack, Drones 9(8) (2025) 589

work page 2025

[6] [5]

Kolokolnikov, Maximizing algebraic connectivity for certain families of graphs, Linear Algebra Appl

T. Kolokolnikov, Maximizing algebraic connectivity for certain families of graphs, Linear Algebra Appl. 471 (2015) 122–140

work page 2015

[7] [6]

Ogiwara, T

K. Ogiwara, T. Fukami, N. Takahashi, Maximizing algebraic connectivity in the space of graphs with a fixed number of vertices and edges, IEEE Trans. Control Netw. Syst. 4 (2017) 359–368

work page 2017

[8] [7]

Olfati Saber, R

R. Olfati Saber, R. M. Murray, Consensus Problems in Networks of Agents With Switching Topology and Time-Delays, IEEE Trans. Automat. Control 49(9) (2004) 1520–1533

work page 2004