REVIEW 3 major objections 4 minor 27 references
Longest odd cycles in non-bipartite $C_{2k+1}$-free graphs
T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read This paper proves an exact edge-count threshold: every n-vertex C_{2k+1}-free graph with at least floor((n-r+1)^2/4)+C(r,2) edges has no odd cycle longer than r.
desk verdict Theorem 1.6 is a genuinely new result, but the proof has a factor-2 error in Lemma 2.1 that breaks the main argument as written. 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
The (s,r+2)-starter: a set of r+2 vertices in which every pair is joined by an odd path of length 2j-1 for some j in {s,...,k}; Lemma 2.2 shows such a set forces a C_{2k+1}. This is combined with Lemma 2.1, which guarantees that among any r+2 vertices two share at least n/(2(r+2)(r+1)) common neighbors, and with Lemmas 3.1-3.3, which bound the number of chords and off-cycle attachment vertices of a shortest r-admissible odd cycle. The extremal example T*(r,n) is the graph formed by a K_r and a balanced complete bipartite graph intersecting in exactly one vertex.
What would settle it
For k=2, r=4, and n=25, an exhaustive computer search over C5-free graphs with at least floor(22^2/4)+6 = 127 edges would settle Theorem 1.6 at the first nontrivial instance: a graph containing a 7-cycle would refute it, and none should exist. To probe the gap in Theorem 1.9, search whether any such graph has more than 4 vertices in the union of its odd blocks; if so, the unproved bound |G1| <= r is false.
Extended reading notes
Core claim
The central claim is Theorem 1.6: for k >= 2, 3 <= r <= 2k, and n >= 2(r+2)(r+1)(r+2k), every n-vertex C_{2k+1}-free graph with e(G) >= floor((n-r+1)^2/4)+C(r,2) has no odd cycle longer than r. The proof proceeds by contradiction from a shortest odd cycle C of length 2m+1 > r. The key step is the (s,r+2)-starter: a set of r+2 vertices in which every pair is joined by an odd path of length between 2s-1 and 2k-1; if such a set exists, the graph must contain a C_{2k+1}. The edge density supplies the needed common neighborhoods, and structural lemmas show that a shortest r-admissible cycle either has many chords, forcing a starter, or few chords and few external vertices, forcing an edge-count c
Load-bearing premise
The proof of Theorem 1.9 assumes without proof that the union of all odd blocks of the graph has at most r vertices; the stability conclusion for vertex and edge deletion relies on this bound.
Editorial extensions
If this is right
- Any C_{2k+1}-free graph meeting the edge bound has odd circumference at most r.
- The bound floor((n-r+1)^2/4)+C(r,2) is best possible for each allowed r, with T*(r,n) as the extremal construction.
- The stability theorem of [23] - d2(G) <= r-2 and gamma2(G) <= C(floor(r/2),2)+C(ceil(r/2),2) with equality iff G = T*(r,n) - follows as a corollary, and the proof is simpler than the original.
- The edge-density result extends earlier weak-pancyclicity and odd-cycle thresholds of [5], [3], [8], and [18].
- For r = 2k, the theorem says a dense C_{2k+1}-free graph has all odd cycles of length at most 2k, matching the boundary of the extremal result for C_{2k+1}.
Reading between the lines
- The n-dependence in the theorem is likely not optimal: the note added in proof records a follow-up reaching a linear bound n >= 100k for the stability corollary, suggesting the polynomial 2(r+2)(r+1)(r+2k) is an artifact of the proof technique.
- The (s,r+2)-starter mechanism may be portable to other forbidden subgraphs, giving exact edge thresholds for odd circumference in graphs avoiding other fixed odd cycles.
- The unproved assertion |G1| <= r in the proof of Theorem 1.9 is the point to attack: if it fails, the stability conclusion might still hold but would need a different argument, for instance via block trees.
- A hierarchy of extremal graphs is suggested by the conjecture in Section 6: when r = 2k + b, the extremal structure should become a balanced bipartite graph glued to a K_{2k} and a K_b along cut vertices, refining the single T*(r,n) picture.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies C_{2k+1}-free graphs with many edges. Theorem 1.6 claims that for n ≥ 2(r+2)(r+1)(r+2k), every n-vertex C_{2k+1}-free graph with e(G) ≥ floor((n-r+1)^2/4)+binom(r,2) contains no odd cycle of length greater than r, unless it already contains C_{2k+1}. The extremal example is the graph T*(r,n) consisting of a complete bipartite graph and a K_r sharing one vertex. Theorem 1.9 then derives a stability result, bounding the vertex-deletion distance d2(G) and edge-deletion distance γ2(G) to bipartiteness. The proof strategy uses a Haggkvist-style starter lemma (Lemma 2.2), a deletion procedure (Lemma 5.1), and several structural lemmas about shortest r-admissible odd cycles (Lemmas 3.1–3.3).
Significance. If correct, Theorem 1.6 would provide an exact edge-threshold result that extends Haggkvist's minimum-degree theorem and several earlier edge-number results (Brandt, Bollobas-Thomason, Lin-Ning-Wu/Caccetta-Jia). The extremal construction T*(r,n) is natural and the conjectured stability structure is plausible. The paper is clearly organized and the local arguments in Section 3 (chords, related/crossing chords, auxiliary graphs) are often elegant. However, the proof contains load-bearing gaps that, as written, leave the central claims unproved.
major comments (3)
- [Section 2, Lemma 2.1] The displayed bound in Lemma 2.1 contains a factor-2 arithmetic error. The sum is over unordered pairs {u,v} subset S; each term is 2|N(u)∩N(v)|. Under the supposition |N(u)∩N(v)| < n/(2(r+2)(r+1)), the first term is at most 2 * C(r+2,2) * n/(2(r+2)(r+1)) = n/2, not n/4. With this correction the displayed inequality gives e(G) < (n-r+1)^2/4 + 3r/2 + 3/4, and the -n/4 term that made the contradiction work disappears. For r=3 and r=4 this upper bound is still above the assumed threshold (e.g., for r=3 it is the threshold plus 9/4), so the claimed contradiction does not follow. Since Lemma 2.1 underpins Lemma 2.2 and both main cases of Theorem 1.6, the proof of Theorem 1.6 is incomplete as written. The charging inequality itself also needs a proof: edges inside S are not obviously covered by common-neighbor pairs.
- [Section 5, after Claim 8] The assertion 'Since |G1| ≤ r ≤ 2k' is unproved and is false in general. Let H be obtained from K_{2,t} (parts {x,y} and {b_1,...,b_t}) by adding the edge xy. For t ≥ 3, H is 2-connected, non-bipartite, and every odd cycle is a triangle; hence H is an odd block with t+2 vertices while r=3. Thus the union of all odd blocks of a graph with no odd cycle longer than r need not have at most r vertices. The edge-density hypothesis of Theorem 1.9 might rule out such examples, but no argument is given. This bound is load-bearing for the conclusions γ2(G)≤... and d2(G)≤r-2, so the proof of Theorem 1.9 is incomplete.
- [Sections 2 and 5, Lemma 2.4] Lemma 2.4 is imported from [23], the same paper whose main theorem (Theorem 1.8) Theorem 1.9 claims to reprove. This lemma is used not only in the proof of Theorem 1.9 but also in Lemma 3.3 and Case 2.1 of Theorem 1.6. The paper presents Theorem 1.9 as 'a simple proof' of Theorem 1.8, but as written the proof is conditional on a result from that very paper. The authors should either prove Lemma 2.4 here or explicitly state that the new proof depends on a lemma from the paper being reproved; otherwise the independence of the proof is overstated.
minor comments (4)
- [Abstract / Introduction] The phrase 'Let n,k,r be two positive integers' should read 'three positive integers'. Also, 'vertcies' is a typo in Section 1.
- [Proof of Theorem 1.9, after Claim 8] The sentence 'γ2(G) ≤ γ2(G1) ≤ ... or r−2 ≤ d2(G) ≤ d2(G1) ≤ r−2' uses 'or' where a conjunction (e.g., 'and') appears to be intended.
- [Claim 8 proof] The 'well-known exercise' that a graph with minimum degree at least 2(r−2)−1 has a cycle of length at least 2(r−2) should be stated or cited explicitly, for completeness.
- [Theorem 1.6 statement] The statement 'contains a C2k+1 or contains no odd cycle of length greater than r' would be clearer as 'either contains a C2k+1 or contains no odd cycle of length greater than r'.
Circularity Check
Main theorem independent; 'simple proof' of Theorem 1.8 imports a lemma from the original source.
-
self citation load bearing
[Section 2, Lemma 2.4; used in Section 4 Case 2.1 and Section 3 Lemma 3.3; application in Section 5 Theorem 1.9]
"Lemma 2.4 ([23]). Let G be a C_{2k+1}-free graph with k ≥ 2, and let C be an odd cycle of length 2ℓ + 1 in G with l ≥ k + 1. Then deg(x, C) ≤ ℓ for every x ∈ V (G) \ V (C)."
This lemma is cited from [23], the authors' own SIAM J. Discrete Math paper that already proved Theorem 1.8, which the present paper claims to 'provide a simple proof of' (Section 1). It is used inside the proof of Theorem 1.6 (e.g., 'By Lemma 2.4, each vertex in U has at most (|C|-1)/2 neighbors on C' in Case 2.1), and Theorem 1.6 is then invoked to derive Theorem 1.9. Thus the 'simple proof' of Theorem 1.8 depends on a substantive lemma from the very paper that originally proved Theorem 1.8. This is a load-bearing self-citation but not a formal equivalence: the central threshold argument of Theorem 1.6 remains independent.
full rationale
The main proof of Theorem 1.6 is a self-contained extremal argument built on external results (Füredi–Gunderson Theorem 1.7, Brandt–Faudree–Goddard Lemma 2.3, and Häggkvist's starter notion). No fitted parameter is renamed as prediction, and no theorem is used to prove itself. The only self-citation of note is Lemma 2.4, cited from the authors' own [23]; it is used in Case 2.1 and Lemma 3.3 to bound the number of neighbors a vertex can have on a long odd cycle. Because [23] contains the very stability theorem (Theorem 1.8) that the paper purports to reprove simply, the proof of Theorem 1.9 inherits a lemma from the original source. That is a legitimate citation, but it weakens the independence of the 'simple proof' claim; it is not a logical circle around Theorem 1.6. Separately, the assertion 'Since |G1| ≤ r ≤ 2k' in the proof of Theorem 1.9 is unproved and appears false in general (e.g., two triangles sharing a cut vertex have |G1|=5>r=3); this is a correctness gap, not a circularity, and I flag it per the reviewing rule but do not count it toward the circularity score. The factor-2 issue in Lemma 2.1 raised by the skeptic is likewise a mathematical-error concern, not a circularity, and the present score does not penalize it.
Assumptions & free parameters
assumptions (5)
- standard math Theorem 1.7: ex(n,C_{2k+1}) = floor(n^2/4) for n >= 4k-2
- standard math Lemma 2.3: non-bipartite graph with minimum degree >= (n+2)/3 is weakly pancyclic with girth 3 or 4
- domain assumption Lemma 2.4 from [23]: deg(x,C) <= l for x outside an odd (2l+1)-cycle in a C_{2k+1}-free graph with l >= k+1
- standard math A graph with minimum degree delta contains a cycle of length at least delta+1
- ad hoc to paper In a 2-connected non-bipartite graph with no odd cycle longer than r, the union of odd blocks has at most r vertices
Cite this review
Pith. "Pith review of Longest odd cycles in non-bipartite $C_{2k+1}$-free graphs." pith.science (2026). https://pith.science/paper/LPPJEPZX
@misc{pith2026250816199,
author = {Pith},
title = {Pith review of: Longest odd cycles in non-bipartite $C_2k+1$-free graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/LPPJEPZX}},
note = {Machine review of arXiv:2508.16199}
}
abstract
In strengthening a result of Andr\'asfai, Erd\H{o}s and S\'os in 1974, H\"{a}ggkvist proved that if $G$ is an $n$-vertex $C_{2k+1}$-free graph with minimum degree $\delta(G)>\frac{2n}{2k+3}$ and $n>\binom{k+2}{2}(2k+3)(3k+2)$, then $G$ contains no odd cycle of length greater than $\frac{k+1}{2}$. This result has many applications.In this paper, we consider a similar problem by replacing minimum degree condition with edge number condition. We prove that for integers $n,k,r$ with $k\geq 2,3\leq r\leq 2k$ and $n \geq 2\left(r+2\right)\left(r+1\right)\left(r+2k\right)$, if $G$ is an $n$-vertex $C_{2k+1}$-free graph with $e(G) \geq \left\lfloor\frac{(n-r+1)^2}{4}\right\rfloor+\binom{r}{2}$, then $G$ contains no odd cycle of length greater than $r$. The construction shows that the result is best possible. This extends a result of Brandt [Discrete Applied Mathematics 79 (1997)], and a result of Bollob\'as and Thomason [Journal of Combinatorial Theory, Series B. 77 (1999)], and a result of Caccetta and Jia [Graphs Combin. 18 (2002)] and independently proving by Lin, Ning and Wu [Combin. Probab. Comput. 30 (2021)]. Recently, Ren, Wang, Yang, and the second author [SIAM J. Discrete Math. 38 (2024)] show that for $3\leq r\leq 2k$ and $n\geq 318(r-2)^2k$, every $n$-vertex $C_{2k+1}$-free graph with $e(G) \geq \left\lfloor\frac{(n-r+1)^2}{4}\right\rfloor+\binom{r}{2}$ can be made bipartite by deleting at most $r-2$ vertices or deleting at most $\binom{\lfloor\frac{r}{2}\rfloor}{2}+\binom{\lceil\frac{r}{2}\rceil}{2}$ edges. As an application, we derive this result and provide a simple proof.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[23]
S. Ren, J. Wang, S. Wang and W. Yang, A stability result for C2k+1-free graphs, SIAM J. Discrete Math. 38 (2024), no. 2, 1733–1756
work page 2024
-
[1]
B. Andr´ asfai, P. Erd˝ os and V. T. S´ os, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Mathematics. 8 (1974), 205– 218
work page 1974
- [2]
-
[3]
B. Bollob´ as and A. Thomason, Weakly pancyclic graphs, Journal of Combinatorial Theory, Series B 77 (1999), 121–137
work page 1999
-
[4]
J. A. Bondy, Pancyclic graphs, J. Combin. Theory Ser. B 11 (1971), 80–84
work page 1971
-
[5]
Brandt, A sufficient condition for all short cycles, Discrete Applied Mathematics 79 (1997), 63–66
S. Brandt, A sufficient condition for all short cycles, Discrete Applied Mathematics 79 (1997), 63–66
work page 1997
- [6]
-
[7]
A. E. Brouwer, Some lotto numbers from an extension of Tur´ an’s theorem, Math. Centr. report ZW152, Amsterdam (1981), 6pp
work page 1981
Show all 27 references
-
[8]
Caccetta and R
L. Caccetta and R. Z. Jia, Edge maximal non-bipartite graphs without odd cycles of prescribed lengths, Graphs Combin. 18 (1) (2002), 75–92
2002
-
[9]
G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Sot. 2 (1952), 69–81
1952
-
[10]
P. Erd˝ os, Some recent results on extremal problems in graph theory (Results), In: Theory of Graphs (International Symposium Rome, 1966), Gordon and Breach, New York, Dunod, Paris 1966, pp. 117–123
1966
-
[11]
Erd˝ os, On some new inequalities concerning extremal properties of graphs, In: Theory of Graphs (Proceedings of the Colloquium, Tihany, 1966), Academic Press, New York 1968, pp
P. Erd˝ os, On some new inequalities concerning extremal properties of graphs, In: Theory of Graphs (Proceedings of the Colloquium, Tihany, 1966), Academic Press, New York 1968, pp. 77–81. 22
1966
-
[12]
F¨ uredi, A proof of the stability of extremal graphs, Simonovits’ stability from Szemer´ edi’s regularity, J
Z. F¨ uredi, A proof of the stability of extremal graphs, Simonovits’ stability from Szemer´ edi’s regularity, J. Combin. Theory Ser. B 115 (2015), 66–71
2015
-
[13]
F¨ uredi and D
Z. F¨ uredi and D. S. Gunderson, Extremal numbers for odd cycles, Combin. Probab. Comput. 24 (2015), 641–645
2015
-
[14]
Gy˝ ori, V
E. Gy˝ ori, V. Nikiforov and R. H. Schelp, Nearly bipartite graphs, Discrete Mathe- matics 272 (2003), 187–196
2003
-
[15]
H¨ aggkvist, Odd cycles of specified length in non-bipartite graphs, North-Holland Mathematics Studies
R. H¨ aggkvist, Odd cycles of specified length in non-bipartite graphs, North-Holland Mathematics Studies. 62 (1982), 89–99
1982
-
[16]
H¨ aggkvist, R
R. H¨ aggkvist, R. J. Faudree, R. H. Schelp, Pancyclic graphs–connected Ramsey num- ber, Ars Combin. 11 (1981), 37–49
1981
-
[17]
Kor´ andi, A
D. Kor´ andi, A. Roberts and A. Scott, Exact Stability for Tur´ an’s Theorem, Advances in Combinatorics 9 (2021), 17 pp
2021
-
[18]
H. Lin, B. Ning and B. Wu, Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2021), 258–270
2021
-
[19]
Mantel, Problem 28, In Wiskundige Opgaven 10 (1907), 60–61
W. Mantel, Problem 28, In Wiskundige Opgaven 10 (1907), 60–61
1907
-
[20]
Nikiforov and R
V. Nikiforov and R. H. Schelp, Cycles and paths in graphs with large minimal degree, Journal of Graph Theory 47 (2004), 39–52
2004
-
[21]
Nikiforov and R
V. Nikiforov and R. H. Schelp, Cycle lengths in graphs with large minimum degree, Journal of Graph Theory 52 (2004), 157–170
2004
-
[22]
Roberts and A
A. Roberts and A. Scott, Stability results for graphs with a critical edge, European J. Combin. 94 (2018), 27–38
2018
-
[24]
Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, Proc
M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, Proc. Colloq., Tihany, 1966, Academic Press, New York (1968), pp. 279–319
1966
-
[25]
Tur´ an, Eine Extremalaufgabe aus der Graphentheorie, Mat
P. Tur´ an, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–452. 23
1941
-
[26]
Yan and Y
Z. Yan and Y. Peng, A strong structural stability of C2k+1-free graphs, arXiv preprint arXiv:2408.15487 (2024)
2024 arXiv
-
[27]
L. Zou, Y. Li and Y. Peng, Strong spectral stabilities for C2k+1-free graphs, arXiv preprint arXiv:2508.13643 (2025). 24
2025 arXiv
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.