{"id":"1b9c94c2-57a8-43f1-89e2-249b9be508b4","arxiv_id":"2508.16199","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"If an n-vertex C_{2k+1}-free graph has at least floor((n-r+1)^2/4) + C(r,2) edges, then every odd cycle in it has length at most r, and the bound is sharp.","lead":"This paper proves an exact edge-count threshold for graphs that avoid a fixed odd cycle: once they have enough edges, all odd cycles they contain must be short. The result unifies several known stability theorems and gives a simpler proof of a recent stability result.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Factor-2 error in Lemma 2.1's common-neighborhood bound invalidates the main proof","rationale":"The reader's conditional verdict was based on the unproved assertion |G1|≤r in Theorem 1.9. I agree that assertion is under-justified, but I found a more central issue in the proof of the main theorem. Lemma 2.1 is foundational: it is invoked in Lemma 2.2 to guarantee large common neighborhoods, and then again in Case 1 and Case 2.2 of Theorem 1.6. The factor-of-2 error in bounding the pair-sum means the proof of Lemma 2.1 is invalid as written, and the subsequent contradiction does not follow. This is a correctness risk in the central claim, not merely a missing citation or a gap in the stability application. I am not claiming the theorem is false; rather, the manuscript needs a corrected proof of Lemma 2.1 (or a different argument) before the main result can be considered established. The reader's CONDITIONAL verdict is therefore appropriate, but for a different and more load-bearing reason.","tokens_in":22017,"tokens_out":51424,"duration_ms":534301,"concrete_test":"Recompute the sum in Lemma 2.1: for |S|=r+2, if every pair satisfies |N(u)∩N(v)| < M with M = n/(2(r+2)(r+1)), then Σ_{u<v} 2|N(u)∩N(v)| < 2·C(r+2,2)·M = n/2, not n/4. Then redo the final algebra for r=3: e(G) ≤ (n-5)^2/4 + 3n/2, which exceeds floor((n-2)^2/4)+3 for large n, so the proof's contradiction disappears. If the corrected calculation is confirmed, Lemma 2.1 needs a genuinely different proof before Theorem 1.6 can be accepted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 2.1 is used in Lemma 2.2 and repeatedly in Theorem 1.6 to produce a pair with |N(u)∩N(v)| ≥ r+2k. Its proof bounds the term Σ_{u,v∈S} 2|N(u)∩N(v)| by C(r+2,2)·n/(2(r+2)(r+1)) = n/4, using |N(u)∩N(v)| < n/(2(r+2)(r+1)) for every pair. But there are C(r+2,2) unordered pairs and each term is 2|N|, so the correct bound is 2·C(r+2,2)·n/(2(r+2)(r+1)) = n/2, not n/4. (If the sum is over ordered pairs, the bound is even larger.) With the corrected n/2, the final estimate becomes e(G) < (n-r+1)^2/4 + 3r/2 + 3/4 + n/4, which is not below the assumed threshold for large n. For example, for r=3 the bound is about (n-5)^2/4 + 3n/2 = n^2/4 - n + 6.25, while the threshold is floor((n-2)^2/4)+3 ≈ n^2/4 - n + 4, so the claimed contradiction does not follow. The lemma may be true, but the supplied proof does not establish it; since Lemma 2.1 underpins the starter argument and both main cases, the central theorem is not proved as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":22419,"tokens_out":23126,"duration_ms":223820,"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":[{"comment":"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":"Section 2, Lemma 2.1"},{"comment":"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.","section":"Section 5, after Claim 8"},{"comment":"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.","section":"Sections 2 and 5, Lemma 2.4"}],"minor_comments":[{"comment":"The phrase 'Let n,k,r be two positive integers' should read 'three positive integers'. Also, 'vertcies' is a typo in Section 1.","section":"Abstract / Introduction"},{"comment":"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.","section":"Proof of Theorem 1.9, after Claim 8"},{"comment":"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.","section":"Claim 8 proof"},{"comment":"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'.","section":"Theorem 1.6 statement"}],"recommendation":"reject","confidential_remarks":"The manuscript is in scope for math.CO, but the two gaps identified in the main theorems are not merely stylistic. The factor-2 error in Lemma 2.1 changes the final estimate in a way that the proof's contradiction no longer follows for r=3,4; and the bound |G1|≤r in Theorem 1.9 is unproved and false without the edge-density hypothesis. These are load-bearing, and the necessary repairs appear to require new ideas rather than local corrections. I cannot recommend publication in the present form. A resubmission with a correct proof of Lemma 2.1 and a proof of the |G1| bound (or a revised stability argument) could be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper proves a new edge-threshold for long odd cycles in C_{2k+1}-free graphs, and the construction showing sharpness is correct. But the proof of the key Lemma 2.1 has an arithmetic error that invalidates the main theorem as written. The reader's report missed it, so I'm flagging it directly.\n\nLemma 2.1 claims that for any S of size r+2, some pair has at least n/(2(r+2)(r+1)) common neighbors. The proof bounds e(S)+e(S,V\\S) by the sum over pairs in S of 2|N(u)∩N(v)| plus a term for vertices with exactly one neighbor in S. The inequality itself is fine; the problem is the bound on that sum. With |N(u)∩N(v)| < n/(2(r+2)(r+1)) for every unordered pair, the sum of 2|N(u)∩N(v)| is at most 2 * C(r+2,2) * that bound, which is n/2, not n/4 as they write. (If the sum is over ordered pairs, it's even bigger.) Plugging n/2 into the rest of the argument gives e(G) < (n-r+1)^2/4 + (3r)/2 + 3/4, which does not contradict the assumed threshold. So the contradiction at the end of Lemma 2.1 does not follow.\n\nThis matters because Lemma 2.1 is used in Lemma 2.2 and in both cases of Theorem 1.6. The theorem may still be true—I suspect the lemma can be rescued with a different constant and a slightly larger n—but the proof as written is not valid.\n\nWhat's good: Theorem 1.6 is a real new statement, unifying Brandt, Bollobas-Thomason, and Caccetta-Jia/Lin-Ning-Wu. The starter method is a substantive extension of Haggkvist's argument. The structure lemmas (3.1–3.3) are elaborate and seem plausible, though the long case analysis is hard to check quickly.\n\nOther soft spots: Theorem 1.9 asserts |G1| ≤ r without proof; that's a gap in the stability application. Also, Lemma 2.4 is taken from the authors' own [23], which is the theorem being reproved, so the 'simple proof' of Theorem 1.8 is only as independent as that lemma.\n\nBottom line: worth refereeing, but the referee must focus on whether Lemma 2.1 can be fixed. If it can, this is a solid paper. As is, the central theorem is unproved.","headline":"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.","tokens_in":22904,"tokens_out":12650,"would_cite":false,"duration_ms":117751,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["odd cycles","C_{2k+1}-free graphs","edge extremal threshold","stability","(s,r+2)-starter","non-bipartite graphs","circumference"],"falsifier":"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.","tokens_in":21907,"feed_emoji":"⭕","tokens_out":9564,"duration_ms":93460,"temperature":0.7,"pith_summary":"This paper establishes an exact edge-count threshold for the absence of long odd cycles in graphs that forbid an odd cycle of length 2k+1. It proves that whenever an n-vertex C_{2k+1}-free graph has at least floor((n-r+1)^2/4)+C(r,2) edges, the graph contains no odd cycle of length greater than r, under the conditions k >= 2, 3 <= r <= 2k, and n large enough. The threshold is best possible: the extremal construction is a balanced complete bipartite graph sharing one vertex with a clique K_r. As a corollary, the paper recovers a recent stability theorem with a shorter proof: such dense graphs can be made bipartite by deleting at most r-2 vertices, or by deleting a small number of edges, and equality holds only for the extremal graph.","feed_headline":"Edge threshold forces short odd cycles in C2k+1-free graphs","feed_subtitle":"Exact bound floor((n-r+1)^2/4)+C(r,2) also yields a simple proof of the stability extremal graph.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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}."],"supporting_citations":[{"why":"Introduces the (s,r+2)-starter concept and the minimum-degree theorem that this paper adapts to edge counts.","marker":"[15]"},{"why":"Gives the exact extremal number ex(n,C_{2k+1}) = floor(n^2/4), used to bound subgraphs after deleting cycles or vertex sets.","marker":"[13]"},{"why":"Supplies weak pancyclicity under minimum degree, used to force a C_{2k+1} in the bipartiteness argument of Lemma 3.3.","marker":"[6]"},{"why":"Supplies Lemma 2.4 (degree bound to an odd cycle) and states the stability theorem re-proved here as Theorem 1.9.","marker":"[23]"},{"why":"Provides the earlier edge-density condition guaranteeing all short cycles, which Theorem 1.6 extends.","marker":"[5]"},{"why":"Gives the weakly pancyclic result for near-extremal non-bipartite graphs that the new edge threshold generalizes.","marker":"[3]"},{"why":"Gives a prior edge-count result forcing an odd cycle of length at most 2k+1, a special case of the new theorem.","marker":"[8]"},{"why":"Provides an independent proof of the same prior result and is part of the lineage being generalized.","marker":"[18]"}],"fun_headline_variants":["Edge threshold forces short odd cycles in C2k+1-free graphs","Exact edge bound caps odd cycle length in C2k+1-free graphs","Edge count determines max odd cycle in C2k+1-free graphs","New edge-number condition limits odd cycles in C2k+1-free graphs","Edge density alone controls odd cycle length in C2k+1-free graphs"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Edge threshold forces short odd cycles in C2k+1-free graphs","Exact edge bound caps odd cycle length in C2k+1-free graphs","Edge count determines max odd cycle in C2k+1-free graphs","New edge-number condition limits odd cycles in C2k+1-free graphs","Edge density alone controls odd cycle length in C2k+1-free graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000299,"raw_usage":{"total_tokens":1749,"prompt_tokens":1108,"completion_tokens":641,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":852,"completion_tokens_details":{"reasoning_tokens":555}},"tokens_in":852,"tokens_out":641,"duration_ms":7543,"temperature":1.0,"reasoning_tokens":555,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T17:29:20.860310+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"H¨ aggkvist, Odd cycles of specified length in non-bipartite graphs, North-Holland Mathematics Studies","cited_arxiv_id":null,"evidence_quote":"Introduces the (s,r+2)-starter concept and the minimum-degree theorem that this paper adapts to edge counts."},{"cited_title":"F¨ uredi and D","cited_arxiv_id":null,"evidence_quote":"Gives the exact extremal number ex(n,C_{2k+1}) = floor(n^2/4), used to bound subgraphs after deleting cycles or vertex sets."},{"cited_title":"Brandt, R","cited_arxiv_id":null,"evidence_quote":"Supplies weak pancyclicity under minimum degree, used to force a C_{2k+1} in the bipartiteness argument of Lemma 3.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 2.4 (degree bound to an odd cycle) and states the stability theorem re-proved here as Theorem 1.9."},{"cited_title":"Brandt, A sufficient condition for all short cycles, Discrete Applied Mathematics 79 (1997), 63–66","cited_arxiv_id":null,"evidence_quote":"Provides the earlier edge-density condition guaranteeing all short cycles, which Theorem 1.6 extends."},{"cited_title":"Bollob´ as and A","cited_arxiv_id":null,"evidence_quote":"Gives the weakly pancyclic result for near-extremal non-bipartite graphs that the new edge threshold generalizes."},{"cited_title":"Caccetta and R","cited_arxiv_id":null,"evidence_quote":"Gives a prior edge-count result forcing an odd cycle of length at most 2k+1, a special case of the new theorem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides an independent proof of the same prior result and is part of the lineage being generalized."}],"review_version":1}