{"id":"c3230533-a418-4e3e-ae41-fc1000a412ad","arxiv_id":"2608.09879","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves Kolokolnikov's conjecture alpha(n,2n-4)=2 for all n, with a structural proof for n>=12, and constructs a counterexample to the b=3 analog.","lead":"The paper proves a 2015 conjecture of Kolokolnikov that any graph with n vertices and 2n-4 edges has algebraic connectivity at most 2, making K_{2,n-2} extremal. It also exhibits a 14-vertex counterexample to the analogous K_{3,n-3} bound.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.1 misstates the all-pairs variational formula (missing factor n); Lemma 5.1 silently relies on the corrected version, so the proof of the n=14–19 degree-4 case is formally unsound as written.","rationale":"The reader's weakest assumption is correct and is the main obstacle to accepting the proof as written. I checked the surrounding arguments: the counting in Observations 4.1–4.3, the use of Theorem 2.3 in Theorems 5.1 and 5.2, the partition bound in Lemma 5.3, the trial-vector bound in Lemma 5.4, and the Schur-complement/inertia analysis in Theorem 5.3 all appear internally consistent. The misstated Theorem 2.1 is localized: only Lemma 5.1 invokes it, and the proof there explicitly uses the factor-n form. This is a patchable defect, not a substantive mathematical gap; the conjecture and the structural strategy are very likely correct. I therefore recommend keeping the CONDITIONAL verdict pending the correction.","tokens_in":17180,"tokens_out":14764,"duration_ms":122329,"concrete_test":"Test the printed Theorem 2.1 on K_n with x=(1,-1,0,...,0): the edge sum is 2 and the pair sum is 2, so E/S=1, but a(K_n)=n, disproving the statement. Then verify Lemma 5.1 by recomputing E=3t+64 and the all-pairs sum S for the trial vector (for example, take n=16, t=8, k=3) and checking that the manuscript's inequality 2S-nE≥0 is what is used. Since this inequality gives nE/S≤2, the step “By Theorem 2.1” is valid only if Theorem 2.1 is restated with the factor n multiplying E/S. This retraction and rewrite resolves the concern.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing concern is the misstatement of Fiedler's all-pairs variational characterization in Theorem 2.1. As printed, the theorem asserts a(G)=min(E/S) without the factor n; this is false, since for K_n the quotient E/S is 1 while a(K_n)=n. Lemma 5.1 constructs a trial vector and proves nE/S≤2 (and <2 in the k=4 case), and then concludes a(G)≤2 “by Theorem 2.1”. The conclusion is valid only with the corrected identity a(G)≤nE/S; the manuscript never supplies this correction. Because Theorem 2.1 is used only in Lemma 5.1, the defect is localized and patchable: the rest of the proof rests on Theorems 2.2, 2.3, and the Schur-complement/inertia argument. Nevertheless, as written, the proof of the n=14,...,19 subcase does not follow from the stated theorem, so the central claim is not formally established until the theorem is corrected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17315,"tokens_out":20888,"duration_ms":159508,"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":[{"comment":"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.","section":"Theorem 2.1, Lemma 5.1"}],"minor_comments":[{"comment":"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].","section":"Abstract"},{"comment":"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.","section":"Observation 5.3"},{"comment":"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.","section":"Theorem 5.2 proof"},{"comment":"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.","section":"Theorem 1.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is essentially correct modulo the missing factor n in Theorem 2.1, and the fix is straightforward: insert the factor n in the theorem statement and adjust the citations in Lemma 5.1. The remainder of the proof, especially the Schur-complement/inertia argument in Theorem 5.3, appears valid and carefully executed. Two independent concurrent proofs of the same conjecture are cited, so the novelty claim is not unique; the authors should frame their contribution as an independent structural proof and the counterexample for the b=3 case. I recommend major revision rather than rejection because the identified defect is localized and fully repairable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nThe 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.\n\nEverything 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.\n\nBottom 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.","headline":"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.","tokens_in":17934,"tokens_out":5678,"would_cite":true,"duration_ms":45750,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["algebraic connectivity","extremal graphs","edge boundary","Schur complement","Laplacian eigenvalues","variational characterization","independent sets"],"falsifier":"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)$.","tokens_in":16920,"feed_emoji":"📈","tokens_out":13302,"duration_ms":121127,"temperature":0.7,"pith_summary":"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.","feed_headline":"With 2n-4 edges, algebraic connectivity never exceeds 2","feed_subtitle":"A structural proof for n≥12, with the bipartite graph K_{2,n-2} reaching the bound, closes the 2015 conjecture.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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)$."],"supporting_citations":[{"why":"It states the conjecture and supplies the computational verification for $n\\le 12$ that completes the full range.","marker":"[8]"},{"why":"It supplies the all-pairs variational characterization used for trial-vector upper bounds; the paper's Theorem 2.1 as printed omits the factor $n$ that the later computations use.","marker":"[5]"},{"why":"It supplies the three-part partition polynomial upper bound behind Lemma 5.3.","marker":"[10]"},{"why":"It supplies the edge-boundary inequality used to force edges between candidate sets and derive contradictions.","marker":"[11]"},{"why":"It supplies Schur complement, inertia congruence, and interlacing used in Theorem 5.3 and the appendix.","marker":"[7]"},{"why":"It supplies the determinant-ratio congruence criterion used to certify the 14-vertex example with $a(G)>3$.","marker":"[6]"}],"fun_headline_variants":["2015 conjecture proven: max algebraic connectivity is 2","Sparse graphs: algebraic connectivity never exceeds 2","Proof: with 2n-4 edges, connectivity max is 2","Decade-old graph conjecture proven","2n-4 conjecture proven; 3(n-3) analog false"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["2015 conjecture proven: max algebraic connectivity is 2","Sparse graphs: algebraic connectivity never exceeds 2","Proof: with 2n-4 edges, connectivity max is 2","Decade-old graph conjecture proven","2n-4 conjecture proven; 3(n-3) analog false"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000775,"raw_usage":{"total_tokens":3421,"prompt_tokens":929,"completion_tokens":2492,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":545,"completion_tokens_details":{"reasoning_tokens":2409}},"tokens_in":545,"tokens_out":2492,"duration_ms":18346,"temperature":1.0,"reasoning_tokens":2409,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:14:57.964761+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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)$.","supporting_citations":[{"cited_title":"Kolokolnikov,Maximizing algebraic connectivity for certain families of graphs, Linear Algebra Appl.471(2015), 122–140","cited_arxiv_id":null,"evidence_quote":"It states the conjecture and supplies the computational verification for $n\\le 12$ that completes the full range."},{"cited_title":"J.25(100)(1975), no","cited_arxiv_id":null,"evidence_quote":"It supplies the all-pairs variational characterization used for trial-vector upper bounds; the paper's Theorem 2.1 as printed omits the factor $n$ that the later computations use."},{"cited_title":"Lin and L","cited_arxiv_id":null,"evidence_quote":"It supplies the three-part partition polynomial upper bound behind Lemma 5.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the edge-boundary inequality used to force edges between candidate sets and derive contradictions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies Schur complement, inertia congruence, and interlacing used in Theorem 5.3 and the appendix."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the determinant-ratio congruence criterion used to certify the 14-vertex example with $a(G)>3$."}],"review_version":2}