Extension on spectral extrema of gem-free graph with given size

Ligong Wang; Yuxiang Liu

REVIEW 3 major objections 5 minor 18 references

Extension on spectral extrema of gem-free graph with given size

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper proves that for odd $m\ge23$, the spectral radius of every gem-free graph with $m$ edges that is not the extremal graph $S_{\frac{m+3}{2},2}$ is at most $\rho(S^2_{\frac{m+5}{2},2})$, with equality only for…

desk verdict New second-extremal result for gem-free graphs, but the proof of the odd-degree case in Construction 2 rests on an unproved eigenvector inequality. read the letter →

arxiv 2411.19110 v1 pith:ZQVE47AX submitted 2024-11-28 math.CO

Yuxiang Liu , Ligong Wang This is my paper · ORCID

classification math.CO MSC 05C5005C35

keywords spectralradiusgem-freegraphfanH5Brualdi-Hoffman-TurantypeproblemsizeofextremalstabilityPerronvector

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

Among graphs with a fixed number $m$ of edges and no copy of the gem $H_5$ — the fan on a 4-vertex path plus a vertex adjacent to every path vertex — the largest spectral radius is known to belong to $S_{\frac{m+3}{2},2}$, a copy of $K_2$ joined to independent vertices. This paper determines what happens right below that maximum for odd $m\ge23$: once $S_{\frac{m+3}{2},2}$ is excluded, every remaining gem-free graph has spectral radius at most $\rho(S^2_{\frac{m+5}{2},2})$, and the bound is attained only by that graph. The runner-up $S^2_{\frac{m+5}{2},2}$ is obtained from $S_{\frac{m+1}{2},2}$ by attaching two pendant vertices to one of the two hub vertices, so the near-extremal structure is a small modification of the extremal one. The result upgrades the single extremal result to a stability statement: the only way to come close to the spectral record is to move two edges into leaves at one hub.

What carries the argument

The argument is carried by a Perron-vector edge-shift lemma (Lemma 2.1): if the Perron coordinate of $u$ is at least that of $v$, moving an edge incident to $v$ so that it becomes incident to $u$ strictly increases the spectral radius while preserving the number of edges. The proof repeatedly applies this to a hypothetical extremal graph $\hat{G}$: each time $\hat{G}$ deviates from $S^2_{\frac{m+5}{2},2}$, the lemma produces a gem-free graph with the same number of edges and larger spectral radius, contradicting maximality. To make the contradictions work, two further ingredients are needed: Lemma 3.1 classifies the neighborhood of the extremal vertex (each component is a triangle or a star), and Lemma 2.2 pins down the spectral-radius comparisons, in particular $\rho(S^2_{\frac{m+5}{2},2})>\frac{1+\sqrt{4m-7}}{2}$, which forces any counterexample to be dense enough that its neighborhood structure falls into the classified cases.

What would settle it

Enumerate all gem-free graphs on 23 edges by a backtracking generator that rejects any graph containing $H_5$, and compute their spectral radii. The theorem is false if any graph other than $S_{13,2}$ and $S^2_{14,2}$ has spectral radius greater than $\rho(S^2_{14,2})$. Equivalently, inspect the intermediate graphs $G'$, $G^{\star}$, and $G_5$ constructed in Lemma 3.4 and Claims 3.1–3.2: if any of them contains $H_5$ on five vertices, the contradiction argument identifying $S^2_{14,2}$ collapses.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2. Let $\mathcal{G}(m,H_5)$ be the family of gem-free graphs with $m$ edges and no isolated vertices. For odd $m\ge23$, if $G\in\mathcal{G}(m,H_5)$ and $G\not\cong S_{\frac{m+3}{2},2}$, then $\rho(G)\le\rho(S^2_{\frac{m+5}{2},2})$, and equality holds exactly when $G\cong S^2_{\frac{m+5}{2},2}$. The runner-up $S^2_{\frac{m+5}{2},2}$ is the graph formed from $S_{\frac{m+1}{2},2}$ (a $K_2$ hub joined to $\frac{m-3}{2}$ isolated vertices) by attaching two pendant vertices to one of the two hub vertices. In other words, once the unique maximum is excluded, the spectral radius over all gem-free graphs of odd size at least 23 is maximized by this explicit split graph with two extra leaves.

Load-bearing premise

The proof assumes that several local edge switches — reattaching a pendant vertex to another hub, or moving a whole vertex to the universal vertex — never create a copy of the gem $H_5$, and it asserts these checks without expanding them; if any one of these moves secretly produces a gem, the contradiction that forces the runner-up graph fails.

Editorial extensions

If this is right

For odd $m\ge 23$, the spectral extremal problem for gem-free graphs is now resolved up to the runner-up: the maximum is $S_{\frac{m+3}{2},2}$ and the unique second graph is $S^2_{\frac{m+5}{2},2}$.
The theorem is a stability statement: any gem-free graph of odd size at least $23$ that is not the known extremal graph has spectral radius strictly below $\rho(S^2_{\frac{m+5}{2},2})$ unless it is exactly that graph.
Together with the even-size counterpart mentioned in the introduction, the Brualdi–Hoffman–Turán problem for the gem is settled for all sufficiently large edge numbers, with explicit first and second extremal graphs.
A direct corollary of the proof is that any counterexample would have to contain at least four edges inside the neighborhood of the extremal vertex, so near-extremal graphs are heavily structured around the vertex where the Perron vector attains its maximum.

Reading between the lines

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

The Perron-vector edge-shift scheme may transfer to the other fan graphs $H_{2k+1}$ and $H_{2k+2}$, for which the extremal graph is known: the natural guess is that the runner-up is again the extremal split graph with two edges converted into pendant leaves on a dominating vertex, and the inequalities of Lemma 2.2 provide the comparison template.
The threshold $m\ge23$ comes from inequalities such as $\rho>5.1$; a computer search over gem-free graphs with $m=11,13,\ldots,21$ could show whether the runner-up theorem actually holds for smaller odd sizes, and would locate the true threshold.
The proof's repeated 'clearly H5-free' and 'it is checked' steps are the natural targets for machine verification: checking each intermediate edge-switch graph for a copy of $H_5$ would either certify the stability statement or expose a hidden gem that would force a different runner-up.

Share X Bluesky LinkedIn Reddit HN

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

The theorem is new and the paper is a legitimate extension of the Sun-Li-Wei C5/C6 approach. Zhang-Wang and Yu-Li-Peng only had the first extremal graph; this paper identifies the runner-up for odd m. The structural setup — components of N(u) are triangles or stars, e(W) is small, at most one star component — is clean and mostly checkable. The Perron-vector inequalities in Section 3 are standard.

The problem is in Lemma 3.7, Construction 2, odd-degree case. The proof asserts each term in f_{w_i} is positive because x_w < x_v ≤ x_û. For the last term, x_û z_{k_i^0} − x_{w_i} z_{v_{d_i}}, that implication does not follow. z_{k_i^0} is the coordinate of a pendant vertex adjacent only to û, while z_{v_{d_i}} is a leaf adjacent to both û and v, so z_{v_{d_i}} > z_{k_i^0}. The ratio z_{v_d}/z_{k^0} can exceed x_û/x_w; the stated inequalities do not dominate it. The paper gives no additional estimate for z_v/z_û, so the claimed positivity is not established. Since this positivity drives the contradiction W = ∅, the extremal characterization is not proven as written. It is a gap, not necessarily a false theorem — the combined sum may still be positive — but the proof as written does not show it.

Secondary issue: several H5-freeness assertions after edge moves are declared rather than shown ('Clearly', 'It is checked'). Some are routine, but because a single overlooked gem breaks the extremal contradiction, a referee would need those cases expanded.

For whom: specialists in spectral extremal graph theory. The result is plausible and fits the pattern of the C5/C6 papers; if the gap is repaired, it is a solid contribution. I would send it to review because the theorem is meaningful and the framework is sound, but the revision needs to fill the odd-degree estimate and spell out the free-ness checks. My own verdict is skeptical pending that fix.

Referee Report

3 major / 5 minor

Summary. The paper studies the Brualdi-Hoffman spectral Turan problem for gem-free (H5-free) graphs with a fixed number m of edges and no isolated vertices. Building on the known theorem that S_{(m+3)/2,2} is the unique spectral extremal graph for all H5-free graphs of odd size, the authors determine the runner-up for odd m at least 23: they claim that among H5-free graphs not isomorphic to S_{(m+3)/2,2}, the maximum spectral radius is attained uniquely by S^2_{(m+5)/2,2}. The proof fixes an extremal graph G_hat and a Perron vertex u_hat, classifies the components of G_hat[N(u_hat)] as triangles or stars, derives inequalities for e(W), and then uses a sequence of local edge moves and two graph constructions to force W = V(G_hat) \ N[u_hat] to be empty. Once W is empty, the structure of the graph is identified with S^t_{(m+t+3)/2,2}, and an eigenvalue comparison from Lemma 2.2 forces t=2.

Significance. If correct, Theorem 1.2 is a natural and sharp stability-type refinement of the gem-free spectral theorem of Zhang-Wang and Yu-Li-Peng, parallel to the C5/C6 result of Sun-Li-Wei. The paper contains no fitted parameters, the candidate extremal graphs are explicit, and the broad strategy is recognizable and plausible. However, several load-bearing steps are currently asserted rather than proved, and one algebraic positivity claim in the construction phase is not justified. These gaps concern the main contradiction that excludes W nonempty, so they are central rather than cosmetic.

major comments (3)

[Section 3, Lemma 3.7, Construction 2, odd d_i case] For odd d_i, the quantity f_{w_i} is expanded as the sum of two nonnegative-looking groups plus the term (x_hat_u z_{k_i^0} - x_{w_i} z_{v_{d_i}}), and this last term is asserted to be positive from x_{w_i}<x_v<=x_hat_u. This implication is invalid. In G'_c, k_i^0 is a pendant vertex adjacent only to u_hat, while v_{d_i} is a common leaf adjacent to both u_hat and v, so z_{v_{d_i}}=(z_u_hat+z_v)/rho > z_u_hat/rho = z_{k_i^0}. The stated inequalities allow parameter regimes, e.g. x_v close to x_hat_u and x_{w_i} close to x_hat_u with z_v close to z_u_hat, in which the last term is negative and can dominate the first two groups. Since the proof of rho(G'_c)>rho(G_c) depends on f_{w_i}>0 for every i, and this inequality is exactly what rules out W nonempty, the contradiction in Lemma 3.7 is not established.
[Section 3, Lemma 3.7, after Construction 2] The assertion that G*_c is isomorphic to S^t_{(m+t+3)/2,2} with t>=1 is not justified. If N0(u_hat)=empty and every d_i is even, the construction deletes all vertices of W and adds no pendant vertices, so G*_c is isomorphic to S_{(m+3)/2,2}, not to a graph with t>=1. Such configurations are H5-free and satisfy the standing hypotheses; for example, take u_hat and v joined to r leaves and one vertex w joined to four of those leaves, with m=2r+5 and r>=9. In this case Lemma 2.2(ii), which requires even t>=4, cannot be applied, and the final contradiction does not cover the case.
[Section 3, Lemma 3.4(ii), Claim 3.1, Claim 3.2] Several edge moves are asserted to preserve H5-freeness without proof: Lemma 3.4(ii) says 'Then G' is still H5-free', Claim 3.1 says 'Clearly, G* is H5-free', and Claim 3.2 says 'It is checked that G5 is still an H5-free graph'. These assertions are load-bearing because Lemma 2.1 can only be invoked when the moved graph remains in the admissible family G(m,H5). In particular, at the moment of Claim 3.1, e(W) is only known to be at most 1 from equation (4), and a vertex w may still have neighbors outside the triangle {z1,z2,z3}; the 'clearly' assertion needs a detailed case analysis. Please supply complete proofs of H5-freeness for these moves or replace them by operations whose H5-freeness is directly verified.

minor comments (5)

[Section 3, Construction 2, odd d_i formula] In the displayed formula for f_{w_i} when d_i is odd, the index v_{j+d_i/2} is not an integer; the intended index is likely v_{j+(d_i+1)/2} or an equivalent relabeling.
[Lemma 3.6(ii)] The inequality e(W) < e(N+(u_hat)) - |N+(u_hat)| + 2 - sum_{u in N0(u_hat)} x_u/x_u_hat is equation (4), not equation (3); the citation should be corrected.
[Introduction, reference to [6]] The text says 'Li, Zhou and Zou completely solved Conjecture 1.1', but reference [6] is attributed to 'S.C. Li, S.S. Zhao, L.T. Zou'; the author names should be harmonized.
[Abstract and Theorem 1.1] The abstract states that every gem-free graph G with m edges satisfies the bound, while the formal statement of Theorem 1.1 in the introduction requires m>=11; the abstract should include this condition.
[Abstract] The phrase 'if G in G(m,H5) \setminus S_{(m+3)/2,2} be a graph of odd size m>=23' should read 'is a graph'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof derives the odd-size gem-free spectral bound from external lemmas and eigenvector comparisons, with no fitted input or definitional equivalence.

full rationale

The claimed derivation is self-contained with respect to circularity. Theorem 1.2 is proved by taking a spectral extremal graph in the relevant H5-free family and deriving structural restrictions on its neighborhood using only the Perron-vector equations, Lemma 2.1 (Zhai-Wang), and Lemma 2.2 (Sun-Li-Wei). The target graph S^2_{(m+5)/2,2} is not defined in terms of the inequality being proved, and no parameter is fitted to the data that the theorem then predicts. The cited references [14] and [18] for the base extremal result are external prior work; although [18] shares an author with the present paper, Theorem 1.2 is an extension and its contradiction machinery does not reduce to that citation. A separate correctness risk exists, but it is not circularity: in Construction 2, for odd d_i the asserted positivity of x_hatu z_{k_i^0} - x_{w_i} z_{v_{d_i}} is not justified by the equality z_{k_i^j} = z_{v_l}, which the paper explicitly states only for j >= 1. This could invalidate the proof of W = empty, but it does not make the derivation circular. Overall, no step equates the theorem's conclusion with an input by construction, so the circularity score is 0.

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

The proof introduces no fitted constants or new entities. Its main imported input is Lemma 2.2 from [13], and its main unstated proof obligation is the preservation of H5-freeness under local edge moves.

assumptions (4)

standard math Perron-Frobenius theorem: a connected graph has a positive Perron vector for its spectral radius, and adding edges increases the spectral radius.
Used throughout Section 3 to write equations for rho^2 x_u and to compare spectral radii of edge-modified graphs.
domain assumption Lemma 2.1 from Zhai-Wang [17]: moving edges toward a vertex with larger Perron coordinate strictly increases the spectral radius.
Imported from prior literature and used in Lemma 2.3, Lemma 3.4(ii), Claim 3.1, and Claim 3.2 for every edge-switch contradiction.
domain assumption Lemma 2.2 from Sun-Li-Wei [13]: for m at least 22, rho(S^2_{(m+5)/2,2}) exceeds (1+sqrt(4m-7))/2 and exceeds rho(S^t_{(m+t+3)/2,2}) for even t at least 4.
Imported from prior literature; supplies the lower bound against which the extremal graph is compared and the final comparison among S^t graphs.
ad hoc to paper The edge-switch operations described in Lemma 3.4(ii), Claim 3.1, and Claim 3.2 preserve H5-freeness whenever the stated conditions on e(W) hold.
Asserted without a full case analysis at several points, including 'Then G' is still H5-free with size m', 'Clearly, G* is H5-free', and 'It is checked that G5 is still an H5-free graph'. If any of these switches creates a gem, the proof fails.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Extension on spectral extrema of gem-free graph with given size." pith.science (2026). https://pith.science/paper/ZQVE47AX

@misc{pith2026241119110,
  author       = {Pith},
  title        = {Pith review of: Extension on spectral extrema of gem-free graph with given size},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZQVE47AX}},
  note         = {Machine review of arXiv:2411.19110}
}

abstract

A graph $G$ is $F$-free if $G$ does not contain $F$ as a subgraph. Let $\mathcal{G}(m, F)$ denote the family of $F$-free graphs with $m$ edges and without isolated vertices. Let $S_{n,k}$ denote the graph obtained by joining every vertex of $K_{k}$ to $n-k$ isolated vertices and $S_{n,k}^{t}$ denote the graph obtained from $S_{n-t,k}$ by attaching $t$ pendant vertices to the maximal degree vertex of $S_{n-t,k}$, respectively. Denote by $H_{n}$ the fan graph obtain from $n-1$-vertex path plus a vertex adjacent to each vertex of the path. Particularly, the graph $H_{5}$ is also known as the gem. Zhang and Wang [Discrete Math. 347(2024)114171] and Yu, Li and Peng [arXiv: 2404. 03423] showed that every gem-free graph $G$ with $m$ edges satisfies $\rho(G)\leq \rho(S_{\frac{m+3}{2},2})$. In this paper, we show that if $G\in \mathcal{G}(m, H_{5})\setminus S_{\frac{m+3}{2},2}$ be a graph of odd size $m\geq23$, then $\rho(G)\leq \rho(S_{\frac{m+5}{2},2}^{2})$, and equality holds if and only if $G\cong S_{\frac{m+5}{2},2}^{2}$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 15 canonical work pages

[1]

Bondy, U.S.R

J.A. Bondy, U.S.R. Murty, Graph Theory, in: Graduate Tex ts in Mathematics, Vol. 244, Springer, New York, 2008

work page 2008
[2]

Brualdi, A.J

R.A. Brualdi, A.J. Hoﬀman, On the spectral radius of (0 , 1) matrices, Linear Algebra Appl. 65 (1985) 133–146

1985
[3]

Brualdi-Hoffman-Tur\'{a}n problem of the gem

F. Chen, X.Y. Yuan, Brualdi–Hoﬀman–Tur´an problem of the gem, arXiv: 2411.08345v1

work page Pith review arXiv
[4]

Chen, X.-D Zhang, Some new results and problems in sp ectral extremal graph theory, J

M.Z. Chen, X.-D Zhang, Some new results and problems in sp ectral extremal graph theory, J. Anhui Univ. Nat. Sci. 42 (2018) 12–25 (in Chinese) . 9

work page 2018
[5]

F¨ uredi, M

Z. F¨ uredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, Erd˝ os centennial, Bolyai Soc. Math. Stud. 25 (2013) 169–26 4

work page 2013
[6]

S. C. Li, S. S. Zhao, L. T. Zou, Spectral extrema of graphs w ith ﬁxed size: forbidden fan graph, friendship graph or theta graph, arXiv: 2409. 15918

work page
[7]

Y.T. Li, W.J. Liu, L.H. Feng, A survey on spectral conditi ons for some extremal graph problems, Adv. Math. (China) 51 (2022) 193–258

work page 2022
[8]

H.Q. Lin, B. Ning, B.Y.D.R. Wu, Eigenvalues and triangle s in graphs, Comb. Probab. Comput. 30 (2) (2021) 258–270

work page 2021

Show all 18 references

[9]

Nikiforov, Walks and the spectral radius of graphs, Li near Algebra Appl

V. Nikiforov, Walks and the spectral radius of graphs, Li near Algebra Appl. 418 (2006) 257–268

2006
[10]

Nikiforov, The spectral radius of graphs without pat hs and cycles of speciﬁed length, Linear Algebra Appl

V. Nikiforov, The spectral radius of graphs without pat hs and cycles of speciﬁed length, Linear Algebra Appl. 432 (2010) 2243–2256

2010
[11]

Nikiforov, Some new results in extremal graph theory

V. Nikiforov, Some new results in extremal graph theory . Lond. Math. Soc. Lect. Note Ser. 392 (2011) 141–181

2011
[12]

Nosal, Eigenvalues of Graphs, Master’s Thesis, Univ ersity of Calgary, 1970

E. Nosal, Eigenvalues of Graphs, Master’s Thesis, Univ ersity of Calgary, 1970

1970
[13]

Sun, S.C

W.T. Sun, S.C. Li, W. Wei, Extensions on spectral extrem a of C5/C 6-free graphs with given size, Discrete Math. 346 (2023) 113591

2023
[14]

L. J. Yu, Y. T. Li, Y. J. Peng, Spectral extremal graphs fo r fan graphs, arXiv: 2404.03423

arXiv
[15]

Zhai, H.Q

M.Q. Zhai, H.Q. Lin, J.L. Shu, Spectral extrema of graph s with ﬁxed size: Cycles and complete bipartite graphs, European J. Combin. 95 (2021) 10 3322

2021
[16]

Zhai, J.L

M.Q. Zhai, J.L. Shu, A spectral version of Mantel’s theo rem, Discrete Math. 345 (2022) 112630

2022
[17]

M.Q. Zhai, B. Wang, Proof of a conjecture on the spectral radius of C4-free graphs, Linear Algebra Appl. 437 (2012) 1641–1647

2012
[18]

Zhang, L.G

Y.T. Zhang, L.G. Wang, On the spectral radius of graphs w ithout a gem, Discrete Math. 347 (2024) 114171. 10

2024

Pith tools

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

[1] [1]

Bondy, U.S.R

J.A. Bondy, U.S.R. Murty, Graph Theory, in: Graduate Tex ts in Mathematics, Vol. 244, Springer, New York, 2008

work page 2008

[2] [2]

Brualdi, A.J

R.A. Brualdi, A.J. Hoﬀman, On the spectral radius of (0 , 1) matrices, Linear Algebra Appl. 65 (1985) 133–146

1985

[3] [3]

Brualdi-Hoffman-Tur\'{a}n problem of the gem

F. Chen, X.Y. Yuan, Brualdi–Hoﬀman–Tur´an problem of the gem, arXiv: 2411.08345v1

work page Pith review arXiv

[4] [4]

Chen, X.-D Zhang, Some new results and problems in sp ectral extremal graph theory, J

M.Z. Chen, X.-D Zhang, Some new results and problems in sp ectral extremal graph theory, J. Anhui Univ. Nat. Sci. 42 (2018) 12–25 (in Chinese) . 9

work page 2018

[5] [5]

F¨ uredi, M

Z. F¨ uredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, Erd˝ os centennial, Bolyai Soc. Math. Stud. 25 (2013) 169–26 4

work page 2013

[6] [6]

S. C. Li, S. S. Zhao, L. T. Zou, Spectral extrema of graphs w ith ﬁxed size: forbidden fan graph, friendship graph or theta graph, arXiv: 2409. 15918

work page

[7] [7]

Y.T. Li, W.J. Liu, L.H. Feng, A survey on spectral conditi ons for some extremal graph problems, Adv. Math. (China) 51 (2022) 193–258

work page 2022

[8] [8]

H.Q. Lin, B. Ning, B.Y.D.R. Wu, Eigenvalues and triangle s in graphs, Comb. Probab. Comput. 30 (2) (2021) 258–270

work page 2021