Pith. sign in

REVIEW 1 major objections 3 minor 21 references

Cycle lengths in graphs of given minimum degree

T0 review · 1 major / 3 minor · reviewed 2026-08-03 · 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 a sharp extremal theorem: any graph on n≥2k−3 vertices with more than (k−1)(n−k+1) edges contains a cycle whose length is a multiple of k, and for odd k this bound is exact.

desk verdict Strong stability and extremal results for mod-k cycles, but a load-bearing finite check in the k=4,5 case is asserted rather than proved. read the letter →

arxiv 2511.03085 v2 pith:PL44IKJK submitted 2025-11-05 math.CO

Yandong Bai , Andrzej Grzesik , Binlong Li , Magdalena Prorok This is my paper · ORCID
classification math.CO MSC 05C3505C38
keywords cyclelengthsadmissiblecyclesminimumdegreeextremalnumbermodulokTurán2-connectedgraphsstability
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 establishes a sharp extremal result for cycle lengths modulo k: if a graph on n vertices has more than (k−1)(n−k+1) edges, and n is at least 2k−3, then some cycle has length divisible by k. For odd k this bound is exact, giving the first determination of the extremal number for cycles of length 0 mod k beyond the previously known case k=3. The proof goes through a stability analysis of earlier theorems on cycle lengths in graphs of given minimum degree: under minimum degree k, 2-connectivity already forces k admissible cycles and cycles in every even residue class mod k, with only two exceptional graphs. A parallel result for even k lowers the minimum degree to k−1 when only even residue classes are asked for. The extremal theorem then follows by a short induction that first improves the degree and connectivity, then applies the modulo-cycle theorem.

What carries the argument

The engine is a pair of lemmas (2.3 and 2.4) that turn the absence of the desired cycle structure into a connectivity guarantee: a 2-connected graph with minimum degree at least k−r that lacks k admissible cycles (or lacks cycles in some even residue class mod k) must be at least (k+2)/2−r connected. With high connectivity in hand, the proof combines the paper's path-concatenation lemmas (2.5 and 2.6) — which glue arithmetic progressions of path lengths across a separator into long progressions of cycle lengths — with known admissible-path theorems. For the hard minimum-degree cases k=4,5, the argument passes through a structural analysis of 5-cycles and the 'hypo-Petersen' family, small gra

What would settle it

Enumerate the finite family of proper hypo-Petersen graphs in Figure 3 and compute their cycle-length sets; if one misses any length from 5 to 9, the proof's Claim 2.3 contradiction disappears. A second, direct check: search for an n-vertex graph with n≥2k−3 and e(G)>(k−1)(n−k+1) that has no 0-mod-k cycle for k=4 or 5.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Theorem 1.10: for every integer k≥3 and every graph G on n≥2k−3 vertices, e(G)>(k−1)(n−k+1) forces a cycle of length 0 mod k. As a corollary, for odd k the extremal number is exactly ex(n,C_{0 mod k})=(k−1)(n−k+1) when n≥2k−3, the lower bound coming from the complete bipartite graph K_{k−1,n−k+1}, which avoids 0-mod-k cycles. This is the first time this extremal number is known for a general family of odd moduli; previous exact values covered only k=3 (and k=2,4 separately). The main structural step is a stability strengthening: 2-connected graphs of minimum degree at least k contain k admissible cycles and cycles of every even length modulo

Load-bearing premise

The argument that minimum degree 4 or 5 already forces admissible cycles depends on an unproved finite check: every proper hypo-Petersen graph (all drawn in Figure 3) contains cycles of consecutive lengths 5 through 9; if any such graph lacks one of those lengths, Theorem 1.3 fails for k=4 or 5, and Theorem 1.10, which reduces to Theorem 1.4, fails with it.

Editorial extensions

If this is right

  • For every odd k and every n≥2k−3, the exact maximum number of edges in a graph with no cycle of length divisible by k is (k−1)(n−k+1); the complete bipartite graph K_{k−1,n−k+1} shows the bound cannot be lowered.
  • The constant c_{0,k} in the linear-edge problem for 0-mod-k cycles equals k−1 for every odd k; before this, exact constants were known only for k≤4.
  • Theorems 1.3 and 1.4 upgrade earlier minimum-degree conditions from k+1 to k for 2-connected graphs, with only two specified exceptions, so results relying on those earlier theorems now work at one lower degree.
  • For even k≥4, a 2-connected graph of minimum degree k−1 on at least k+2 vertices already contains cycles of every even length modulo k.
  • 2-connected non-bipartite graphs of minimum degree at least k contain cycles of every residue class modulo k, apart from K_{k+1} and, for k=3, the Petersen graph.

Reading between the lines

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

  • Beyond the paper: if Theorem 1.10 is correct, the still-open even-k case of the 0-mod-k extremal constant will need different extremal graphs — the bipartite K_{k−1,n−k+1} that is extremal for odd k contains a 0-mod-k cycle when k is even, and the known k=4 value is already smaller than k−1.
  • Beyond the paper: the proof's k=4,5 case currently rests on a visual check of the finite hypo-Petersen family; a short computer enumeration of those graphs' cycle lengths would turn that step into a verified finite fact and remove the only non-textual dependency in the chain leading to Theorem 1.10.
  • Beyond the paper: a natural next question is whether exact formulas for other residue classes, such as cycles of length ℓ mod k with even ℓ, hold at the same thresholds; the present arguments provide a template but do not settle the general case.
  • Beyond the paper: the threshold n≥2k−3 in Theorem 1.10 stitches together two regimes — for smaller n the extremal problem is the known odd-cycle Turán problem — and a unified formula may be provable by the same induction.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper proves stability versions of theorems of Gao–Huo–Liu–Ma on cycle lengths in graphs of given minimum degree. For a 2-connected graph with minimum degree at least k≥4, it shows (Theorem 1.3) that the graph contains k admissible cycles unless it is K_{k+1} or K_{k,n-k}; (Theorem 1.4) that it contains cycles of all even lengths modulo k under the same exceptions; and (Theorem 1.7) a non-bipartite version covering all residues, with the Petersen graph as the only extra exception for k=3. It also proves Theorem 1.6 for even k with minimum degree k−1. The main extremal application is Theorem 1.10: every n-vertex graph with more than (k−1)(n−k+1) edges contains a (0 mod k)-cycle, for k≥3 and n≥2k−3. This yields the corollary ex(n,C_{0 mod k})=(k−1)(n−k+1) for every odd k, matching the lower bound given by K_{k−1,n−k+1}. The proofs are built from established theorems on admissible paths and cycles, a connectivity lemma, and a detailed induction, with a substantial case analysis for the exceptional small cases k=4,5.

Significance. If the proof is correct, the paper resolves the extremal number for (0 mod k)-cycles for all odd k, a problem with a long history going back to Burr and Erdős. Theorem 1.10 is the first general determination of this extremal number beyond small k. The paper is well structured, gives explicit extremal constructions, and uses a mix of classical results (Woodall, Bondy, Gao–Huo–Liu–Ma, etc.) and original arguments. It also transparently acknowledges the overlap of Lemma 5.4 with a recent result of Lin–Wang–Zhou. The main caveat is that one finite, load-bearing assertion in Lemma 3.11 is left unproved, with only a figure reference. This is a gap that needs to be closed before the central claims can be fully accepted, but it appears to be fixable within the scope of the manuscript.

major comments (1)
  1. [Section 3, Lemma 3.11 (after Figure 3)] The assertion 'every proper hypo-Petersen graph contains cycles of consecutive lengths from 5 to 9, see Figure 4' is load-bearing but is not proved. It is used to finish the contradiction in Lemma 3.11 after H=G[{x_i,y_i,z_i}] is shown to be a proper hypo-Petersen graph, and this underpins Theorem 1.3 for k∈{4,5}. Since Theorem 1.4 is deduced from Theorem 1.3, the k=5 case of Theorem 1.10 also depends on it. Claim 2.3 only rules out the Petersen graph; it does not establish any cycle-length property of the other graphs in Figure 3. The reference to Figure 4 is not a proof, and Figure 4 appears to depict a single representative rather than all proper hypo-Petersen graphs. Please provide a complete, machine-checkable verification—for instance an explicit cycle list for each graph in Figure 3—or cite a published result that establishes this cycle spectrum.
minor comments (3)
  1. [Lemma 3.1] The statement 'One can check that the assertion holds for r≤3' is another finite check. Although it is much smaller than the hypo-Petersen check, please expand it or give the explicit resulting path lists, since this lemma is used in the proof of Lemma 3.4.
  2. [Introduction, after Corollary 1.11] The formula for ex(n,C_{2 mod k}) is stated without proof, with the comment that it follows 'by the same arguments' and can also be obtained from [13]. Since this result is not used in the paper, please provide a proof sketch or a precise reference to make the statement self-contained.
  3. [Figures 3 and 4] Please include adjacency lists or a compact description of the hypo-Petersen graphs in Figure 3, so that the finite claims about them are reproducible without relying solely on drawings.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation chain uses independent external theorems and internal proofs; the flagged issues are unproved finite checks and a k=3 citation mismatch, not input-output equivalences.

full rationale

The paper's main derivation chain is not circular. Theorem 1.10 is proved by induction on n; Claims 1 and 2 reduce to a 2-connected graph with minimum degree at least k, and the terminal step applies Theorem 1.4, which was proved earlier in Section 4 from Theorem 1.3 and from external results. Theorem 1.3 is proved via Theorem 3.2, Lemma 3.5, Lemma 3.11, and Theorems 3.6/3.7, all of which are either proved in the paper or cited to published external work ([6], [12], [13], [14], [16]). The only author-overlapping citation that is load-bearing is [14] (Gao, Li, Ma, Xie), used for Theorem 3.9 and Lemma 4.2/5.1; that is a published, externally checkable theorem whose assumptions do not include the present target results, so under the review rules it is real evidence and does not raise the circularity score. The paper even remarks that Lemma 5.4 can be deduced from the independent result of Lin, Wang, and Zhou [16]. No fitted parameters are renamed as predictions, and no definition is equivalent to a conclusion. Two non-circular gaps exist and should be flagged separately: (1) in Lemma 3.11 the assertion 'every proper hypo-Petersen graph contains cycles of consecutive lengths from 5 to 9, see Figure 4' is a load-bearing finite verification supported only by a figure, which is a completeness/correctness gap but not circularity because the cycle-length property is neither assumed in the definition of hypo-Petersen graphs nor derived from the theorem being proved; (2) the proof of Theorem 1.10 invokes Theorem 1.4 for k=3 even though Theorem 1.4 is stated only for k≥4, again a correctness gap rather than a circular reduction. Neither of these makes the derivation equivalent to its inputs.

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

The paper relies on several published theorems for admissible paths, triangle cases, and extremal graph theory. No new physical or mathematical entities are introduced. The only non-standard axiom is the finite but unproved assertion about proper hypo-Petersen graphs, which is a gap in the k=4,5 case of Theorem 1.3.

assumptions (9)
  • standard math Theorem 2.1 (Gao-Huo-Liu-Ma): if G+xy is 2-connected and all vertices except x,y have degree ≥k+1, then G contains k admissible (x,y)-paths.
    Used pervasively (Lemmas 2.3, 2.4, 3.4, 3.11, Theorem 1.7) to construct admissible paths and hence admissible cycles.
  • standard math Theorem 2.2 (Chiba-Ota-Yamashita): one extra low-degree vertex is allowed for admissible paths.
    Used in Lemmas 2.4, 3.11, and Theorem 1.6 to handle a third low-degree vertex.
  • standard math Theorem 3.2 (Gao-Huo-Ma): a 2-connected graph with minimum degree k containing a triangle has k cycles of consecutive lengths or is K_{k+1}.
    Used in Theorems 1.3, 1.4, and 1.7 for the triangle case.
  • standard math Theorems 3.6 and 3.7 (Gao-Huo-Liu-Ma): 3-connected bipartite/non-bipartite graphs with no small cycles and large minimum degree contain admissible cycles.
    Used in Theorem 1.3 for k≥6 after excluding triangles and 4-cycles.
  • standard math Theorem 4.1 (Bondy-Vince), Theorem 4.2 (Gao-Li-Ma-Xie), Theorem 4.3 (Dean-Lesniak-Saito), Theorem 4.6 (Chen-Saito and Dean et al.): small-k results for cycles modulo 3 and 4.
    Used to handle k=4 and k=6 in Theorems 1.4 and 1.6.
  • standard math Lemma 5.1 (Gao-Li-Ma-Xie): structural result on even cycles in 3-connected graphs.
    Used in Lemma 5.3 and Theorem 1.7.
  • standard math Theorem 6.1 (Woodall) and Theorem 6.2 (Bondy): extremal and pancyclic theorems.
    Used in the base case and the cut-vertex case of Theorem 1.10.
  • standard math Lin-Wang-Zhou [16]: every 2-connected non-bipartite graph with minimum degree at least k contains ⌈(k-1)/2⌉ cycles of consecutive odd lengths.
    The authors note Lemma 5.4 can be deduced from this result; not used in the proofs, but relevant to novelty.
  • domain assumption Assertion that every proper hypo-Petersen graph contains cycles of consecutive lengths from 5 to 9.
    Used in Lemma 3.11 to obtain a contradiction in the k=4,5 case; only supported by Figure 4, no detailed proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Cycle lengths in graphs of given minimum degree." pith.science (2026). https://pith.science/paper/PL44IKJK

@misc{pith2026251103085,
  author       = {Pith},
  title        = {Pith review of: Cycle lengths in graphs of given minimum degree},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PL44IKJK}},
  note         = {Machine review of arXiv:2511.03085}
}
abstract

We prove that if $G$ is a 2-connected graph with minimum degree at least $k\geqslant 4$, then (1) $G$ contains $k$ cycles whose lengths form an arithmetic progression with common difference one or two, unless $G\cong K_{k+1}$ or $K_{k,n-k}$; (2) $G$ contains cycles of lengths $\ell$ modulo $k$ for all even $\ell$, unless $G\cong K_{k+1}$ or $K_{k,n-k}$; (3) $G$ contains cycles of lengths $\ell$ modulo $k$ for all $\ell$, unless $G\cong K_{k+1}$ or $G$ is bipartite. In addition, we show that if $k$ is even and $G$ is 2-connected with minimum degree at least $k-1$ and order at least $k+2$, then $G$ contains cycles of lengths $\ell$ modulo $k$ for all even $\ell$. As a corollary, we determine the maximum number of edges in a graph that does not contain a cycle of length divisible by $k$ for all odd $k$.

Figures

Figures reproduced from arXiv: 2511.03085 by the authors.

Figure 1
Figure 1. Constructions of S, T, Q and Gi for i ∈ {1, 2, 3, 4} in Lemma 3.4. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Graph Fr. Claim 2.1. If C is a 5-cycle of G, then (1) C is an induced cycle of G, (2) every vertex outside C has at most one neighbor in C, and (3) if P is a V (C)-path in G of length 3, then its two end-vertices have distance exactly 2 in C (that is, G[V (C) ∪ V (P)] ∼= F2). Proof. All three statements can be deduced from the fact that G has neither a triangle nor a 4-cycle. Claim 2.2. G contains no F3. Proof. Supp… view at source ↗
Figure 3
Figure 3. Hypo-Petersen graphs. Now by Claims 2.4 and 2.3, H = G[{xi , yi , zi : i = 1, . . . , 5}] is a proper hypo-Petersen graph. It follows that H, and then, G, has cycles of lengths 5, 6, 7, 8, 9, a contradiction. Let C be a shortest cycle of G. By Claim 2, |C| ⩾ 6. Note that any vertex outside C has at most one neighbor in C as otherwise it creates a cycle of length at most |C|/2 + 2 < |C|, contradicting the minimality … view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The 6-, 7-, 8-, 9-cycles in a hypo-Petersen graph. [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]
Figure 5
Figure 5. Figure 5: Constructions of Li(x, y) (i = 1, . . . , 4) in Lemma 4.4. Proof. Suppose that G is a counterexample with the smallest number of edges. Since G + xy is 2-connected, we have that G is 2-connected or a block-chain. Claim 1. xy /∈ E(G). Proof. Suppose that xy ∈ E(G). Let …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 1 linked inside Pith

  1. [13]

    J. Gao, Q. Huo, C. Liu, J. Ma, A Unified Proof of Conjectures on Cycle Lengths in Graphs, Int. Math. Res. Not. 2022 (10) (2022) 7615–7653

    2022

  2. [16]

    H. Lin, G. Wang, W. Zhou, A strengthening on consecutive odd cycles in graphs of given minimum degree, J. Graph Theory 110 (4) (2025) 431–436

    2025

  3. [1]

    Y. Bai, B. Li, Y. Pan, S. Zhang, On graphs without cycles of length 1 modulo 3, arXiv:2503.03504

    arXiv

  4. [2]

    Bollob´ as, Cycles modulok, Bull

    B. Bollob´ as, Cycles modulok, Bull. London Math. Soc. 9 (1) (1977) 97–98

    1977

  5. [3]

    J. A. Bondy, Pancyclic graphs I, J. Combin. Theory Ser. B 11 (1) (1971) 80–84

    1971

  6. [4]

    J. A. Bondy, A. Vince, Cycles in a graph whose lengths differ by one or two, J. Graph Theory 27 (1998) 11–15

    1998

  7. [5]

    G. Chen, A. Saito, Graphs with a cycle of length divisible by three, J. Combin. Theory, Ser. B 60 (2) (1994) 277–292

    1994

  8. [6]

    Chiba, K

    S. Chiba, K. Ota, T. Yamashita, Minimum degree conditions for the existence of a sequence of cycles whose lengths differ by one or two, J. Graph Theory 103 (2) (2023) 340–358

    2023

Show all 21 references
  1. [7]

    Dean, Which graphs are pancyclic modulok, In Sixth International Conference on the Theory of Appli- cations of Graphs, 315–26

    N. Dean, Which graphs are pancyclic modulok, In Sixth International Conference on the Theory of Appli- cations of Graphs, 315–26. Kalamazoo, Michigan, 1988

    1988

  2. [8]

    N. Dean, A. Kaneko, K. Ota, B. Toft, Cycles modulo 3, Dimacs Technical Report 91 (32) (1991)

    1991

  3. [9]

    N. Dean, L. Lesniak, A. Saito, Cycles of length 0 modulo 4 in graphs, Discrete Math. 121 (1-3) (1993) 37–49. 29

    1993

  4. [10]

    P. Erd˝ os, Some recent problems and results in graph theory, combinatorics and number theory, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Congress. Numer. XVII (1976) 3–14

    1976

  5. [11]

    Furedi, D.S

    Z. Furedi, D.S. Gunderson, Extremal numbers for odd cycles, Combinatorics, Probability and Computing 24 (2015) 641–645

    2015

  6. [12]

    J. Gao, Q. Huo, J. Ma, A strengthening on odd cycles in graphs of given chromatic number, SIAM J. Discrete Math. 35 (4) (2021) 2317–2327

    2021

  7. [14]

    J. Gao, B. Li, J. Ma, T. Xie, On two cycles of consecutive even lengths, J. Graph Theory 106 (2) (2024) 225–238

    2024

  8. [15]

    Gy˝ ori, B

    E. Gy˝ ori, B. Li, N. Salia, C. Tompkins, K. Varga, M. Zhu, On graphs without cycles of length 0 modulo 4, J. Combin. Theory, Ser. B 176 (2026) 7–29

    2026

  9. [17]

    C. Liu, J. Ma, Cycle lengths and minimum degree of graphs, J. Combin. Theory, Ser. B 128 (2018) 66–95

    2018

  10. [18]

    Saito, Cycles of length 2 modulo 3 in graphs, Discrete Math

    A. Saito, Cycles of length 2 modulo 3 in graphs, Discrete Math. 101 (1992) 285–289

    1992

  11. [19]

    Sudakov, J

    B. Sudakov, J. Verstra¨ ete, The extremal function for cycles of lengthℓmodk, Electron. J. Combin. 24 (1) (2017) #P1.7

    2017

  12. [20]

    Thomassen, Graph decomposition with applications to subdivisions and path systems modulok, J

    C. Thomassen, Graph decomposition with applications to subdivisions and path systems modulok, J. Graph Theory 7 (1983) 261–271

    1983

  13. [21]

    D. R. Woodall, Sufficient Conditions for Circuits in Graphs, Proc. Lond. Math. Soc. 3 (4) (1972) 739–755. 30

    1972

Pith tools

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