{"id":"b32e2ae2-3903-48b5-a798-e109b83de968","arxiv_id":"2411.17371","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For Δ=n-2 and Δ=n-3, the connected nonregular graphs of order n with maximum spectral radius are fully characterized: G(n,t) for Δ=n-2, and H1(n) or H2(n) for Δ=n-3.","lead":"This paper identifies, for graphs with n vertices and maximum degree n-2 or n-3, exactly which connected nonregular graph has the largest spectral radius. The answer is a small family of explicit graphs built from cliques, a matching deleted from one block, and one low-degree vertex.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 4 for 59≤n≤99 depends on an unshown computer check; if the asserted sign pattern (15) fails for any n in that range, the extremal characterization may be wrong.","rationale":"The reader’s verdict is CONDITIONAL, with the weakest assumption identified as Lemma 6 and the rationale also mentioning the unverified 59≤n≤99 computation. I agree that Lemma 6 is a genuine external dependency, but because it is a published lemma from Liu 2024, it is a reasonable citation rather than an internal flaw. The more concrete, internally verifiable weak point is the asserted computer check in inequality (15): the paper gives analytic arguments only for n≥100, and the range 59≤n≤99 is dispatched with a non-reproducible computation. Since the theorem explicitly claims n≥59, that finite check is load-bearing. The H2(n) definitional typo is also real: as printed, H2(n) cannot exist because |V3|=2 but H2[V3]=K_{n−7}−M_{(n−7)/2}; the proof and figure make the intended construction clear, so this is a presentation defect rather than a mathematical counterexample. The rest of the argument appears structurally sound: the local switching arguments, quotient matrix comparisons, and the derivation of the δ=n−5 case are internally consistent up to minor typos. Thus my concern does not move the verdict; it reinforces the existing conditional status and gives a precise check that would settle the main remaining gap.","tokens_in":17709,"tokens_out":65156,"duration_ms":560613,"concrete_test":"Evaluate the inequalities in (15) exactly for every integer n with 59≤n≤99 using rational arithmetic, for example by scripting the explicit polynomials f1, f2, and g from the paper. If all four signs match for every n, the computational gap is closed; if any sign differs, Theorem 4 fails for that n and the threshold must be revised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The critical spectral comparison in Case 1, Subcase 1.3 reduces to showing that the largest root of g(λ) is smaller than the largest root of f1(λ) or f2(λ). For n≥100 this is established by the displayed analytic bounds, but for 59≤n≤99 the paper states only: “a direct computation (which we check by computers) also confirms that g(t4)<0, g(t3)>0, g(t2)<0, g(t1)>0” (inequality (15)). No code, output table, or exact arithmetic verification is supplied. Since the theorem’s threshold is n≥59, the entire conclusion for that range rests on this unshown computation: if even one sign in (15) were wrong for some n, the root ordering could reverse and H1(n) or H2(n) might not be the unique extremal graph. This is a concrete internal gap, not a disagreement with consensus. In addition, the definition of H2(n) in Section 1 is internally inconsistent as written: it states |V2|=|V3|=2 while also writing H2[V3]=K_{n−7}−M_{(n−7)/2}, which is impossible for n≥59; the surrounding figure and proof indicate V1 was intended. Finally, Lemma 6 from Liu 2024 is external and load-bearing: the first reductions |S|=1 and |S|∈{1,2} in Theorems 3 and 4 both require it, and the paper neither proves it nor flags it as a dependency. These issues do not by themselves show the central claim is false, but they make the proof not yet fully checkable as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers connected nonregular graphs of order n and maximum degree Δ that attain the maximum spectral radius, denoted G(n,Δ). It proves two structural characterizations: Theorem 3 states that for Δ=n−2 and n≥5 the extremal graphs are exactly G(n,n−3) for odd n and either G(n,n−4) or G(n,2) for even n; Theorem 4 states that for Δ=n−3 and n≥59 the extremal graph is unique, isomorphic to H1(n) for even n and to H2(n) for odd n. The proof reduces the possible degree sequences using Perron-vector monotonicity (Lemma 6), then compares characteristic polynomials of equitable quotient matrices after a series of local switching operations. The final comparison in the Δ=n−3 case is reduced to root ordering of three quartics f1, f2, and g.","tokens_in":18043,"tokens_out":26850,"duration_ms":224611,"significance":"If the proof is completed, the paper gives the first complete extremal-graph characterizations for maximum degree within a constant of the order, and it confirms the Liu–Li and Liu conjectures in these two families. The candidate graphs are explicit and simple, the quotient-matrix computations are deterministic, and the main root comparisons are checkable by hand for n≥100. I found no circularity: the external Lemma 6 is cited from Liu's published work, and the polynomial comparisons are not fitted to the conclusion. The main obstacle to accepting Theorem 4 as proved is the unverified computer-assisted range 59≤n≤99; a second obstacle is that the definition of H2(n) in Section 1 is internally inconsistent. These issues are local and repairable, but they currently prevent the proof from being fully checkable.","major_comments":[{"comment":"The proof of Theorem 4 for 59≤n≤99 depends entirely on the assertion that g(t4)<0, g(t3)>0, g(t2)<0, g(t1)>0, stated as 'a direct computation (which we check by computers)'. No code, output table, or exact arithmetic certificate is provided. Since the threshold of Theorem 4 is n≥59 and the sign pattern is used to locate the roots of g and to conclude ρ(f2)>ρ(g) (or ρ(f1)>ρ(g)), an error in any of these signs for some n in this range would invalidate the extremal characterization. Please supply a verifiable computation for the finitely many n (for example, exact rational arithmetic or Sturm-sequence certificates for the polynomials t↦g(t_i(n))), or extend the analytic estimates down to n=59.","section":"Section 4, inequality (15)"},{"comment":"As written, the bullet list defining H2(n) is inconsistent: it declares |V2|=|V3|=2 while also requiring H2[V3]=K_{n−7}−M_{(n−7)/2}, which is impossible for n≥59. The figure and the proof in Subcase 1.2.2 indicate that V1 and V2 are the two two-vertex sets and V3 is the large set. Please correct the partition data (e.g., |V1|=|V2|=2, H2[V1∪V2]=K4, and H2[V3]=K_{n−7}−M_{(n−7)/2}) and adjust the adjacency bullets accordingly. As it stands, Theorem 4 refers to a graph that is not defined.","section":"Section 1, definition of H2(n)"}],"minor_comments":[{"comment":"The equality between the first 3×3 determinant and the second is not obtained by a valid row operation. The final polynomial f(δ,λ) is correct, but the displayed transformation should be replaced by a valid computation or an algebraic simplification.","section":"Section 3, determinant display"},{"comment":"The displayed simplification '3n²−22n+38' after the lower bound appears to be an algebra slip; the expression evaluates to n²−8n+14. The positivity conclusion is unaffected for n≥59, but the display should be corrected.","section":"Section 4, Subcase 2.1, n-even comparison"},{"comment":"The statement 'Y^T(dI−J_{n−3})Y≥0' should read 'dI−J_d', since Y has dimension d.","section":"Section 2, proof of Lemma 16"},{"comment":"'Similarly as Lemma 12' should refer to Lemma 11.","section":"Section 2, before Lemma 12"},{"comment":"The notation G(n,t) for the auxiliary graph collides with the notation G(n,Δ) for the extremal family; consider using a different symbol for the auxiliary graph.","section":"Section 1, notation"}],"recommendation":"major_revision","confidential_remarks":"The main mathematical line is coherent and I found no circularity. The critical issue is the missing computer verification for 59≤n≤99; if that is supplied and the H2(n) definition is corrected, I would expect to recommend acceptance. The use of Lemma 6 as an external dependency is legitimate, but the authors may want to state it explicitly as an assumption if the target journal requires self-containedness."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The two characterizations are real results. Theorem 3 is clean and complete as far as I checked; Theorem 4 is the substantive one, and the proof strategy—reduce to |S|≤2, then compare quotient polynomials—is the right inheritance from Liu's program. The paper does what it claims: for Δ=n-2 and Δ=n-3 it pins down the extremal graphs exactly, and the n−3 case was open. Credit where due: the authors do not fit parameters; extremal candidates are constructed first and shown optimal by polynomial comparison.\n\nThe soft spots are concrete but not fatal. The biggest is the n=59..99 range in Theorem 4. The sign pattern (15) is asserted to hold by \"direct computation (which we check by computers)\", but no code, output table, or exact arithmetic is provided. Since the theorem threshold is n≥59, the whole conclusion for that range depends on that unshown check. This is not a disagreement with consensus; it is a verification gap. The fix is easy: supply machine-checkable or tabulated verification, or extend the analytic estimates downward.\n\nSecond, the H2(n) definition in Section 1 is internally inconsistent: it says |V2|=|V3|=2 and then writes H2[V3]=K_{n-7}-M_{(n-7)/2}. The proof's G2^(2) makes the intended partition clear enough (the large set is T''), so this is a typo-level defect, but it will confuse a reader and must be fixed. Same for the determinant display in Section 3, which uses a row operation that is not valid as written even though the final polynomial is correct.\n\nThird, Lemma 6 from Liu 2024 is load-bearing for both structural reductions. It is a published result, not a self-citation problem, but the paper treats it as background and does not flag how much of Theorems 3 and 4 depends on it. A one-sentence dependency statement would be appropriate.\n\nMy bottom line: the central argument holds up in outline, the results are new, and I found no sign of cooked data or circular fitting. The paper deserves a serious referee. I would ask the authors to close the finite-check gap and clean up the typos before acceptance, but this should not be desk-rejected.\n\nWho benefits: people working on spectral extremal graph theory, especially the Liu–Li conjecture. I would take it to reading group and would cite it once the finite check is resolved.","headline":"Genuine new characterizations for Δ=n-2 and Δ=n-3; Theorem 4 is very likely correct but the unshown 59≤n≤99 computer check needs to be supplied.","tokens_in":18567,"tokens_out":3333,"would_cite":true,"duration_ms":30182,"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":"For connected nonregular graphs with maximum degree $n-2$ or $n-3$, the paper identifies exactly which graphs maximize the spectral radius, confirming the degree-sequence conjecture in these cases.","keywords":["spectral radius","nonregular graphs","maximum degree","Perron vector","equitable partition","quotient matrix","extremal graphs"],"falsifier":"Find a connected nonregular graph with $\\Delta=n-3$ and $n\\ge 59$ whose spectral radius exceeds that of $H_1(n)$ (even $n$) or $H_2(n)$ (odd $n$), or exhibit a counterexample to the cited monotonicity lemma: two deficient vertices $u,v$ with $x_v\\le x_u$ but $N_T(v)$ not contained in $N_T(u)$. For the claimed threshold, a symbolic verification of the sign pattern (15) for all $59\\le n\\le 99$ would test the only computer-assisted step.","tokens_in":17516,"feed_emoji":"📐","tokens_out":9597,"duration_ms":80664,"temperature":0.7,"pith_summary":"This paper settles, in two families of near-complete graphs, the question of which connected nonregular graph with $n$ vertices and maximum degree $\\Delta$ has the largest spectral radius. When $\\Delta=n-2$, it proves that every such extremal graph is one of two explicitly constructed block graphs, with the choice depending on whether $n$ is even or odd. When $\\Delta=n-3$ and $n\\ge 59$, it proves the extremal graph is unique: a specified graph $H_1(n)$ for even $n$ and $H_2(n)$ for odd $n$. These are the first complete structural characterizations for $\\Delta$ this close to $n$, and they confirm the degree-sequence conjecture from 2008 in these cases. The proof confines the vertices of degree below $\\Delta$ to a set of size one or two and then compares explicit characteristic polynomials.","feed_headline":"Unique spectral-radius winner found when Δ=n−3, n≥59","feed_subtitle":"For Δ=n−2 the maximizers are two explicit graphs; for Δ=n−3 the winner is one named graph.","key_machinery":"The workhorse is the Perron vector $x$ of the adjacency matrix, partitioned by $S$ (vertices with degree below $\\Delta$) and $T$ (vertices with degree $\\Delta$). A lemma cited from earlier work says that in an extremal graph, for deficient vertices $u,v$, $x_v\\le x_u$ exactly when the $T$-neighbourhood of $v$ is contained in that of $u$; combined with completeness of $G[S]$, this forces $|S|=1$ for $\\Delta=n-2$ and $|S|\\in\\{1,2\\}$ for $\\Delta=n-3$. Once the degree sequence is fixed, the graph is built from components whose complement is a union of paths and cycles, and edge-switching operations are used to show any configuration except the claimed ones can be improved. For the final comparison, the graphs carry equitable partitions whose quotient matrices have explicit characteristic polynomials (a cubic for $\\Delta=n-2$ and quartics for $\\Delta=n-3$); comparing their largest real roots selects the extremal graph.","core_discovery":"The paper's central discovery is a complete classification of the spectral-radius-extremal connected nonregular graphs when the maximum degree is $n-2$ or $n-3$. Theorem 3 states that for $n\\ge 5$, a graph in $\\mathcal{G}(n,n-2)$ is isomorphic to $G(n,n-3)$ when $n$ is odd, and to $G(n,n-4)$ or $G(n,2)$ when $n$ is even, where $G(n,t)$ is the graph built from a vertex $u$ joined to $K_t$ with a perfect matching removed, that graph joined completely to $K_{n-t-1}$. Theorem 4 states that for $n\\ge 59$, a graph in $\\mathcal{G}(n,n-3)$ is isomorphic to $H_1(n)$ for even $n$ and $H_2(n)$ for odd $n$. Thus the extremal graph for $\\Delta=n-3$ is unique and has degree sequence $(\\Delta,\\ldots,\\Delta,1)$ for even $n$ and $(\\Delta,\\ldots,\\Delta,2)$ for odd $n$, the smallest minimum degree allowed by parity.","pith_inferences":["If the same quotient-matrix pattern persists for $\\Delta=n-c$ with fixed $c$, one would expect a similar parity-driven dichotomy: unique extremal graphs for odd $n$ and a small finite list for even $n$, with minimum degree $1$ or $2$; this is an extension the paper does not state.","The $n\\ge 59$ threshold rests on a finite computer check of the sign pattern (15) for $59\\le n\\le 99$; making that interval check fully symbolic or publishing the verification table would remove the only non-human step from the proof.","The quantitative inequalities in (9)--(11) could support a stability version of Theorem 4: any graph whose spectral radius is within $\\varepsilon$ of the maximal value should have small $S$ and complement structure close to $H_1(n)$ or $H_2(n)$."],"forward_implications":["For $\\Delta=n-3$ and $n\\ge 59$, spectral-radius maximization has a unique solution: $H_1(n)$ for even $n$, $H_2(n)$ for odd $n$; every other connected nonregular graph with the same order and maximum degree has strictly smaller spectral radius.","For $\\Delta=n-2$ and $n\\ge 5$, the extremal graphs are exactly the three explicit families $G(n,n-3)$, $G(n,n-4)$, and $G(n,2)$, with the choice fixed by parity.","The extremal graph for $\\Delta=n-3$ has minimum degree $1$ (even $n$) or $2$ (odd $n$), the smallest positive value allowed by parity, so in these regimes the gap $\\Delta-\\rho(G)$ is as large as the structure permits.","The spectral radius of the extremal graph is the largest real root of one of the explicit characteristic polynomials derived from quotient matrices, giving a direct numerical route to the gap $\\Delta-\\lambda_1(n,\\Delta)$ for these $\\Delta$."],"supporting_citations":[{"why":"Supplies Lemma 6, the key monotonicity lemma tying Perron-vector order on deficient vertices to $T$-neighbourhood containment, plus Lemma 7 and the modified conjecture.","marker":"[8]"},{"why":"Proposed the original degree-sequence conjecture that the paper confirms for $\\Delta=n-2,n-3$.","marker":"[10]"},{"why":"Supplies Lemma 5, stating that the subgraph induced by the deficient vertices is complete.","marker":"[11]"},{"why":"Supplies the local switching lemma (Lemma 8) used to show certain edge replacements increase spectral radius, and the polynomial comparison lemma (Lemma 11).","marker":"[5]"},{"why":"Supplies the quotient-matrix interlacing lemma (Lemma 9), which lets the paper compute extremal spectral radii from small explicit matrices.","marker":"[7]"},{"why":"Supplies the Rayleigh-quotient characterization and Perron--Frobenius theorem used to identify spectral radius with the largest real root of these polynomials.","marker":"[15]"}],"fun_headline_variants":["Extremal graph for Δ=n−3 is unique for n≥59","Spectral-radius extremal graph for Δ=n−3 is unique","For Δ=n−3, the maximizer is a single graph (n≥59)","Nonregular graph maximizing spectral radius: unique for Δ=n−3","Complete classification: extremal graphs for Δ=n−2 and Δ=n−3"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is a lemma cited from earlier work, not proved here, asserting that in any extremal graph, comparing Perron-vector entries of two deficient vertices is the same as comparing containment of their neighbourhoods inside the full-degree set; the structural reductions that shrink $S$ to size one or two all hang on it.","fun_headline_variants_meta":{"raw":{"variants":["Extremal graph for Δ=n−3 is unique for n≥59","Spectral-radius extremal graph for Δ=n−3 is unique","For Δ=n−3, the maximizer is a single graph (n≥59)","Nonregular graph maximizing spectral radius: unique for Δ=n−3","Complete classification: extremal graphs for Δ=n−2 and Δ=n−3"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000939,"raw_usage":{"total_tokens":4028,"prompt_tokens":975,"completion_tokens":3053,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":591,"completion_tokens_details":{"reasoning_tokens":2953}},"tokens_in":591,"tokens_out":3053,"duration_ms":20720,"temperature":1.0,"reasoning_tokens":2953,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:12:11.733072+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a connected nonregular graph with $\\Delta=n-3$ and $n\\ge 59$ whose spectral radius exceeds that of $H_1(n)$ (even $n$) or $H_2(n)$ (odd $n$), or exhibit a counterexample to the cited monotonicity lemma: two deficient vertices $u,v$ with $x_v\\le x_u$ but $N_T(v)$ not contained in $N_T(u)$. For the claimed threshold, a symbolic verification of the sign pattern (15) for all $59\\le n\\le 99$ would test the only computer-assisted step.","supporting_citations":[{"cited_title":"Liu, Extremal spectral radius of nonregular graphs with pre scribed maximum degree, J","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 6, the key monotonicity lemma tying Perron-vector order on deficient vertices to $T$-neighbourhood containment, plus Lemma 7 and the modified conjecture."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proposed the original degree-sequence conjecture that the paper confirms for $\\Delta=n-2,n-3$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 5, stating that the subgraph induced by the deficient vertices is complete."},{"cited_title":"Cvetkovi´ c, P","cited_arxiv_id":null,"evidence_quote":"Supplies the local switching lemma (Lemma 8) used to show certain edge replacements increase spectral radius, and the polynomial comparison lemma (Lemma 11)."},{"cited_title":"Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl","cited_arxiv_id":null,"evidence_quote":"Supplies the quotient-matrix interlacing lemma (Lemma 9), which lets the paper compute extremal spectral radii from small explicit matrices."},{"cited_title":"Zhan, Matrix Theory, Graduate Studies in Mathematics, vol","cited_arxiv_id":null,"evidence_quote":"Supplies the Rayleigh-quotient characterization and Perron--Frobenius theorem used to identify spectral radius with the largest real root of these polynomials."}],"review_version":1}