{"id":"19c63bbf-7cdd-4e1e-be80-a56db0b1b22a","arxiv_id":"2411.14835","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives an explicit if-and-only-if classification of all connected graphs G for which the eigenvalue multiplicity of L(G) attains 2c(G)+p(G)-1.","lead":"This paper completely characterizes the connected graphs whose line graph has an eigenvalue with the largest possible multiplicity, matching a known bound. It resolves an open problem raised in a 2024 paper, extending earlier results for trees and for the eigenvalue minus one.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.4's non-cycle case is delegated to [2] without a self-contained proof, and the entire induction depends on it.","rationale":"The paper's central claim is a complete characterization of connected non-cycle G for which L(G) attains the Chang et al. bound. For this to be true, three ingredients must hold: the upper bound (imported), the tree case (imported), and the reduction lemma that lets one peel off cycle edges one at a time (Lemma 3.4). The first two are from published papers and are cited explicitly; the third is partially proved and partially outsourced. Since Lemma 3.4 is applied repeatedly in Corollary 3.5 to determine the possible λ and in the induction in Theorem 1.2 to reduce to the tree case, any failure of its 'if' or 'only if' direction in the non-cycle case would break the classification. The reader's weakest-assumption analysis identifies exactly this point, and I agree. The other omissions—Claim 4 and the parity of x'—are real but smaller: they concern specific subcases of Theorems 3.6 and 3.7, and the surrounding arguments strongly suggest they are fillable. They do, however, add to the difficulty of verifying the paper without access to [2] or a computer search. I found no internal contradiction in the parts that are written out, and the 'if' parts of Theorems 3.6, 3.7, and 1.2 are explicit interlacing arguments with correct counts. The novelty is clear: the arbitrary-eigenvalue extremal problem was open, and the paper gives a plausible and testable classification. The appropriate verdict is therefore the same as the reader's: conditional acceptance pending a self-contained proof or independent verification of Lemma 3.4's non-cycle case.","tokens_in":14702,"tokens_out":15212,"duration_ms":147111,"concrete_test":"Extract the exact statement and proof of Theorem 3.2 of [2] and check that it implies both directions of Lemma 3.4 for arbitrary λ when G-e is not a cycle, with no extra hypotheses on e. Independently, run an exhaustive enumeration of all connected graphs on at most 8 vertices: compute the spectrum of each line graph, compare the graphs attaining m_{L(G)}(λ)=2c(G)+p(G)-1 with the five families of Theorem 1.2, and verify the equivalence in Lemma 3.4 for every edge e in every applicable graph. A counterexample would refute the classification; a clean pass would show the gaps are presentational.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3.4 is the pivotal reduction: every step of the induction in Corollary 3.5 and the 'only if' part of Theorem 1.2 prunes an edge e by invoking it. The paper proves the G-e-cycle branch in detail, but for the non-cycle branch the proof consists of the sentence 'by the proof of Theorem 3.2 in [2]', with the statement of [2, Thm. 3.2] not reproduced. What is needed is a precise equivalence for arbitrary λ: L(G) is λ-optimal iff L(G-e) is λ-optimal, p(G-e)=p(G)+1, and m_{L(G)}(λ)=m_{L(G-e)}(λ)+1. The 'if' direction is the one that makes the pruning induction legitimate; if [2]'s result only gives the upper bound or only treats λ=-1, or if it silently assumes some extra property of e beyond being on a cycle and incident to a major vertex, then the main theorem is not established. The paper also explicitly omits Claim 4 (d_T(y)=1, 'similar to Claim 3') and the parity of x' in Theorem 3.7 ('by similar discussion'), both needed to rule out non-pendant attachments and the θ(k',x',l') case. None of this shows the classification is false, but the proof as written is not completely verifiable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper characterizes, for every connected graph G that is not a cycle, exactly when the line graph L(G) has an eigenvalue λ of maximum possible multiplicity 2c(G)+p(G)-1. Theorem 1.2 gives five explicit families: paths with distance congruence, the extremal trees of [12], unicyclic and bicyclic graphs obtained by attaching cycles of specified lengths to optimal trees, two cycles joined by an edge, and graphs with c(G)≥3 cycles attached to c(G) distinct pendant vertices of an optimal tree. The proof proceeds by induction on the cyclomatic number, with Lemma 3.4 as the pruning step that reduces optimality of L(G) to optimality of L(G-e), using the tree characterization from [12] and the upper bound from [2].","tokens_in":14920,"tokens_out":16091,"duration_ms":164436,"significance":"If Theorem 1.2 is correct, it completely solves the problem left open by Chang et al. and unifies the two previously known special cases (trees and λ=-1). The classification is concrete and falsifiable: each family is described by explicit congruence conditions on distances or cycle lengths. A notable strength is that the argument is structural and uses no fitted parameters or target-inclusive assumptions; the 'if' directions are constructive and rely on the interlacing theorem and Lemma 2.2. The main weakness is that several load-bearing steps of the 'only if' direction are either delegated to [2] without a statement or omitted as 'similar', so the proof as written is not completely verifiable. These gaps appear repairable within the paper's scope, but they must be filled before the characterization can be accepted.","major_comments":[{"comment":"Lemma 3.4 is the engine of the induction in Corollary 3.5, Theorems 3.6 and 3.7, and the 'only if' direction of Theorem 1.2, but for the case where G-e is not a cycle the proof consists solely of the sentence 'by the proof of Theorem 3.2 in [2]'. The statement of [2, Theorem 3.2] is not reproduced, and the reader cannot verify that it gives the two-directional equivalence needed here for arbitrary λ and for an edge e on a cycle adjacent to a major vertex, including the case where the other endpoint of e is itself major. Please state the result from [2] and give a self-contained derivation of both directions of the equivalence.","section":"§3, Lemma 3.4"},{"comment":"In the case where G-e is a cycle, the proof shows that the left-hand side of Lemma 3.4 cannot hold, but the lemma is an 'iff' statement; the argument as written does not discharge the right-hand side. Since G-e is a cycle, p(G-e)=0, while the right-hand side requires p(G-e)=p(G)+1, which is impossible; this should be stated explicitly. As written, the proof of the equivalence is logically incomplete, even though the conclusion may be salvaged by this observation.","section":"§3, Lemma 3.4, G-e cycle branch"},{"comment":"The proof of Claim 4 (d_T(y)=1) is omitted with the comment that it is 'similar to that of Claim 3'. This claim is needed to conclude that the unique cycle of G is attached to a pendant vertex of T and to justify the count p(G-e1)=p(T) used in Claim 5. Because the omitted argument is load-bearing for the unicyclic characterization, it must be supplied rather than left as an exercise.","section":"§3, Theorem 3.6, Claim 4"},{"comment":"The exclusion of the bicyclic graph θ(k',x',l') relies on the assertion that x' is odd, which is justified only by 'by similar discussion as above'. This parity statement is essential for the final congruence |C| = |C1|-x'+|C2|-x' ≡ 2 (mod 4) that produces the contradiction. The argument establishing x' odd, together with the definitions of |C1|, |C2|, and the displayed cycle C, should be written out in full.","section":"§3, Theorem 3.7, θ(k',x',l') case"},{"comment":"In the induction step, the proof asserts that if G-e is of the form 'two cycles joined by an edge', then there is another cycle C' and an edge e' on C' adjacent to a major vertex such that G-e' is a bicyclic graph with two intersecting cycles. This existence and the 'intersecting' property are not proved, and they are the mechanism by which Theorem 3.7 is invoked to rule out the branch. The choice of e' and the verification that the resulting graph falls into the excluded intersection case should be made explicit.","section":"§3, proof of Theorem 1.2, c(G)≥3 case"}],"minor_comments":[{"comment":"There is a typo in the abstract: 'ploblem' should be 'problem'; the same typo appears in the abstract and in the introduction's description of the open problem.","section":"Abstract and Introduction"},{"comment":"In the necessity part, 'd(v, B') ≡ q−1 (mod 2q−1)' should read 'mod 2q+1', and the line 'd(v, B'') = q−1 (mod 2q+1)' is missing the congruence symbol before q−1.","section":"§3, Corollary 3.3 proof"},{"comment":"The notation appears inconsistent: if G-e is a cycle, then G is a cycle plus a chord, which in the notation of §2 is θ(k,1,l), not θ(k,2,l). Please correct the notation or explain the convention used in Figure 4.","section":"§3, Lemma 3.4 proof"},{"comment":"The sentence 'If G is not obtained from a tree T by joining C1 and C2 to two distinct vertices of T' should be 'from a tree T with L(T) λ-optimal'; otherwise every graph obtained by joining two cycles by an edge is obtained from the tree K2.","section":"§3, Theorem 3.7, Case 1"},{"comment":"In the 'If' part for c(G)≥3, the phrase 'where mL(T)=2c(T)+p(T)−1' should be 'where mL(T)(λ)=p(T)−1'; as written, c(T)=0 makes the formula correct but potentially confusing.","section":"§3, proof of Theorem 1.2, form (v)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript addresses a well-defined open problem and the main theorem is likely correct, but the current proof is not fully checkable at several points that are central to the induction. The authors should be required to make Lemma 3.4 self-contained and to supply the omitted proofs in Theorem 3.6 and Theorem 3.7. I do not see circularity or fitted parameters; the omissions appear to be presentation and completeness gaps rather than signs of a false result. The paper is within the scope of the journal and, after revision, would be a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this paper settles the open problem from Chang et al. 2024, characterizing all connected non-cycle graphs G for which m_{L(G)}(λ) = 2c(G)+p(G)-1, for arbitrary λ. That is a real result, and the five-family classification is consistent with the known tree case and the λ=-1 case.\n\nWhat is new: the arbitrary-λ case was explicitly open; previous work covered only trees and λ=-1. The proof builds naturally on the existing bound and tree classification, with an induction on the cyclomatic number. The \"if\" directions are worked out in detail, and the path-deletion/interlacing machinery is used cleanly. The paper also correctly identifies the eigenvalue restriction: λ must be 2 cos(iπ/(m+1)) with i and m+1 coprime.\n\nThe soft spots are real but not fatal. The \"only if\" direction rests on Lemma 3.4, and the proof of its non-cycle branch is not self-contained: it says \"by the proof of Theorem 3.2 in [2]\" without reproducing the statement or argument. A reader cannot verify that [2]'s result gives exactly the required iff for arbitrary λ, as opposed to only the upper bound or only λ=-1. Since the induction and the final classification depend on this lemma, this is a genuine gap in the write-up, not a cosmetic one. In addition, Claim 4 in Theorem 3.6 (d_T(y)=1) is omitted as \"similar to Claim 3\", and the parity of x' in Theorem 3.7 is disposed of with \"by similar discussion\". Both are needed to rule out configurations. I do not think the theorem is false; the omitted pieces appear to be routine analogues of arguments already presented. But the proof as printed is not fully verifiable without those details.\n\nWho is this for: spectral graph theorists working on eigenvalue multiplicity. It deserves a serious referee; I would send it to review, with the request that the authors supply the missing details or explicitly recover the needed lemma from [2]. My own verdict is conditional rather than accept, but this is a paper to engage with, not to desk-reject.","headline":"A plausible complete solution to an open characterization problem, with a couple of load-bearing proof details left to the reader or to [2].","tokens_in":15477,"tokens_out":2257,"would_cite":true,"duration_ms":23316,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"Theorem 1.2 completely classifies all connected non-cycle graphs whose line graphs attain the maximum eigenvalue multiplicity 2c(G)+p(G)−1.","keywords":["eigenvalue multiplicity","line graph","cyclomatic number","pendant vertices","extremal characterization","cosine eigenvalues","path and cycle spectrum","λ-optimal line graphs"],"falsifier":"Find a connected non-cycle graph G and an edge e lying on a cycle and adjacent to a major vertex such that L(G) is λ-optimal but L(G−e) is not λ-optimal, or such that p(G−e) ≠ p(G)+1. Such a counterexample would break the induction and hence Theorem 1.2. A direct computation of multiplicities for the θ(k′,x′,l′) bicyclic graphs already treated in the proof would test the hinge in the one case the paper handles in detail.","tokens_in":14462,"feed_emoji":"🔢","tokens_out":4829,"duration_ms":43856,"temperature":0.7,"pith_summary":"This paper solves a characterization problem left open in 2024: for a connected graph G that is not a cycle, when does an eigenvalue λ of the line graph L(G) attain the largest possible multiplicity 2c(G)+p(G)−1, where c(G) is the cyclomatic number and p(G) is the number of pendant vertices? The answer, Theorem 1.2, is a complete list of five graph families and the associated eigenvalue λ, which is always a cosine eigenvalue 2cos(iπ/(m+1)) of a path or 2cos(2kπ/(2q+1)) of a cycle. The earlier tree case and the earlier λ=−1 case become special instances of the new classification.","feed_headline":"Line-graph multiplicity maximum fully classified","feed_subtitle":"The five graph families that make an eigenvalue reach 2c(G)+p(G)−1 in a line graph are now explicit.","key_machinery":"Carrying the proof is an induction on the cyclomatic number c(G). Lemma 3.4 is the hinge: if e is an edge lying on a cycle and incident with a major vertex, then L(G) is λ-optimal if and only if L(G−e) is λ-optimal, the multiplicity drops by exactly one, and the number of pendant vertices rises by one. This lets every extremal graph be reduced by deleting cycle edges one by one to an extremal tree. Spectral lemmas on paths and cycles—their eigenvalues 2cos(iπ/(m+1)) and 2cos(2kπ/(2q+1)), the multiplicity of λ on cycles, and the invariance of multiplicity under deleting a path of length a multiple of m+1—then force the cycle orders and pendant-distance congruences appearing in the classification. Annihilator and path-deletion lemmas provide the dimension bounds used in the contradictions.","core_discovery":"The paper establishes an if-and-only-if classification: L(G) is λ-optimal exactly when λ and G have one of the five forms in Theorem 1.2. The eigenvalue λ must be 2cos(iπ/(m+1)) with gcd(i,m+1)=1; the extremal graphs are either paths with pendant vertices at distances congruent to m modulo m+1, trees with at least three pendant vertices at distances congruent to 2q modulo 2q+1, a λ-optimal tree to which one or two cycles of prescribed order are attached at distinct pendant vertices, two prescribed cycles joined by an edge, or a λ-optimal tree to which at least three cycles of order a multiple of 2q+1 are attached at distinct pendant vertices. This completes the characterization that Chang et al. described as somewhat difficult.","pith_inferences":["The same edge-deletion induction may apply to equality cases for other graph-associated matrices, such as Aα-matrices or signless Laplacians of line graphs, because the annihilator lemma used here originates in an Aα-eigenvalue setting.","The proof's reliance on the cited proof of Theorem 3.2 in Chang et al. for the non-cycle case of Lemma 3.4 means the full classification's generality depends on an argument not reproduced here; a self-contained treatment of that step would decisively settle its scope.","The arithmetic congruences in the classification suggest a number-theoretic sieve: for fixed λ, all extremal graphs have pendant distances and cycle lengths lying in one residue class, which would make computational enumeration of extremal graphs straightforward.","Although the paper states the result only for connected graphs, a componentwise analysis would likely extend the classification to disconnected graphs, since line graph spectra and the parameters c(G) and p(G) are additive over components."],"forward_implications":["The maximum multiplicity in line graphs is attained only for eigenvalues of the explicit cosine forms; no other real eigenvalue can reach the bound.","All λ-optimal line graphs decompose into a λ-optimal tree skeleton with prescribed cycles attached at distinct pendant vertices, plus the two-cycle bridge configuration; no wild extremal graphs exist.","The tree case of Yang and Wang and the λ=−1 case of Chang et al. follow as special instances of Theorem 1.2, unifying the previous results.","Checking λ-optimality of a given graph reduces to finitely many arithmetic checks: pendant distances modulo m+1 or 2q+1 and cycle orders modulo m+1, 2(m+1), or 2q+1.","If the classification is correct, the extremal line-graph multiplicity problem is closed, and subsequent work can move to other graph operators or to multiplicity bounds strictly below the maximum.","The structural description makes it possible to enumerate all λ-optimal line graphs on n vertices by enumerating λ-optimal trees and admissible cycle attachments."],"supporting_citations":[{"why":"Supplies the tree case of the characterization, restated here as Theorem 3.1 and Corollary 3.3, which forms the base of the induction.","marker":"[12]"},{"why":"Provides the upper bound for line graphs, the extremal λ=−1 case, and the proof of Theorem 3.2 invoked inside Lemma 3.4 for the reduction when G−e is not a cycle.","marker":"[2]"},{"why":"Gives the standard spectrum of paths and cycles used in Lemma 2.1 and Lemma 2.2 to determine possible eigenvalues and admissible cycle orders.","marker":"[1]"},{"why":"Supplies Lemma 2.3, the annihilator bound m_G(λ) ≤ |U|, used throughout to rule out cases via dimension contradictions.","marker":"[10]"},{"why":"Provides Lemma 2.4, the generalized dimension bound, used in the path-deletion Lemma 2.6.","marker":"[14]"},{"why":"Supplies Lemma 2.8, the bridge multiplicity lemma used to prove Lemma 2.9, the path-deletion multiplicity identity.","marker":"[6]"}],"fun_headline_variants":["Line-graph eigenvalue bound fully resolved","All extremal line graphs for eigenvalue multiplicity","Complete characterization of λ-optimal line graphs","Five families achieve line-graph multiplicity maximum"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof hinges on Lemma 3.4, the claim that deleting a carefully chosen cycle edge from an extremal line graph always leaves an extremal line graph; for the case where G−e is not a cycle, the paper refers to the proof of a theorem in Chang et al. rather than giving a fully self-contained argument, so the classification inherits that argument's validity and scope.","fun_headline_variants_meta":{"raw":{"variants":["Line-graph eigenvalue bound fully resolved","All extremal line graphs for eigenvalue multiplicity","Complete characterization of λ-optimal line graphs","Five families achieve line-graph multiplicity maximum"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000216,"raw_usage":{"total_tokens":1430,"prompt_tokens":943,"completion_tokens":487,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":559,"completion_tokens_details":{"reasoning_tokens":445}},"tokens_in":559,"tokens_out":487,"duration_ms":5477,"temperature":1.0,"reasoning_tokens":445,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:50:05.661892+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a connected non-cycle graph G and an edge e lying on a cycle and adjacent to a major vertex such that L(G) is λ-optimal but L(G−e) is not λ-optimal, or such that p(G−e) ≠ p(G)+1. Such a counterexample would break the induction and hence Theorem 1.2. A direct computation of multiplicities for the θ(k′,x′,l′) bicyclic graphs already treated in the proof would test the hinge in the one case the paper handles in detail.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the tree case of the characterization, restated here as Theorem 3.1 and Corollary 3.3, which forms the base of the induction."},{"cited_title":"Chang, J","cited_arxiv_id":null,"evidence_quote":"Provides the upper bound for line graphs, the extremal λ=−1 case, and the proof of Theorem 3.2 invoked inside Lemma 3.4 for the reduction when G−e is not a cycle."},{"cited_title":"Brouwer, W.H","cited_arxiv_id":null,"evidence_quote":"Gives the standard spectrum of paths and cycles used in Lemma 2.1 and Lemma 2.2 to determine possible eigenvalues and admissible cycle orders."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 2.3, the annihilator bound m_G(λ) ≤ |U|, used throughout to rule out cases via dimension contradictions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Lemma 2.4, the generalized dimension bound, used in the path-deletion Lemma 2.6."},{"cited_title":"Johnson, C.M","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 2.8, the bridge multiplicity lemma used to prove Lemma 2.9, the path-deletion multiplicity identity."}],"review_version":1}