Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

A note on two cycles of consecutive even lengths in graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read An n-vertex graph above a sharp edge bound always contains two consecutive even cycles, and the only graphs at the bound are chains of K5 cliques.

desk verdict This paper proves the k=2 case of Sudakov–Verstraëte and determines ex(n,C_{2 mod 4}) with exact extremal graphs, but one case in the proof has a literally false inference that is nevertheless repairable. read the letter →

arxiv 2506.08692 v1 pith:V75EDFGH submitted 2025-06-10 math.CO

Binlong Li , Yufeng Pan , Lingjuan Shi This is my paper
classification math.CO MSC 05C3505C38
keywords consecutiveevencyclesextremalgraphtheoryTuránnumberoflength2mod4blockdecompositionK5cliquescycledistributioncliqueblocks
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 settles, for every $n$, the exact maximum number of edges a graph on $n$ vertices can have while avoiding two cycles whose even lengths differ by 2. Writing $n-1 = 4q + r$ with $0\le r < 4$, the maximum is $10q + \binom{r+1}{2}$, and the only graphs attaining it are connected graphs made of $q$ blocks isomorphic to $K_5$, plus one block $K_{r+1}$ when $r$ is nonzero. This proves the $k=2$ case of the conjecture that edge-maximal graphs avoiding $k$ consecutive even cycle lengths have all blocks of order at most $2k+1$. The result upgrades an earlier average-degree theorem into a sharp extremal statement and identifies the extremal graphs exactly.

What carries the argument

The central object is the class $G_n$ of block-chain graphs, whose blocks are all $K_5$'s with at most one clique remainder. The argument is carried by an induction that reduces a hypothetical counterexample to a graph with a 2-cut: Claim 1 invokes the cited theorem that every 3-connected graph on at least 6 vertices already contains two cycles of consecutive even lengths, ruling out higher connectivity. The remaining machinery consists of Lemma 2, which shows that adjoining one or two vertices with a few edges to a graph in $G_n$ either creates the desired two cycles or yields a spanning subgraph of a larger member of $G_{n+1}$ or $G_{n+2}$, and Lemma 4, which converts a 2-cut with a degree-sum condition on edges into two cycles of consecutive even lengths by splicing paths of length difference 2.

What would settle it

Search for a 3-connected graph on at least six vertices with no two cycles of consecutive even lengths; one such graph would contradict the cited theorem from [11] on which Claim 1 rests and would break the induction. Alternatively, a single $n$-vertex graph with $n-1=4q+r$ and more than $10q + \binom{r+1}{2}$ edges but no two cycles of consecutive even lengths would refute the main theorem directly.

Watch

Extended reading notes

Core claim

The paper claims that the extremal function for cycles of length $2$ modulo $4$ is exactly $10q + \binom{r+1}{2}$ for $n-1=4q+r$ with $0\le r<4$, and that the extremal graphs are precisely the connected graphs whose blocks are $q$ copies of $K_5$ together with one smaller clique $K_{r+1}$ when $r$ is nonzero. Any graph with more edges than this threshold must contain two cycles of consecutive even lengths, while graphs at the threshold avoid such pairs because their cycles lie inside cliques of order at most $5$, so the only even cycle length available is $4$ and the consecutive pair $4,6$ cannot appear. The proof is by induction on $n$; it first shows that a counterexample would have connectivity exactly $2$, then handles the four possible residues of $n$ modulo $4$ separately.

Load-bearing premise

The proof assumes, without proving it here, a theorem from the earlier article [11] that every 3-connected graph with at least 6 vertices contains two cycles of consecutive even lengths; if that theorem were false, the induction's first step would fail and the whole reduction to 2-connected graphs would collapse.

Editorial extensions

If this is right

  • The exact maximum number of edges in an $n$-vertex graph with no two consecutive even cycles is now known for every $n$: $10q + \binom{r+1}{2}$ with $n-1=4q+r$.
  • Any graph above this edge count must contain two cycles of consecutive even lengths; in particular, it must contain a 4-cycle and a 6-cycle.
  • The edge-maximal graphs avoiding such pairs are completely classified as chains of $K_5$ blocks, with one smaller clique block allowed when $n$ is not $1$ modulo $4$.
  • Because these extremal graphs contain no cycle of length $2$ modulo $4$, the same threshold governs the maximum edges in a graph with no such cycle at all, unifying the pair-avoidance and family-avoidance bounds.
  • The result confirms the predicted block-clique structure for the $k=2$ case of the general conjecture on $k$ consecutive even cycle lengths.

Reading between the lines

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

  • Going beyond the paper: the same induction template could plausibly prove the general $k$ case if a matching theorem for 3-connected graphs with $k$ consecutive even cycles is available.
  • Going beyond the paper: the exact edge maximum for cycles of length $2$ modulo $4$ sharpens the comparison with the known bound for cycles of length $0$ modulo $4$, bringing the open problem of classifying those extremal graphs into sharper focus.
  • Going beyond the paper: a natural test is whether the same threshold forces two cycles of lengths differing by exactly 2 when the parity restriction is dropped; the extremal structures would likely differ.
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.

Referee Report

2 major / 4 minor

Summary. The paper proves Theorem 3: if n−1=4q+r with 0≤r<4 and an n-vertex graph G has e(G)≥10q+binom(r+1,2), then G contains two cycles of consecutive even lengths unless G is a connected 'tree of cliques' consisting of q blocks K5 and, when r≠0, one further block K_{r+1}. This confirms the k=2 case of the Sudakov–Verstraëte conjecture and, as explained in Section 4, gives the exact Turán number ex(n,C_{2 mod 4}) together with all extremal graphs. The proof is by induction on n. Claim 1 reduces the problem to 2-connected graphs using Theorem 5; the cases r=1,2,3 are then treated via the 2-cut structure, Lemma 4, and Lemma 2, with a case analysis on the minimum degree. The overall strategy is sound, but some applications of Lemma 2 require repair, most notably in Case 2.1.

Significance. If the proof is completed, the result is a natural and nontrivial step: it upgrades the extremal result of Gao, Li, Ma and Xie (the k=2 Verstraëte case) to the stronger Sudakov–Verstraëte form, with a clean characterization of all extremal graphs. The paper also yields the exact Turán number for the family C_{2 mod 4}, complementing the known C_{0 mod 4} result. The exposition is concise and the induction skeleton is coherent; the main gaps are local and repairable. I note the dependence on Theorems 4 and 5 from [11], which are published but not reproduced; assuming those results are correct, the new arguments in Cases 2–4 are mostly sound.

major comments (2)
  1. [Section 3, Case 2.1] The sentence 'By Lemma 2, G'∈G_{n−1}' is not justified and is literally impossible: after fixing d_{G'}(v)=3 we have e(G')=10q−1, whereas every member of G_{n−1} has exactly 10q edges. What Lemma 2(i) yields is only that the graph obtained from G'' by adding v and any two of the three edges incident with v is a spanning subgraph of some H∈G_{n−1}. Because H has no remainder block and contains G'' (whose remainder block B0 is a K4), v must be adjacent in H only to the four vertices of B0; choosing the two edges arbitrarily then forces all three neighbors of v in G' to lie in B0. The subsequent assertion that G' contains four (u1,u2)-paths of consecutive lengths should be derived from Claim 1 applied to G''∈G_{n−2} or to H, not from the false membership G'∈G_{n−1}. The case is repairable, but as written the proof of the only part of Case 2.1 not already covered by Theorem 2 or Lemma 4 is incomplete.
  2. [Section 3, Case 4] The step 'By Lemma 2 (i), G either contains two cycles of consecutive even lengths or G is a subgraph of a member in G_n' does not follow directly when d(v)=3, because Lemma 2(i) is stated only for a vertex added with two edges. The argument can be repaired by applying Lemma 2(i) to any two of v's incident edges; the resulting H∈G_n has q K5-blocks plus a K4 remainder, which forces the two selected neighbors of v to lie in B0, and hence, since the two edges are arbitrary, all three neighbors of v lie in B0. This also shows that the third edge is harmless. Please add this justification; as written the proof of δ(G)≥4 skips the degree-three case.
minor comments (4)
  1. [Section 3, Case 3] The inference 'This implies that all neighbors of u_i, v_i in G' are in B0' should be expanded: since H∈G_{n−2} has no remainder block and contains G' with its triangle remainder B0, the only 5-vertex block of H containing B0 is B0∪{u_i,v_i}, so all edges from u_i and v_i to G' go to B0. Please spell out this structural argument before applying Lemma 1(iii).
  2. [Section 2, Lemma 3] The proof of Lemma 3 is only a reference to a 'known' Menger consequence; since Lemma 3 is essential to Lemma 4, please include a short derivation or a precise citation for the existence of (x,y)-paths of both parities in a 2-connected non-bipartite graph.
  3. [Section 2, Lemma 2, Claim 1] When u and v lie in different blocks, the 'common path from w to v' should be chosen internally disjoint from B\{w} so that the four resulting (u,v)-paths, and the cycles built from them, are simple; please add this detail.
  4. [Section 4] The displayed formula for ex(n,C_{0 mod 4}) appears to have a missing floor; the intended statement is likely ex(n,C_{0 mod 4})=⌊19(n−1)/12⌋. Please correct the typography.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the new cases are proved by induction from independent published lemmas, and the cited self-results are not the target theorem.

full rationale

The main theorem is a genuine extension, not a restatement of its inputs. The r=0 residue is explicitly quoted from the prior theorem ('Case 1. r=0... deduced from Theorem 2, immediately'), and the new residues r=1,2,3 are proved by induction using original reductions (Lemma 2, Lemma 4) rather than by assuming the conclusion. The only load-bearing imported result is Theorem 5 of [11], used in Claim 1 to rule out 3-connectivity ('By the Theorem 5 and the assumption of G, G is not 3-connected'). That cited theorem is independent of the present statement: it concerns all 3-connected graphs of order at least 6, whose edge counts can be as low as 3n/2, while the present threshold is about (5/2)(n-1). It is a published, parameter-free result whose assumptions do not contain the target theorem, so under the review rules it is real evidence and does not raise the circularity score. Theorems 2 and 4 are likewise external lemmas. No parameter is fitted to the conclusion, the extremal class G_n is characterized by induction rather than assumed, and the concluding Turan-number identities are immediate consequences or standard equivalences. No circular step can be exhibited by reduction of an equation or by definition.

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

The proof is fully graph-theoretic and adds no fitted parameters or new entities. It rests on four external theorems from Bondy-Vince and Gao-Li-Ma-Xie, two of which are coauthored by B. Li; these are published results used as black boxes, not assumptions of the target result.

assumptions (5)
  • domain assumption Theorem 1 (Bondy-Vince): every graph with at most two vertices of degree less than three contains two cycles whose lengths differ by one or two.
    Invoked in the proof of Lemma 4 to obtain two cycles of lengths differing by 1 or 2 in the component G2 (Section 3).
  • domain assumption Theorem 4 (Gao et al.): under certain degree conditions there exist two (x,y)-paths whose lengths differ by two.
    Used in the proof of Lemma 4 to get paths P1,P2 in G1.
  • domain assumption Theorem 5 (Gao et al.): every 3-connected graph of order at least 6 contains two cycles of consecutive even lengths.
    Used in Claim 1 of Theorem 3 to force κ(G)=2.
  • domain assumption Theorem 2 (Gao et al.): the k=2 case of Verstraëte's conjecture, used to settle Case r=0.
    Section 3, Case 1: the r=0 case is deduced directly from Theorem 2.
  • standard math Disjoint (X,Y)-path theorem for k-connected graphs (Menger-type), used to derive Lemma 3.
    Invoked before Lemma 3: 'It is known that for a k-connected graph...' to obtain an odd and an even (x,y)-path in a non-bipartite 2-connected graph.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A note on two cycles of consecutive even lengths in graphs." pith.science (2026). https://pith.science/paper/V75EDFGH

@misc{pith2026250608692,
  author       = {Pith},
  title        = {Pith review of: A note on two cycles of consecutive even lengths in graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V75EDFGH}},
  note         = {Machine review of arXiv:2506.08692}
}
abstract

Bondy and Vince proved that a graph of minimum degree at least three contains two cycles whose lengths differ by one or two, which was conjectured by Erd\H{o}s. Gao, Li, Ma and Xie gave an average degree counterpart of Bondy-Vince's result, stating that every $n$-vertex graph with at least $\frac{5}{2}(n-1)$ edges contains two cycles of consecutive even lengths, unless $4|(n-1)$ and every block of $G$ is a clique $K_5$. This confirms the case $k=2$ of Verstra\"ete's conjecture, which states that every $n$-vertex graph without $k$ cycles of consecutive even lengths has edge number $e(G)\leq\frac{1}{2}(2k+1)(n-1)$, with equality if and only if every block of $G$ is a clique of order $2k+1$. Sudakov and Verstra\"{e}te further conjectured that if $G$ is a graph with maximum number of edges that does not contain $k$ cycles of consecutive even lengths, then every block of $G$ is a clique of order at most $2k+1$. In this paper, we prove the case $k=2$ for Sudakov-Verstra\"{e}te's conjecture, by extending the results of Gao, Li, Ma and Xie.

Discussion (0). Sign in 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

  1. On $2$-connected graphs avoiding cycles of length $0$ modulo $4$

    math.CO 2025-07 conditional novelty 7.0 of 10

    Every 2-connected n-vertex graph with more than floor((3n-1)/2) edges contains a cycle whose length is a multiple of 4, and this bound is sharp for all n at least 12.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages · cited by 1 Pith paper

  1. [11]

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

    work page 2024

  2. [1]

    Bollob´ as, Cycles modulok, Bull

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

    work page 1977

  3. [2]

    J. A. Bondy, U. S. R. Murty, Graph Theory, 2008

    work page 2008

  4. [3]

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

    work page 1998

  5. [4]

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

    work page 1994

  6. [5]

    Minimum degree conditions for the existence of cycles of all lengths modulo $k$ in graphs

    S. Chiba, T. Yamashita, Minimum degree conditions for the existence of cycles of all lengths modulokin graphs, arXiv:1904.03818 [math.CO]

    work page Pith review arXiv 1904

  7. [6]

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

    work page 1993

  8. [7]

    Diwan, Cycles of even lengths modulok

    A. Diwan, Cycles of even lengths modulok. J. Graph Theory 65 (2010) 246–252. 9

    work page 2010

Show all 16 references
  1. [8]

    Fan, Distribution of cycle lengths in graphs, J

    G. Fan, Distribution of cycle lengths in graphs, J. Comb. Theory Ser. B 84 (2002) 187–202

    2002

  2. [9]

    F ¨uredi, D.S

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

    2015

  3. [10]

    J. Gao, Q. Huo, C. Liu, J. Ma, A unified proof of conjectures on cycle lengths in graphs, Int. Math. Res. Not. 10 (2022) 7615–7653

    2022

  4. [12]

    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, arXiv: 2312.09999 [math.CO]

    arXiv

  5. [13]

    Sudakov, J

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

    2017

  6. [14]

    Thomassen, Cycles in graphs of uncountable chromatic number, Combinatorica 3 (1983) 133–134

    C. Thomassen, Cycles in graphs of uncountable chromatic number, Combinatorica 3 (1983) 133–134

    1983

  7. [15]

    Thomassen, Paths, Circuits and Subdivisions in: Selected Topics in Graph Theory 3, L

    C. Thomassen, Paths, Circuits and Subdivisions in: Selected Topics in Graph Theory 3, L. Beineke, R. Wilson eds., Academic Press (1988) 97–133

    1988

  8. [16]

    Verstra ¨ete, Extremal problems for cycles in graphs, In Recent Trends Combinatorics, A

    J. Verstra ¨ete, Extremal problems for cycles in graphs, In Recent Trends Combinatorics, A. Beveridge et al. (eds.), The IMA Volumes in Mathematics and its Applications 159, 83–116, Springer, New York, 2016. 10

    2016

Pith tools

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