Maximizing the algebraic connectivity of graphs of given order and size: a proof of a conjecture of Kolokolnikov

Abhay Jayarajan; M. Rajesh Kannan; Rahul Roy; Sebastian M. Cioab\u{a}

REVIEW 1 major objections 4 minor 20 references

Maximizing the algebraic connectivity of graphs of given order and size: a proof of a conjecture of Kolokolnikov

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The paper proves the 2015 conjecture: every graph with $n$ vertices and $2n-4$ edges has algebraic connectivity at most $2$, with $K_{2,n-2}$ attaining the bound.

desk verdict Resolves Kolokolnikov's conjecture with a mostly sound structural proof; one misstated theorem (missing factor n) is a real but local defect that is easy to fix. read the letter →

arxiv 2608.09879 v2 pith:3CIORN5V submitted 2026-08-10 math.CO

Sebastian M. Cioabă , Abhay Jayarajan , M. Rajesh Kannan , Rahul Roy This is my paper · ORCID

classification math.CO MSC 05C5005C35

keywords algebraicconnectivityextremalgraphsedgeboundarySchurcomplementLaplacianeigenvaluesvariationalcharacterizationindependentsets

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 establishes the 2015 conjecture that, among all simple graphs with $n$ vertices and $2n-4$ edges, the second-smallest Laplacian eigenvalue $a(G)$ (the algebraic connectivity) is never larger than $2$. Since the range $n\le 12$ was already checked computationally, the structural proof for $n\ge 12$ settles the extremal value $\alpha(n,2n-4)=2$ for every $n\ge 4$. The complete bipartite graph $K_{2,n-2}$ attains the bound, and the authors identify other small extremal graphs. As a secondary point, they construct a 14-vertex graph with 33 edges whose algebraic connectivity exceeds 3, so the analogous claim for $3(n-3)$ edges is false.

What carries the argument

The engine is the variational characterization of algebraic connectivity: for any nonconstant vector $x$, $a(G)\le n\,\frac{\sum_{uv\in E}(x_u-x_v)^2}{\sum_{i<j}(x_i-x_j)^2}$, so exhibiting a trial vector with quotient at most $2$ certifies the bound. (The paper's Theorem 2.1 as printed drops the factor $n$; the subsequent computations restore it.) Two inequalities do the structural work: a three-part partition bound (Theorem 2.2) that reduces $a(G)\le y$ to checking a quadratic polynomial, and an edge-boundary inequality (Theorem 2.3) that forces an edge between any two disjoint sets whose boundary ratios are both below $a(G)$. The final case analyzes $L(G)-2I$ via Schur complements and inertia, using the sign pattern of this matrix to rule out $a(G)>2$. The recurring objects are the degree-3 set $T$, the degree-4 vertices $R$ with exactly one neighbor in $T$, and the high-degree vertices $U$ with few internal neighbors.

What would settle it

Enumerate (or search by spectral computation) all simple graphs on 13 vertices with 22 edges; Theorem 1.1 asserts every such graph has $a(G)\le2$, so any graph with $a(G)>2$ disproves the conjecture. A more local check is to evaluate the printed quotient in Theorem 2.1 on $K_n$: the ratio is $1$, not $n$, confirming that the proof as written depends on restoring the factor $n$ before its displayed inequalities can bound $a(G)$.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.1: if $G$ is a connected graph with $n\ge12$ vertices and $2n-4$ edges, then $a(G)\le 2$, and therefore $\alpha(n,2n-4)=2$. The proof first uses the average-degree bound to eliminate $\delta(G)\ge4$ and observes that $\delta(G)\le2$ is immediate, leaving only the case $\delta(G)=3$; the rest is a structural case analysis on $T$, the set of degree-3 vertices. When $T$ has an edge, a short boundary-count argument forces a contradiction with $a(G)>2$. When $T$ is independent, the proof splits further according to the presence and location of degree-4 vertices, using trial vectors, partition bounds, and eventually Schur complements and inertia of $L(G)-2I$. The paper also gives a 14-vertex, 33-edge graph with $a(G)>3$, disproving the analogous statement for $3(n-3)$ edges.

Load-bearing premise

The proof's trial-vector bounds depend on the all-pairs variational characterization in its factor-$n$ form, $a(G)\le n\,\frac{\sum_{uv\in E}(x_u-x_v)^2}{\sum_{i<j}(x_i-x_j)^2}$; as printed, Theorem 2.1 states this without the factor $n$, so the derivation of $a(G)<2$ from the computed quotients relies on an unstated correction to that theorem.

Editorial extensions

If this is right

For every $n\ge4$, $\alpha(n,2n-4)=2$, and $K_{2,n-2}$ is an extremal graph; at $n=8$ and $n=10$ other graphs also attain $2$.
Any graph with $n$ vertices and $2n-4$ edges has minimum degree at most $3$; the only case needing proof is $\delta(G)=3$, so the conjecture is, in effect, a statement about the placement of degree-3 vertices.
The proof for $n\ge12$ is fully structural and does not rely on computer enumeration, so the result is checkable by hand once the case split is granted.
The 14-vertex example with 33 edges shows $K_{3,n-3}$ is not generally the algebraic-connectivity maximizer at $m=3(n-3)$.

Reading between the lines

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

Editorial inference: the missing factor $n$ in Theorem 2.1 is a normalization error; any reader applying the printed formula would compare $a(G)$ against sums over all pairs instead of $n$ times that quotient, so the proof should be read as relying on the corrected statement.
Editorial inference: the identity $\sum_{u\notin T}(d(u)-4)=t-8$ converts the constraint $m=2n-4$ into a surplus count on non-degree-3 vertices; analogous surplus identities should give exact or near-exact maxima for other linear edge densities $m=cn$.
Editorial inference: the degree-4 set $R$ and the high-degree set $U$ are the only flexible parts of the extremal configuration; a natural next step is to characterize all maximizing graphs for each $n$, not just the value of the maximum.
Editorial inference: for $m=3(n-3)$, the appendix's counterexample suggests the true maximizer is not complete bipartite; locating it for general $n$ is a testable extension of the same machinery.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

Short version: this is the paper that actually proves Kolokolnikov's conjecture, and it deserves a serious referee. The main theorem — a(G) ≤ 2 for every n ≥ 12 with 2n−4 edges, with K_{2,n−2} extremal — is very likely true, and the proof is a real structural proof, not a computer-assisted case check. The authors also show the b=3 analog fails with an explicit 14-vertex graph, which is a nice bonus.

What's new: the conjecture was open since 2015 except for n ≤ 12 computational verification. This paper gives a clean decomposition: δ ≤ 2 trivial; δ=3, then separate on whether the degree-3 vertices form an independent set. The non-independent case uses a short edge-boundary argument via Liu–Hong–Gu–Lai. The independent case splits into several subcases using degree-deficit counting, Theorem 2.3, a trial vector, and a Schur complement/inertia argument. It all hangs together.

The one real problem: Theorem 2.1 misstates Fiedler's all-pairs characterization. As printed, it says a(G)= min E/S, but the correct identity is a(G)= n · min E/S (for K_n the printed quotient is 1, not n). The proof of Lemma 5.1 proves nE/S < 2 and then invokes "Theorem 2.1" to conclude a(G)<2. That conclusion only follows from the corrected identity. So the formal derivation in that lemma is unsound as written. It's patchable — you just fix the statement and keep the calculation — but a careful referee will need to flag it. There's also a minor arithmetic typo in Observation 5.1 that doesn't affect the logic.

Everything else looks solid. The rest of the paper doesn't use Theorem 2.1, and I didn't find hidden circularity or invented entities. The counting arguments are checkable and the Schur-complement proof is explicit.

Bottom line: this is a good paper that should be published after a minor revision. Send it to a referee who can verify the case analysis, and make the author correct Theorem 2.1 and the typo. I'd accept a peer review invitation for this.

Referee Report

1 major / 4 minor

Summary. The paper studies the maximum algebraic connectivity α(n,m) over all graphs with n vertices and m edges. The main result (Theorem 1.1) asserts that for n≥12 and m=2n−4, every graph satisfies a(G)≤2, so that α(n,2n−4)=2, thereby settling a 2015 conjecture of Kolokolnikov when combined with the previously known computational verification for n≤12. The proof is structural and divides into cases according to the minimum degree, the independence or otherwise of the set T of degree-3 vertices, and the presence of degree-4 vertices. The arguments use Fiedler's variational principle, the Lin–Miao partition bound, the Liu–Hong–Gu–Lai edge lemma, trial vectors, edge-boundary estimates, and a Schur-complement/inertia argument. The paper also gives a 14-vertex graph with 33 edges showing that α(n,3(n−3))=3 is false in general.

Significance. If the proof is correct, the paper settles a conjecture that has been open since 2015 and provides an entirely structural, enumeration-free argument for all n≥12. The combination of degree-deficit counting, small-edge-boundary arguments, and Schur-complement inertia techniques is a useful methodological contribution. The appendix contains an explicit counterexample to the analogous statement for b=3, which is a valuable complement. The proof is self-contained apart from standard cited results, and the central claim is falsifiable and precisely stated. However, the manuscript contains a misstatement of Fiedler's all-pairs variational characterization that is load-bearing in one subcase, so the proof as written is not formally complete.

major comments (1)

[Theorem 2.1, Lemma 5.1] Theorem 2.1 is stated without the factor n: it claims a(G) = min ∑_E (x_i−x_j)^2 / ∑_{i<j}(x_i−x_j)^2. This is false as printed; for K_n the quotient equals 1 for every nonconstant vector, while a(K_n)=n. Lemma 5.1 twice uses the corrected form, namely a(G) ≤ n · ∑_E (x_i−x_j)^2 / ∑_{i<j}(x_i−x_j)^2: the displayed computations show that 2·(all-pairs sum) − n·(edge sum) is nonnegative/positive and then conclude a(G)≤2 or a(G)<2 “by Theorem 2.1.” Without correcting Theorem 2.1, the derivation of the n=14,...,19 subcase with a degree-4 vertex does not follow from the stated theorem. Please restate Theorem 2.1 with the factor n and make explicit in Lemma 5.1 that the trial vector is being used with the corrected identity. Since Theorem 2.1 is used only in Lemma 5.1, the defect is localized, but it is load-bearing as written.

minor comments (4)

[Abstract] The abstract contains a leftover LaTeX comment beginning with “%Combined with the computational verification...”. Either remove it or incorporate it explicitly, because the statement “we prove Kolokolnikov's conjecture” in the abstract and the final remarks should be qualified: the proof covers n≥12, and the remaining cases n≤11 come from the computational verification in [8].
[Observation 5.3] The display for e(S) is ambiguous: it should read e(S) ≤ (|T^c| − 2t − 8 + 3s)/2, not “|T^c| −2t−8 + 3s / 2”. The same formatting issue appears in the proof of Theorem 5.2.
[Theorem 5.2 proof] The notation e(G^c[S]) is used without defining G^c. Please define the complement graph or write “non-edges of G[S]” instead.
[Theorem 1.1] The word “Consequently” in Theorem 1.1 implicitly uses the lower bound a(K_{2,n−2})=2. Since this graph is explicitly mentioned in the introduction and final remarks, the reader can fill this in, but a brief parenthetical would make the deduction fully explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a self-contained structural derivation using standard external theorems; no fitted parameter is renamed as a prediction.

full rationale

The paper proves Kolokolnikov's conjecture for n ≥ 12 by a case analysis built from Laplacian eigenvalue bounds. The target quantity a(G) is defined independently via the Laplacian spectrum, and each upper-bound step invokes either the standard Rayleigh-quotient characterization, the external Lin–Miao bound (Theorem 2.2), the Liu–Hong–Gu–Lai edge lemma (Theorem 2.3), or standard congruence/inertia/interlacing facts from Horn–Johnson and Gantmacher. No parameter is fitted to a data subset and then reported as a prediction; no quantity is defined in terms of the conjecture; and no load-bearing step reduces by construction to its own input. The only appearance of the authors' own prior work is reference [3], cited in the introduction for related context on regular graphs, and it is not used in any proof step. The independent concurrent proofs [2] and [19] are mentioned but are not needed for the argument. The misstatement in Theorem 2.1, which omits the factor n from the all-pairs variational quotient, is a correctness or typographical defect in a quoted external theorem, not a circularity: Lemma 5.1 uses the correct n-scaled quotient, and the defect is localized and patchable. Because the derivation is self-contained against external benchmarks and does not define its target quantity in terms of its own conclusions, the circularity score is 0.

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

All axioms are established results in spectral graph theory and matrix analysis, cited from the literature; none are introduced ad hoc for this paper. There are no free parameters or invented entities.

assumptions (5)

standard math Fiedler's variational characterization: a(G) = min over nonconstant vectors x of E/S with the correct factor-n normalization (Theorem 2.1, as corrected).
Used in Lemma 5.1 to upper-bound a(G) by a trial vector. The printed statement omits the factor n; the intended theorem is standard.
standard math Lin-Miao upper bound via a 3-partition (Theorem 2.2).
Used in Lemma 5.3 Case 1 to show a(G) < 2 via polynomial p(2) < 0.
standard math Liu-Hong-Gu-Lai inequality relating edge counts between vertex subsets to algebraic connectivity (Theorem 2.3).
Used in Theorem 5.1, Lemma 5.2, Lemma 5.3 Case 2, and Observation 5.5.
standard math Schur complement congruence and Sylvester's law of inertia (Lemmas 5.5, 5.6).
Used in Theorem 5.3 to transfer eigenvalue counts from the Schur complement M to L(G)-2I.
standard math Cauchy interlacing for principal submatrices (Lemma 5.7).
Used in Theorem 5.3 Claim 1 to force nonpositive eigenvalues of M from a 4x4 submatrix.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Maximizing the algebraic connectivity of graphs of given order and size: a proof of a conjecture of Kolokolnikov." pith.science (2026). https://pith.science/paper/3CIORN5V

@misc{pith2026260809879,
  author       = {Pith},
  title        = {Pith review of: Maximizing the algebraic connectivity of graphs of given order and size: a proof of a conjecture of Kolokolnikov},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3CIORN5V}},
  note         = {Machine review of arXiv:2608.09879}
}

abstract

The algebraic connectivity of a graph $G$ is a well-studied graph invariant that is related to other properties of the graph such as connectivity and expansion. Given $n$ and $m$, $\alpha(n,m)$ is the maximum algebraic connectivity of a graph with $n$ vertices and $m$ edges. In 2015, Kolokolnikov conjectured that $\alpha(n,2n-4)=2$ for $n\geq 4$, and verified this claim computationally for $n \le 12$. In this paper, we prove Kolokolnikov's conjecture. We also show that $\alpha(n,3(n-3)) = 3$ is false in general. %Combined with the computational verification for $n \le 12$, this yields $\alpha(n,2n-4)=2$ for all admissible values of $n$.

Figures

Figures reproduced from arXiv: 2608.09879 by the authors.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 19 canonical work pages

[1]

A. E. Brouwer and W. H. Haemers,Spectra of graphs, Universitext, Springer, New York,

work page
[2]

C. Chi, J. Wang, and J. Zheng,On a conjecture of kolokolnikov on algebraic connectivity,

work page
[3]

S. M. Cioab˘ a, J. H. Koolen, Nozaki H., and J. R. Vermette,Maximizing the order of a regular graph of given valency and second eigenvalue, SIAM J. Discrete Math.30 (2016), no. 3, 1509–1525. MR 3537002

work page 2016
[4]

Fiedler,Algebraic connectivity of graphs, Czechoslovak Math

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

work page 1973
[5]

J.25(100)(1975), no

,A property of eigenvectors of nonnegative symmetric matrices and its appli- cation to graph theory, Czechoslovak Math. J.25(100)(1975), no. 4, 619–633. MR 387321

work page 1975
[6]

F. R. Gantmacher,Matrizenrechnung. II. Spezielle Fragen und Anwendungen, Hochschulb¨ ucher f¨ ur Mathematik [University Books for Mathematics], vol. Band 37, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959. MR 107647

work page 1959
[7]

R. A. Horn and C. R. Johnson,Matrix analysis, second ed., Cambridge University Press, Cambridge, 2013. MR 2978290

work page 2013
[8]

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

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

work page 2015

Show all 20 references

[9]

2, 215–229

Arbind Kumar Lal, Kamal Lochan Patra, and Binod Kumar Sahoo,Algebraic connectiv- ity of connected graphs with fixed number of pendant vertices, Graphs and Combinatorics 27(2011), no. 2, 215–229

2011
[10]

Lin and L

Z. Lin and L. Miao,Upper bounds on the algebraic connectivity of graphs, Electron. J. Linear Algebra38(2022), 77–84. MR 4387572 23

2022
[11]

Q. Liu, Y. Hong, X. Gu, and H.-J. Lai,Note on edge-disjoint spanning trees and eigen- values, Linear Algebra Appl.458(2014), 128–133. MR 3231810

2014
[12]

Maas,Transportation in graphs and the admittance spectrum, Discrete Applied Math- ematics16(1987), no

C. Maas,Transportation in graphs and the admittance spectrum, Discrete Applied Math- ematics16(1987), no. 1, 31–49

1987
[13]

Merris,Characteristic vertices of trees, Linear and multilinear algebra22(1987), no

R. Merris,Characteristic vertices of trees, Linear and multilinear algebra22(1987), no. 2, 115–131

1987
[14]

Mohar,The Laplacian spectrum of graphs, Graph theory, combinatorics, and appli- cations, Vol

B. Mohar,The Laplacian spectrum of graphs, Graph theory, combinatorics, and appli- cations, Vol. 2. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs held at Western Michigan University, Kalamazoo, MI, USA, May 30-June 3, 19...

1988
[15]

109, 1992, Algebraic graph theory (Leibnitz, 1989), pp

,Laplace eigenvalues of graphs—a survey, vol. 109, 1992, Algebraic graph theory (Leibnitz, 1989), pp. 171–183. MR 1192380

1992
[16]

6, 677–679

Damon Mosk-Aoyama,Maximum algebraic connectivity augmentation is np-hard, Op- erations Research Letters36(2008), no. 6, 677–679

2008
[17]

Nozaki,Linear programming bounds for regular graphs, Graphs Combin.31(2015), no

H. Nozaki,Linear programming bounds for regular graphs, Graphs Combin.31(2015), no. 6, 1973–1984. MR 3417208

2015
[18]

D. A. Spielman and S.-H. Teng,Spectral partitioning works: planar graphs and finite element meshes, Linear Algebra Appl.421(2007), no. 2-3, 284–305. MR 2294342

2007
[19]

Z. Zhu, J. Li, Y. Ren, and Ji Liu,Maximizing algebraic connectivity with2(n−2)edges: The large vertex number case, 2026. https://arxiv.org/abs/2608.07360. A Appendix Lemma A.1.[6] LetAbe a real symmetric matrix. Let∆ k be the determinant of thek-th leading principal submatrix....

2026 arXiv
[2026]

https://arxiv.org/abs/2608.09822

arXiv

Pith tools

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

[1] [1]

A. E. Brouwer and W. H. Haemers,Spectra of graphs, Universitext, Springer, New York,

work page

[2] [2]

C. Chi, J. Wang, and J. Zheng,On a conjecture of kolokolnikov on algebraic connectivity,

work page

[3] [3]

S. M. Cioab˘ a, J. H. Koolen, Nozaki H., and J. R. Vermette,Maximizing the order of a regular graph of given valency and second eigenvalue, SIAM J. Discrete Math.30 (2016), no. 3, 1509–1525. MR 3537002

work page 2016

[4] [4]

Fiedler,Algebraic connectivity of graphs, Czechoslovak Math

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

work page 1973

[5] [5]

J.25(100)(1975), no

,A property of eigenvectors of nonnegative symmetric matrices and its appli- cation to graph theory, Czechoslovak Math. J.25(100)(1975), no. 4, 619–633. MR 387321

work page 1975

[6] [6]

F. R. Gantmacher,Matrizenrechnung. II. Spezielle Fragen und Anwendungen, Hochschulb¨ ucher f¨ ur Mathematik [University Books for Mathematics], vol. Band 37, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959. MR 107647

work page 1959

[7] [7]

R. A. Horn and C. R. Johnson,Matrix analysis, second ed., Cambridge University Press, Cambridge, 2013. MR 2978290

work page 2013

[8] [8]

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

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

work page 2015