REVIEW 5 major objections 5 minor 14 references
Line graphs with the largest eigenvalue multiplicity
T0 review · 5 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Theorem 1.2 completely classifies all connected non-cycle graphs whose line graphs attain the maximum eigenvalue multiplicity 2c(G)+p(G)−1.
desk verdict A plausible complete solution to an open characterization problem, with a couple of load-bearing proof details left to the reader or to [2]. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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].
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 (5)
- [§3, Lemma 3.4] 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.
- [§3, Lemma 3.4, G-e cycle branch] 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.
- [§3, Theorem 3.6, Claim 4] 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.
- [§3, Theorem 3.7, θ(k',x',l') case] 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.
- [§3, proof of Theorem 1.2, c(G)≥3 case] 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.
minor comments (5)
- [Abstract and Introduction] 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.
- [§3, Corollary 3.3 proof] 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.
- [§3, Lemma 3.4 proof] 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.
- [§3, Theorem 3.7, Case 1] 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.
- [§3, proof of Theorem 1.2, form (v)] 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.
Circularity Check
No circular derivation: the main theorem is proved from prior independent characterizations and local eigenvalue inequalities; the only delegated step is an external proof from [2].
full rationale
The derivation chain does not assume Theorem 1.2. The 'if' direction builds lambda-optimal graphs explicitly via the Interlacing Theorem and the known multiplicities of paths and cycles from Lemma 2.2, so the extremal equality is computed, not assumed. The 'only if' direction is an induction on c(G): the base cases c(G)=0,1,2 use Corollary 3.3, Theorem 3.6, and Theorem 3.7, and the induction step invokes Lemma 3.4 to reduce optimality of L(G) to optimality of L(G-e) together with p(G-e)=p(G)+1. Lemma 3.4's non-cycle case is justified by 'the proof of Theorem 3.2 in [2]', which is a reference to prior work by Chang et al., not by the present authors, and no equation of the present paper is used as its own input. The G-e-cycle case is proved in the text using Lemma 2.3 and the cycle spectrum, and it shows the right-hand side cannot hold in that situation. The paper's self-citation [14] supplies Lemma 2.4, a dimension inequality that is an external published result and does not encode the classification; it only bounds multiplicities under vertex deletion and is not equivalent to the target characterization. No fitted parameter is renamed as a prediction, and no eigenvalue condition in the theorem is used to define the graph classes in a way that would make the equality m_{L(G)}(lambda)=2c(G)+p(G)-1 hold automatically. The completeness concerns noted by the reader, such as Claim 4 being omitted and one parity discussion being 'similar', are proof-completeness risks rather than circularity, because they do not show that any conclusion is being imported from its own statement.
Assumptions & free parameters
assumptions (5)
- domain assumption Proposition 1.1: for connected G not a cycle, m_{L(G)}(lambda) <= 2c(G)+p(G)-1.
- domain assumption Theorem 3.1 from [12]: complete characterization of trees T with m_{L(T)}(lambda) = p(T)-1.
- standard math Lemma 2.4: annihilator dimension inequality from [14].
- standard math Lemma 2.8: Parter-Wiener bridge lemma from [6].
- standard math Lemma 2.1: spectra of paths and cycles from [1].
Cite this review
Pith. "Pith review of Line graphs with the largest eigenvalue multiplicity." pith.science (2026). https://pith.science/paper/W3WY4FJ4
@misc{pith2026241114835,
author = {Pith},
title = {Pith review of: Line graphs with the largest eigenvalue multiplicity},
year = {2026},
howpublished = {\url{https://pith.science/paper/W3WY4FJ4}},
note = {Machine review of arXiv:2411.14835}
}
abstract
For a connected graph $G$, we denote by $L(G)$, $m_{G}(\lambda)$, $c(G)$ and $p(G)$ the line graph of $G$, the eigenvalue multiplicity of $\lambda$ in $G$, the cyclomatic number and the number of pendant vertices in $G$, respectively. In 2023, Yang et al. \cite{WL LT} proved that $m_{L(T)}(\lambda)\leq p(T)-1$ for any tree $T$ with $p(T)\geq 3$, and characterized all trees $T$ with $m_{L(T)}(\lambda) = p(T)-1$. In 2024, Chang et al. \cite{-1 LG} proved that, if $G$ is not a cycle, then $m_{L(G)}(\lambda)\leq 2c(G)+p(G)-1$, and characterized all graphs $G$ with $m_{L(G)}(-1) = 2c(G)+p(G)-1$. The remaining ploblem is to characterize all graphs $G$ with $m_{L(G)}(\lambda)= 2c(G)+p(G)-1$ for an arbitrary eigenvalue $\lambda$ of $L(G)$. In this paper, we give this problem a complete solution.
Figures
Figures from the paper (9 more)
Reference graph
Works this paper leans on
- [2]
-
[12]
J. Yang, L. Wang, Line graphs of trees with the largest eigenvalue multiplicity, Linear Algebra Appl. 676 (2023) 56-65
work page 2023
- [1]
-
[3]
S. Chang, B.S. Tam, J. Li, Y . Zheng, Graphs G with nullity2c(G) +p(G) − 1, Discrete Appl. Math. 311 (2022) 38-58
work page 2022
-
[4]
Z. Du, Y . Huang, The multiplicity of eigenvalues of trees, Linear Algebra Appl. 654 (2022) 56-68
work page 2022
- [5]
-
[6]
C.R. Johnson, C.M. Saiago, Geometric Parter-Wiener, etc. theory, Linear Algebra Appl. 537 (2018) 332-347
work page 2018
- [7]
Show all 14 references
-
[8]
F. Tian, Y . Wang, On the multiplicity of positive eigenvalues of a graph, Linear Algebra Appl. 652 (2022) 105-124
2022
-
[9]
L. Wang, X. Fang, X. Geng, Graphs with nullity 2c(G) + p(G) − 1, Discrete Math. 345 (2022) 112786
2022
-
[10]
L. Wang, X. Fang, X. Geng, F. Tian, On the multiplicity of an arbitrary Aα-eigenvalue of a connected graph, Linear Algebra Appl. 589 (2020) 28-38
2020
-
[11]
L. Wang, L. Wei, Y . Jin, The multiplicity of an arbitrary eigenvalue of a graph in terms of cyclomatic number and number of pendant vertices, Linear Algebra Appl. 584 (2020) 257-266
2020
-
[13]
Zhang, J
Y . Zhang, J. Zhao, D. Wong, A characterization for a graph with an eigenvalue of multiplicity 2c(G) +p(G) − 1, Discrete Math. 347 (2024)
2024
-
[14]
W. Zhen, D. Wong, Y . Zhang, Eigenvalue multiplicity of graphs with given cyclomatic number and given number of quasi-pendant vertices, Discrete Appl. Math. 347 (2024) 23-29. 20
2024
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.