Two problems on booksize and triangular edges in Nosal graphs

Jing Zeng; Lihua You; Xiaoxue Zhang; Xinghui Zhao

Two problems on booksize and triangular edges in Nosal graphs

T0 review · 0 major / 6 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read For m-edge graphs with no isolated vertices, spectral radius ≥ √m forces a book of size ρ/3 and ρ triangular edges.

desk verdict Settles two open problems on Nosal graphs with optimal constants; proofs check out, with a few terse spots that need polishing. read the letter →

arxiv 2607.15071 v2 pith:CW5LVPLZ submitted 2026-07-16 math.CO

Xinghui Zhao , Lihua You , Jing Zeng , Xiaoxue Zhang This is my paper · ORCID

classification math.CO MSC 05C3505C50

keywords booksizetriangularedgesspectralradiusNosalgraphextremaltheorysupersaturationPerronvectorbooks

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

This paper proves that any m-edge graph with no isolated vertices whose spectral radius ρ is at least √m, and which is not complete bipartite, must contain a book of size at least ρ/3 and at least ρ edges that lie in triangles. The result answers a question about the optimal constant for book size in Nosal graphs (graphs with ρ(G) > √m) and confirms a conjecture about triangular edges. It implies that every Nosal graph has a book of size greater than √m/3 and more than √m triangular edges. The proof is a spectral double-counting argument that uses the Perron vector to turn the global condition ρ ≥ √m into local triangle counts.

What carries the argument

The proof centers on the Perron vector x of G: after normalizing its largest entry to 1 and picking a vertex u* where it is attained, it expresses ρ² - m as a sum of excess contributions from edges inside N(u*) minus deficit terms f(w) for outside vertices. A local count shows that any 'good' edge uv forces at least R(d_U(u), d_U(v), c_uv) triangular edges, and the tight case is analyzed through the subgraph H of triangular edges and the matrix M = ρI - A(H) with a nonnegative inverse obtained by the Neumann series. The final step is a vector comparison showing that if τ(G) < ρ, the deficit strictly exceeds the excess, contradicting ρ ≥ √m.

What would settle it

Construct an m-edge graph with no isolated vertices, ρ ≥ √m, and not complete bipartite, with bk(G) < ρ/3 or τ(G) < ρ. More specifically, for Theorem 1.11, search for a graph where equality holds in the local count of Lemma 4.3 but some outside vertex's neighborhood in V* contains a triangular edge of H; such a graph would refute Claim 1 and invalidate the vector comparison.

Watch

Extended reading notes

Core claim

The central discovery is a pair of sharp bounds: for every m-edge graph G with no isolated vertices, ρ(G) ≥ √m, and G not complete bipartite, the maximum book size (the largest number of triangles sharing a common edge) satisfies bk(G) ≥ ρ(G)/3, and the number of triangular edges satisfies τ(G) ≥ ρ(G). Because ρ(G) ≥ √m, these are exactly the optimal constants 1/3 and 1 in the conjectured lower bounds for Nosal graphs (ρ(G) > √m). The paper also constructs examples showing that neither constant can be improved.

Load-bearing premise

The proof of Theorem 1.11 rests on Claim 1, which asserts that when equality holds in the local triangular-edge count, the triangular-edge subgraph is induced and every outside vertex sees an independent set inside it; if that structural rigidity misses an equality case, the vector comparison that produces the contradiction loses its foundation.

Editorial extensions

If this is right

Every Nosal graph has a book of size greater than √m/3 and more than √m triangular edges.
The constants 1/3 and 1 are best possible: the paper's examples show no larger factor can hold uniformly.
The stronger bounds are stated in terms of ρ(G) rather than √m, so the result is a genuine spectral supersaturation theorem, not just a corollary of the √m threshold.
For t ≥ 4, the same supersaturation phenomenon extends to edges contained in K_t, with a linear lower bound (Theorem 5.4).

Reading between the lines

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

The localization method around a Perron-maximal vertex could be adapted to find optimal constants for generalized books B_{s,k}, since the same excess-vs-deficit structure may appear there.
The structurally rigid tight case (Claim 1) suggests a general principle: in spectral supersaturation, equality in local counts forces strong induced-structure constraints; probing this rigidity may unify other tight cases.
A direct test would be to check whether the assumption 'no isolated vertices' can be relaxed: the theorems likely hold for the non-isolated core of a graph, with isolated vertices appended without effect.

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

This is a clean, genuinely new result. It answers Problem 1.6 of Li–Liu–Zhang and confirms Conjecture 1.3 of Li–Feng–Peng, improving the book-size constant from 1/4 to the optimal 1/3 and proving τ(G) ≥ ρ(G). The proof strategy extends the Perron-vector weighting of Zhai, Li and Lou—not revolutionary, but the execution is solid. Theorem 1.10's double-counting argument is short and correct: Lemma 3.1's identity checks, Lemma 3.3's lower bound is fine, and the final inequality gives bk ≥ ρ/3. Theorem 1.11 is more intricate. The localization identity (5) is exactly right, and Lemma 4.3's edge counting gives the right R. The proof branches into two cases. Case 1 is a straightforward regularity argument. Case 2 is the heart: under τ(G) < ρ, derive a contradiction. The vector comparison in Claim 2 is sound, and the Neumann series step is legitimate because ρ(H) < ρ. I checked the equality case in Subcase 2.2: the proof of Claim 1 is terse, but the stress-test's reconstruction works—once equality holds in Lemma 4.3, the classification of V* follows, and the neighborhood independence is direct. The only real blemish is notation: the definition of p_z has a typo (missing overline) and some subscripts render ambiguously. That's a referee fix, not a substantive flaw.

One minor thing: Lemma 3.2's proof that K_3(G) is nonempty is a bit quick; it hinges on z_e = 0 for every edge implying complete bipartite. It's correct, but a reader might want one more sentence. Also, the abstract's promise of 'no isolated vertices' is important—the complete bipartite exception needs it—and the authors handle the disconnected case properly.

Bottom line: the results are real, the constants are optimal (the examples in Section 5 confirm this), and the proofs are internally consistent. This deserves a serious referee. I'd accept it after a round of polishing.

Referee Report

0 major / 6 minor

Summary. The paper studies m-edge graphs G with no isolated vertices, spectral radius ρ(G) ≥ √m, and G not isomorphic to a complete bipartite graph. Theorem 1.10 proves bk(G) ≥ ρ(G)/3, and Theorem 1.11 proves τ(G) ≥ ρ(G). These imply, for Nosal graphs, bk(G) > √m/3 and τ(G) > √m, resolving Problem 1.6 of Li–Liu–Zhang and Conjecture 1.3 of Li–Feng–Peng. The proofs use Perron-vector weighting, double counting over triangles (Section 3), and a localization around a maximum eigenvector entry with a tight-case structural analysis and a vector comparison argument (Section 4).

Significance. The paper settles two open problems in spectral extremal graph theory and gives essentially optimal constants up to o(√m) slack. The bounds are stated in the stronger form involving ρ(G) rather than only √m, and this stronger form is essential to the proofs. The derivations are self-contained and direct: they use only Perron–Frobenius, standard eigenvalue identities, and careful counting, with no fitted parameters and no circularity. The tight-case analysis in Theorem 1.11, especially Claim 1, is delicate but valid after filling in the compressed details. The optimality examples in Section 5 are also useful, modulo a minor numerical typo noted below.

minor comments (6)

[§5, Further work] The displayed equality τ(H) = 2t+1 = √e(H) + t is false for all t ≥ 1. Indeed e(H)=4t^2+3t+1 gives √e(H) = 2t + 3/4 + O(1/t), so τ(H) = √e(H) + 1/4 + o(1). The asymptotic optimality of the constant 1 still follows from τ(H)/√m → 1, but the stated equality should be corrected.
[§4, Subcase 2.2, definition of p_z] There are missing overlines in the definition of p_z and in several equations of Claim 2. The intended definition is p_{v,z} = d_{V_z}(v) + 1/2 d_{\overline{V_z}}(v) for v ∈ \overline{V_z}; with the printed notation the identity j^T p_z = ρ|V_z| + e(H) does not hold. Please correct the notation throughout Claim 2.
[§4, Claim 1] The proof of Claim 1 is very compressed. In particular, the identification of V* and the explicit description of E(H) are asserted with "Clearly"; the equality analysis in (8) that rules out additional triangular edges (e.g., edges within N_U(y') or within N_W(y)∩N_W(y')) should be spelled out. The claim is valid, but this is a delicate structural step that needs a fuller justification for the reader.
[§4, Case 1] The step "Thus x_v = 1/2 for any v ∈ U_1" is terse. It should be explained: if some x_v > 1/2, then a B-neighbor u of v would have β_u ≥ x_v > 1/2, forcing u ∈ U_1 \ U_2 and contradicting U_2 = U_1. The argument is sound but not immediate.
[§4, after Claim 2] The renormalization of the Perron vector from max=1 to sum=1 should be flagged explicitly. Earlier sets B, U_1, U_2 were defined using the max=1 normalization; the final argument uses a different scaling. Since the graph-theoretic objects V*, V_z, p_z do not depend on this scaling, the proof is valid, but the transition should be clarified to avoid confusion.
[§3, Lemma 3.2] The sentence "Then G is a complete bipartite graph by the definition of z_e" is terse. A brief justification (fix an edge uv, partition V into N(u) and N(v), and use z_e=0 to force all cross edges) would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: main theorems are derived directly from Perron-vector eigenvalue equations and standard external results.

full rationale

Theorems 1.10 and 1.11 are proved by weighted double counting over triangles and the Perron eigenvector. The only invoked results are standard facts (Perron–Frobenius, the spectral bound ρ(H)≤√(2e(H)), and Kruskal–Katona), none of which assumes the conclusions. In Theorem 1.10, the proof uses bk(G)≥|C_e| and derives (ρ−3bk(G))Σt_e≤0 with Σt_e>0, so the conclusion bk(G)≥ρ(G)/3 is forced by the inequalities rather than assumed. In Theorem 1.11, the delicate Claim 1 is derived from equality in the local triangular-edge counting inequality, not from the target statement; the later vector comparison is a contradiction argument based on ρ(H)<ρ, which follows from τ(G)<ρ and the standard spectral bound. No fitted parameters are renamed as predictions, no uniqueness theorem is imported from the authors' prior work, and no load-bearing self-citation appears. The derivation chain is self-contained apart from standard, externally checkable lemmas.

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

The paper introduces auxiliary sets (U, W, U1, U2, V*) and auxiliary vectors p_z, but these are proof constructs, not new postulated entities. No free parameters are fitted; the bounds are functions of the spectral radius itself.

assumptions (3)

standard math Perron–Frobenius theorem: an irreducible non-negative symmetric matrix has a positive eigenvector for its spectral radius.
Used in Lemma 2.1 to obtain a positive Perron vector x in both proofs.
standard math Spectral radius bound ρ(H) ≤ √(2e(H)) for any graph H.
Used in Section 4 to conclude ρ(H) < ρ from τ(G) < ρ.
standard math Kruskal–Katona theorem
Used only in Section 5 for the generalized K_t result, not for the central theorems.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Two problems on booksize and triangular edges in Nosal graphs." pith.science (2026). https://pith.science/paper/CW5LVPLZ

@misc{pith2026260715071,
  author       = {Pith},
  title        = {Pith review of: Two problems on booksize and triangular edges in Nosal graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CW5LVPLZ}},
  note         = {Machine review of arXiv:2607.15071}
}

abstract

A graph $G$ with $m$ edges is said to be a Nosal graph if $\rho(G)>\sqrt{m}$. For a graph $G$, we write $bk(G)$ for its maximum book size and $\tau(G)$ for the number of edges contained in triangles. Li, Liu and Zhang [J. Combin. Theory Ser. B 179 (2026) 219--249] proved that every $m$-edge Nosal graph satisfies $bk(G)> \frac{1}{24}\sqrt{m}$ and $\tau(G) > \frac{1}{12}\sqrt{m}$. Recently, two results on the booksize constant are proved: $\frac{1}{9}$ by Zhai, Li and Lou [arXiv:2601.10163v2], and $\frac{1}{4}$ by Chen, Li and Tang [arXiv:2607.16746v1]. In this paper, we establish the following result: Every $m$-edge graph $G$ with no isolated vertices and $\rho(G)\geq \sqrt{m}$ that is not isomorphic to any complete bipartite graph satisfies $bk(G)\geq\frac{\rho(G)}{3}$ and $\tau(G)\geq \rho(G)$. As direct consequences, we answer a question of Li, Liu and Zhang [J. Combin. Theory Ser. B 179 (2026) 219--249] and confirm a conjecture of Li, Feng and Peng [J. Graph Theory 110 (4) (2025) 408--425].

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

On a spectral booksize problem fo non bipartite graphs
math.CO 2026-08 accept novelty 7.0 of 10

Every sufficiently large m-edge non-bipartite graph without isolated vertices satisfying rho(G)^2 >= m-1+2/(rho(G)-1) is either an exceptional graph S+_{m,s} or contains a book of size at least (1/4-o(1)) sqrt(m), and...

Reference graph

Works this paper leans on

32 extracted references · 2 linked inside Pith · cited by 1 Pith paper

[1]

Babai, B

L. Babai, B. Guiduli, Spectral extrema for graphs: the Zarankiewicz problem, Elec- tron. J. Comb. 16 (2009), #R123

2009
[2]

Bollob´ as, Extremal Graph Theory, Academic Press, 1978

B. Bollob´ as, Extremal Graph Theory, Academic Press, 1978. 16

1978
[3]

Bollob´ as, V

B. Bollob´ as, V. Nikiforov, Cliques and the spectral radius, J. Comb. Theory, Ser. B 97 (5) (2007) 859–865

2007
[4]

H. Chen, Y. Li, Q. Tang, Supersaturation in Nosal graphs: Triangles and books, arXiv:2607.16746v1, 2026

arXiv 2026
[5]

Cioab˘ a, D

S. Cioab˘ a, D. Desai, M. Tait, A spectral Erd˝ os–S´ os theorem, SIAM J. Discrete Math. 37 (3) (2023) 2228–2239

2023
[6]

Cioab˘ a, D

S. Cioab˘ a, D. Desai, M. Tait, The spectral even cycle problem, Comb. Theory 4 (1) (2024) 10

2024
[7]

Cioab˘ a, L

S. Cioab˘ a, L. Feng, M. Tait, X.-D. Zhang, The maximum spectral radius of graphs without friendship subgraphs, Electron. J. Comb. 27 (2020), #P4.22

2020
[8]

Cvetkovi´ c, P

D. Cvetkovi´ c, P. Rowlinson, S. K. Simi´ c, An Introduction to the Theory of Graph Spectra, Cambridge Univ. Press, Cambridge, 2010

2010

Show all 32 references

[9]

L. Fang, H. Lin, J. Shu, Z. Zhang, Spectral extremal results on trees, Electron. J. Comb. 31 (2) (2024) P2.34

2024
[10]

J. He, J. Ma, T. Yang, Some extremal results on 4-cycles, J. Comb. Theory, Ser. B 149 (2021) 92–108

2021
[11]

B. Li, B. Ning, Eigenvalues and cycles of consecutive lengths, J. Graph Theory 103 (3) (2023) 486–492

2023
[12]

X. Li, M. Zhai, J. Shu, A Brualdi–Hoffman–Tur´ an problem on cycles, Eur. J. Comb. 120 (2024) 103966

2024
[13]

Y. Li, L. Feng, Y. Peng, A spectral Erd˝ os-Faudree-Rousseau theorem, J. Graph Theory 110 (4) (2025) 408–425

2025
[14]

Y. Li, H. Liu, S. Zhang, More on Nosal’s spectral theorem: Books and 4-cycles, J. Comb. Theory, Ser. B 179 (2026) 219–249

2026
[15]

Y. Li, W. Liu, L. Feng, A survey on spectral conditions for some extremal graph problems, Adv. Math. (China) 51 (2) (2022) 193–258

2022
[16]

Y. Li, Y. Peng, The maximum spectral radius of non-bipartite graphs forbidding short odd cycles, Electron. J. Comb. 29 (4) (2022), #P4.2

2022
[17]

H. Lin, B. Ning, B. Wu, Eigenvalues and triangles in graphs, Comb. Probab. Comput. 30 (2) (2021) 258–270. 17

2021
[18]

H. Liu, O. Pikhurko, K. Staden, The exact minimum number of triangles in graphs of given order and size, Forum Math. Pi 8 (2020) e8

2020
[19]

Lov´ asz, M

L. Lov´ asz, M. Simonovits, On the number of complete subgraphs of a graph, in: Proc. of Fifth British Comb. Conf., Aberdeen, 1975, pp. 431–442

1975
[20]

Lov´ asz, M

L. Lov´ asz, M. Simonovits, On the number of complete subgraphs of a graph II, in: Studies in Pure Math., Birkh¨ auser, 1983, pp. 459–495

1983
[21]

Mubayi, Counting substructures I: color critical graphs, Adv

D. Mubayi, Counting substructures I: color critical graphs, Adv. Math. 225 (2010) 2731–2740

2010
[22]

Nikiforov, Some inequalities for the largest eigenvalue of a graph, Comb

V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Comb. Probab. Comput. 11 (2) (2002) 179–189

2002
[23]

Nikiforov, A contribution to the Zarankiewicz problem, Linear Algebra Appl

V. Nikiforov, A contribution to the Zarankiewicz problem, Linear Algebra Appl. 432 (2010) 1405–1411

2010
[24]

Nikiforov, On a theorem of Nosal, arXiv:2104.12171, 2021

V. Nikiforov, On a theorem of Nosal, arXiv:2104.12171, 2021

2021 arXiv
[25]

B. Ning, M. Zhai, Counting substructures and eigenvalues I: triangles, Eur. J. Comb. 110 (2023) 103685

2023
[26]

Nosal, Eigenvalues of graphs, Master’s thesis, University of Calgary, 1970

E. Nosal, Eigenvalues of graphs, Master’s thesis, University of Calgary, 1970

1970
[27]

Pikhurko, Z.B

O. Pikhurko, Z.B. Yilma, Supersaturation problem for color-critical graphs, J. Comb. Theory, Ser. B 123 (2017) 148–185

2017
[28]

M. Zhai, R. Li, Z. Lou, Advances on two spectral conjectures regarding booksize of graphs, arXiv:2601.10163v2, 2026

2026
[29]

M. Zhai, H. Lin, J. Shu, Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs, Eur. J. Comb. 95 (2021) 103322

2021
[30]

M. Zhai, R. Liu, J. Xue, A unique characterization of spectral extrema for friendship graphs, Electron. J. Comb. 29 (2022), #P3.32

2022
[31]

Zhang, On the first two eigenvalues of regular graphs, Linear Algebra Appl

S. Zhang, On the first two eigenvalues of regular graphs, Linear Algebra Appl. 686 (2024) 102–110

2024
[32]

Zhang, The spectral radius, maximum average degree and cycles of consecutive lengths of graphs, Graphs Comb

W. Zhang, The spectral radius, maximum average degree and cycles of consecutive lengths of graphs, Graphs Comb. 40 (2) (2024) 32. 18

2024

Pith tools

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

[1] [1]

Babai, B

L. Babai, B. Guiduli, Spectral extrema for graphs: the Zarankiewicz problem, Elec- tron. J. Comb. 16 (2009), #R123

2009

[2] [2]

Bollob´ as, Extremal Graph Theory, Academic Press, 1978

B. Bollob´ as, Extremal Graph Theory, Academic Press, 1978. 16

1978

[3] [3]

Bollob´ as, V

B. Bollob´ as, V. Nikiforov, Cliques and the spectral radius, J. Comb. Theory, Ser. B 97 (5) (2007) 859–865

2007

[4] [4]

H. Chen, Y. Li, Q. Tang, Supersaturation in Nosal graphs: Triangles and books, arXiv:2607.16746v1, 2026

arXiv 2026

[5] [5]

Cioab˘ a, D

S. Cioab˘ a, D. Desai, M. Tait, A spectral Erd˝ os–S´ os theorem, SIAM J. Discrete Math. 37 (3) (2023) 2228–2239

2023

[6] [6]

Cioab˘ a, D

S. Cioab˘ a, D. Desai, M. Tait, The spectral even cycle problem, Comb. Theory 4 (1) (2024) 10

2024

[7] [7]

Cioab˘ a, L

S. Cioab˘ a, L. Feng, M. Tait, X.-D. Zhang, The maximum spectral radius of graphs without friendship subgraphs, Electron. J. Comb. 27 (2020), #P4.22

2020

[8] [8]

Cvetkovi´ c, P

D. Cvetkovi´ c, P. Rowlinson, S. K. Simi´ c, An Introduction to the Theory of Graph Spectra, Cambridge Univ. Press, Cambridge, 2010

2010