Pith. sign in

REVIEW 2 major objections 4 minor 14 references

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

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

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

Pith's one-line read A 2-connected $n$-vertex graph with more than $\lfloor (3n-1)/2 \rfloor$ edges necessarily contains a cycle whose length is divisible by 4, and the bound is tight for every $n\ge 12$.

desk verdict New exact extremal bound for 2-connected graphs without (0 mod 4)-cycles, with a load-bearing classification that is only sketch-verified. read the letter →

arxiv 2507.12798 v1 pith:SZWGY5KX submitted 2025-07-17 math.CO

Hojin Chu , Boram Park , Homoon Ryu This is my paper
classification math.CO MSC 05C3505C3805C40
keywords 0mod4cyclesmodulokextremalgraphtheory2-connectedgraphsplanarEulerformulaedgeboundsgap-reducingconstructions
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

The paper establishes the exact extremal edge bound for 2-connected graphs that avoid cycles of length divisible by 4: any such graph on $n$ vertices has at most $\lfloor (3n-1)/2 \rfloor$ edges, and for every $n\ge 12$ there are 2-connected $n$-vertex graphs with exactly that many edges and no forbidden cycle. This adds a new exact value to the small catalogue of extremal numbers for cyclic length conditions, and it sharpens the general 0-mod-4 bound of $\lfloor 19(n-1)/12 \rfloor$ within the 2-connected class, where the known extremal examples fail to be 2-connected. The proof turns a global cycle-avoidance condition into a planar face-counting argument, with the hard work concentrated in a structural classification of what can sit on the two sides of any 2-vertex cut.

What carries the argument

The load-bearing object is the $L$-type classification: for a specified pair $(x,y)$, the pair is $L$-type when every $(x,y)$-path has length congruent modulo 4 to an element of $L$. Proposition 2.3 classifies all small graphs (up to $n=9$) of the four relevant two-element types, giving sharp edge bounds and identifying the extremal members up to reversal, and this classification drives the structural lemmas that force each side of a 2-vertex cut to be $K_3$, $F_3$, or $F_4$. Around it stand the parallel-sum operation for gluing graphs at two identified vertices, reversing-equivalence for swapping the two sides of a cut, and the gap function $\mathrm{gap}(G)=3n-1-2e(G)$ together with gap-reducing sequences that build the tight examples.

What would settle it

An exhaustive search over 2-connected graphs on at most, say, 12 vertices, or over all graphs $(H;x,y)$ with $n\le 9$, would settle the classification: the theorem is false if any 2-connected $n$-vertex graph without a $(0 \bmod 4)$-cycle has more than $\lfloor (3n-1)/2 \rfloor$ edges, and Proposition 2.3 is false if, for instance, a 7-vertex graph with $(x,y)$ a $\{2,3\}$-type has 9 edges or a 9-vertex $\{2,3\}$-type graph has 13 edges. Completing the omitted appendix cases by a certified exhaustive check would confirm the supporting classification.

Watch

Extended reading notes

Core claim

The central claim, Theorem 1.2, is that a 2-connected $n$-vertex graph with no $(0 \bmod 4)$-cycle has at most $\lfloor (3n-1)/2 \rfloor$ edges, and the threshold is tight: a family of constructions yields 2-connected $n$-vertex graphs with exactly $\lfloor (3n-1)/2 \rfloor$ edges for every $n\ge 12$. The upper-bound proof takes a minimal counterexample, invokes the known fact that non-planar graphs already contain a $(0 \bmod 4)$-cycle so the graph is planar, and then uses Euler's formula after showing there are at most two 3-faces and at most five 5-faces. That face control rests on Lemma 3.2, which says each side of every 2-vertex cut is, up to reversal, one of the tiny graphs $K_3$, $F_3$, or $F_4$; this is obtained from a classification of small graphs by their $(x,y)$-path-length types. The lower-bound side is a gap-function construction: operations that attach the small gadgets $F_3,F_4,F_6,F_7,F_8,F_9,P_4$, or $K_3$ along specified path-length types systematically reduce the gap $3n-1-2e(G)$, generating infinitely many tight examples.

Load-bearing premise

The proof depends on Proposition 2.3, a classification of small graphs with prescribed $(x,y)$-path-length types, and that classification is only sketched in the appendix with several cases deferred to an unverified computer check; if any of those small cases is wrong, the structural lemmas and the main theorem collapse.

Editorial extensions

If this is right

  • For $n\ge 12$, the maximum number of edges in a 2-connected $n$-vertex graph with no cycle whose length is divisible by 4 is exactly $\lfloor (3n-1)/2 \rfloor$.
  • Because $19/12$ exceeds $3/2$, the new bound is strictly stronger than the general 0-mod-4 bound for all sufficiently large $n$.
  • Every graph meeting the bound must be planar, since non-planar graphs already contain a 0-mod-4 cycle.
  • Extremal graphs exist for every $n\ge 12$ and can be generated in infinite families by gap-reducing sequences starting from a 5-cycle.
  • In any sufficiently large extremal example for the general $\lfloor 19(n-1)/12 \rfloor$ bound, every block must be small, since a large 2-connected block would violate the new bound.

Reading between the lines

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

  • The gap-reducing gadget machinery is a template that could plausibly transfer to other residue classes, such as cycles of length 1 or 2 mod 4, where the analogous 2-connected extremal numbers are not known.
  • The reliance on Proposition 2.3 means the theorem currently rests on an uncompleted case check; an independent certified exhaustive verification of the $n\le 9$ classification would turn a sketch plus code into a checkable proof.
  • The sharp contrast with the general $\lfloor 19(n-1)/12 \rfloor$ extremal graphs suggests that cut vertices are not incidental in the general construction: forcing 2-connectivity lowers the density to $3/2$, so a useful avenue is to study which block decompositions can realize the general bound.
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 determines the extremal number of edges in a 2-connected graph that contains no cycle of length 0 modulo 4. The main result, Theorem 1.2, states that any 2-connected n-vertex graph with more than floor((3n-1)/2) edges contains such a cycle, and Section 4 constructs 2-connected extremal graphs attaining exactly floor((3n-1)/2) edges for every n >= 12. The proof proceeds by taking a minimal counterexample, using the result of [9] that every non-planar graph contains a (0 mod 4)-cycle to reduce to planar graphs, analyzing the structure of 2-vertex cuts through a sequence of lemmas culminating in Lemma 3.2, bounding the numbers of 3-faces and 5-faces (Lemmas 3.13 and 3.14), and finally deriving a contradiction from Euler's formula. Tightness is shown by a gap-reducing construction based on the small graphs F3, F4, F6, F7, F8, and F9.

Significance. If the main theorem is correct, it provides the first exact extremal result for cycles of length 0 modulo 4 within the 2-connected class, giving a linear coefficient of 3/2 instead of the general bound 19/12 from [9]. The result would also add a clean exact value to the catalogue of c_{ell,k} constants for a constrained graph class, and the proposed construction method in Section 4 appears flexible enough to produce many extremal examples. The overall architecture of the proof is convincing: the reduction to a planar minimal counterexample, the vertex-cut decomposition, and the Euler-formula face-counting argument are all coherent. The paper also makes an honest attempt to handle finite cases by providing code, but that code is not yet in a form that makes the classification independently verifiable; this is the main obstacle to accepting the proof as complete.

major comments (2)
  1. [Appendix, proof of Proposition 2.3] The proof of Proposition 2.3 is not complete as written. The appendix explicitly states that 'Some cases are written in a rough way,' that case (A5) ends with 'tedious case checking,' and that verification is delegated to a GitHub repository with no commit hash, no run instructions, and no certificate that the code enumerates exactly the cases (A1)-(A5). Proposition 2.3 is load-bearing: it drives Lemma 3.5, Lemma 3.7, and Lemma 3.2, which in turn produce the triangle and 5-face bounds used in the Euler-formula contradiction. A wrong or missing case in this finite classification would invalidate Theorem 1.2. Please provide a fully written proof of all five cases or a versioned, executable certificate whose coverage of (A1)-(A5) is machine-checked.
  2. [Section 3.1, Lemma 3.5(i) and Claim 3.8] The equality characterization in Proposition 2.3 is used in a quantitative way, not merely as an upper bound. In Lemma 3.5(i) the argument distinguishes whether G1 is reversing-equivalent to F7 and whether G2 is reversing-equivalent to F8, and in Claim 3.8 it requires that G2 is reversing-equivalent to F9 when 5 <= n2 <= 9. The numerical contradictions depend on these exact classifications, so the unverified structural part of Proposition 2.3 is directly responsible for the face-counting contradiction. This strengthens the need to make the appendix's verification fully rigorous.
minor comments (4)
  1. [Section 2.2] The phrase 'reserving-equivalent' should be 'reversing-equivalent' throughout the definition and subsequent usage.
  2. [Lemma 2.7(iv) proof] In the sentence 'V(H) ∩ E(Ci) = ∅', the first set should presumably be 'E(H)', so that the condition reads 'E(H) ∩ E(Ci) = ∅'; as written it is not meaningful.
  3. [Appendix, code repository] The repository link should be accompanied by a version identifier (commit hash) and explicit instructions for reproducing the verification; ideally the code should output a certificate that each of the enumerated cases (A1)-(A5) is covered.
  4. [Section 4] The constructions in Figure 14 are described briefly; a short explanation of why the two displayed examples have no (0 mod 4)-cycles would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the extremal bound is derived from structural lemmas and Euler's formula; the small-graph classification is an auxiliary lemma, not an input that already encodes the result.

full rationale

The paper's central claim, Theorem 1.2, is proved by contradiction using Euler's formula: after establishing that a minimal counterexample has at most two 3-faces and at most five 5-faces, the inequality e(G) = n + f(G) - 2 <= (3n-1)/2 is obtained by arithmetic from face counts, not by invoking the theorem being proved. The structural lemmas (Lemma 3.2, Lemma 3.7, Proposition 2.3) are auxiliary classifications of local configurations; they do not define the extremal number in terms of the final bound. Proposition 2.3 is an input lemma with a case-checking proof in the appendix and a supplementary code repository; its status as an unverified or partially sketched proof is a correctness and reproducibility concern, not a circularity concern, because the lemma does not assume the theorem and is not fitted from the target quantity. The paper relies on external results [5] and [9] for 3-connected graphs and for the general (0 mod 4)-cycle bound; these citations are from different author groups and provide independent support rather than a self-citation chain. The extremal constructions in Section 4 use the gap function gap(G) = (3n-1) - 2e(G) and explicit gadgets that are checked to preserve or reduce the gap; tightness is verified by construction, not by asserting the theorem. No fitted parameter is renamed as a prediction, and no known result is repackaged under new coordinates. The reader's suspicion about the verification gap in Proposition 2.3 is legitimate but belongs under correctness risk, not circularity. Overall, the derivation is self-contained and no circular step is exhibited.

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

The central claim rests on standard graph theory (Menger, Euler, Ramsey r(3,3)=6), on imported results from [5] (3-connected graphs contain a 0 mod 4 cycle) and [9] (non-planar graphs contain such a cycle; even theta graphs; bipartite bounds; odd-cycle intersection lemmas), and on the paper's own Proposition 2.2 (proved) and Proposition 2.3 (appendix sketch plus code). No numeric free parameters are fitted; the only hand-chosen elements are the six gadget graphs and the reversing operation, which are discrete objects whose type properties are checkable by finite inspection. The most fragile input is the code-verified classification of Proposition 2.3, which the authors describe as rough and do not certify.

assumptions (7)
  • standard math Menger's theorem (pairwise vertex-disjoint (X,Y)-paths versus separating sets)
    Invoked as Theorem 2.1 in Proposition 2.2, Lemma 3.4, Lemma 3.13, and Proposition 2.8.
  • standard math Euler's formula n + f = e + 2 for connected planar graphs
    Used in Section 3 to convert the face bounds f3 <= 2, f4 = 0, f5 <= 5 into e(G) <= (3n-1)/2.
  • standard math Ramsey number r(3,3) = 6
    Used in Lemma 3.14 to conclude that six 5-faces force three that pairwise intersect at a vertex or three that pairwise share a length-2 path.
  • domain assumption Theorem 2.4 (Dean, Lesniak, Saito): every 3-connected graph contains a (0 mod 4)-cycle
    Justifies that the minimal counterexample G is not 3-connected, so 2-vertex cuts exist and drive the structural analysis.
  • domain assumption Theorem 2.5 from [9]: non-planar graphs contain a (0 mod 4)-cycle; even theta graphs contain one; bipartite n-vertex graphs without (0 mod 4)-cycles have at most 3(n-2)/2 edges
    Gives planarity of G (the premise of the Euler argument), forbids even theta structures, and supplies the bipartite edge bound used in Lemma 3.4 and the appendix.
  • domain assumption Lemma 2.6 from [9]: structural facts about triples of odd cycles congruent modulo 4
    Source of Lemma 2.7 and Proposition 2.8, used throughout the triangle and 5-face analyses in Lemmas 3.13 and 3.14.
  • ad hoc to paper Correctness and completeness of the code-based verification of the finite cases of Proposition 2.3
    The appendix delegates cases (A1)-(A5) partly to the repository github.com/Homoon-ryu/2con_0mod4-cycle_free without providing a commit hash, an enumeration, or a certificate; the main proof loads Proposition 2.3 in Lemmas 3.5, 3.7, and 3.2.
invented entities (3)
  • Gadget graphs F3, F4, F6, F7, F8, F9 with specified vertices (a,b)
    purpose: Building blocks for parallel sums; their (a,b)-path-length types control which cycles appear after gluing, enabling the vertex-cut classification (Lemma 3.2) and the extremal constructions (Section 4).
    New to this paper; their type properties rest on finite inspection of Figure 1, with no external confirmation.
  • Reversing-equivalence operation on a 2-vertex cut
    purpose: Reduces small-graph classifications by preserving edge count and cycle lengths; used in Proposition 2.3 and Lemma 3.7.
    A definition introduced by the authors (the text also calls it 'reserving-equivalent'); it is an internal transformation, not an externally testable entity.
  • Gap function gap(G) = (3n-1) - 2e(G)
    purpose: Tracks distance from the extremal edge count through gluing steps; Propositions 4.1-4.2 show which gadgets strictly reduce the gap, yielding infinitely many tight examples.
    A bookkeeping tool internal to Section 4; no independent handle outside the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On $2$-connected graphs avoiding cycles of length $0$ modulo $4$." pith.science (2026). https://pith.science/paper/SZWGY5KX

@misc{pith2026250712798,
  author       = {Pith},
  title        = {Pith review of: On $2$-connected graphs avoiding cycles of length $0$ modulo $4$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SZWGY5KX}},
  note         = {Machine review of arXiv:2507.12798}
}
abstract

For two integers $k$ and $\ell$, an $(\ell \text{ mod }k)$-cycle means a cycle of length $m$ such that $m\equiv \ell\pmod{k}$. In 1977, Bollob\'{a}s proved a conjecture of Burr and Erd\H{o}s by showing that if $\ell$ is even or $k$ is odd, then every $n$-vertex graph containing no $(\ell \text{ mod }k)$-cycles has at most a linear number of edges in terms of $n$. Since then, determining the exact extremal bounds for graphs without $(\ell \text{ mod }k)$-cycles has emerged as an interesting question in extremal graph theory, though the exact values are known only for a few integers $\ell$ and $k$. Recently, Gy\H{o}ri, Li, Salia, Tompkins, Varga and Zhu proved that every $n$-vertex graph containing no $(0 \text{ mod }4)$-cycles has at most $\left\lfloor \frac{19}{12}(n -1) \right\rfloor$ edges, and they provided extremal examples that reach the bound, all of which are not $2$-connected. In this paper, we show that a $2$-connected graph without $(0 \text{ mod } 4)$-cycles has at most $\left\lfloor \frac{3n-1}{2} \right\rfloor$ edges, and this bound is tight by presenting a method to construct infinitely many extremal examples.

Figures

Figures reproduced from arXiv: 2507.12798 by the authors.

Figure 1
Figure 1. Graphs (Fi ; a, b) and deleting a loop or multiple edges. When P is a path and the ends of P are a and b, we simply denote (G; x, y) ⊎ (P; a, b) by (G; x, y) ⊎ P. For a vertex cut {x, y} of a graph G, a connected component S of G− {x, y}, a reverse of G at {x, y} with S means a graph H = (H1; x, y) ⊎ (H2; y, x), where H1 = G[V (S) ∪ {x, y}] and H2 = G − V (S). We also say H is obtained by reversing G. Note that for … view at source ↗
Figure 2
Figure 2. Graphs that are reversing-equivalent to F9 in [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Illustrations for Lemma 2.7 (i) and (ii) [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (11 more)
Figure 4
Figure 4. Figure 4: An illustration for Proposition 2.8 Proof. We note that since G has no C4, |V (Ti) ∩ V (Tj )| ≤ 1 for every distinct i, j ∈ {1, 2, 3}. First, suppose that |V (Ti) ∩ V (Tj )| = 1 for every distinct i, j ∈ {1, 2, 3}. By Lemma 2.7 (iv), there is a unique vertex v in V (T1…
Figure 5
Figure 5. Figure 5: Illustrations for (Case 1) (Case 2) Now suppose that |V (T3)∩U| ≥ 2. If V (T3)∩U contains {t1, t2}, then P, Q, and t1t2 are three vertex-disjoint (V (T1), V (T2))-paths, which is a contradiction by Lemma 2.7 (iii). Thus we may assume that t2 ̸∈ V (T3). Then |V (T3)∩V (…
Figure 6
Figure 6. Figure 6: Illustrations for (Case 2) 3 Proof of Theorem 1.2 Let G be a minimal counterexample to Theorem 1.2, and let n = |V (G)|. That is, G is a 2-connected graph that contains no (0 mod 4)-cycle, e(G) > 3n−1 2 , and every 2-connected graph G′ of order less than n has at most …
Figure 7
Figure 7. Figure 7: An illustration for Claim 3.6 Proof. Take an (x, y)-path Q in G1. Let ℓ(Q) ≡ t (mod 4) for some t ∈ {0, 1, 2, 3}. Let G∗ 2 = (G2; x, y)⊎ Pt+1. Then G∗ 2 is 2-connected, has no (0 mod 4)-cycles, and |V (G∗ 2 )| ≤ n. Recall that xy ̸∈ E(G). Suppose that |V (G∗ 2 )| < n. …
Figure 8
Figure 8. Figure 8: Illustrations for Claim 3.10, where thick lines show the path [PITH_FULL_IMAGE:figures/full_fig_p014_8.png]
Figure 9
Figure 9. Figure 9: An illustration for Lemma 3.13, where the shaded parts represent [PITH_FULL_IMAGE:figures/full_fig_p016_9.png]
Figure 10
Figure 10. Figure 10: Illustrations for the cases (1)∼(3), where the shaded parts represent the parts containing the end vertices of R. For the case (5), if b = t2, then P, Q, R are three vertex-disjoint paths between V (T1) and V (T2), and, if b = t3, then P[p1, p3], Q[q1, q3], R are thre…
Figure 11
Figure 11. Figure 11: Illustrations for the cases (4) and (6), where the shaded part represent the part containing [PITH_FULL_IMAGE:figures/full_fig_p017_11.png]
Figure 12
Figure 12. Figure 12: An illustration for Claim 3.16. Note that G is a plane graph and C1, C2, C3 are faces. Then G0 = G − {v, w, w1, w2} is 2-connected. By the minimality of G, e(G0) ≤ 3(n−4)−1 2 . Then e(G) = e(G0) + 6 ≤ 3(n−4)−1 2 + 6 = 3n−1 2 , which is a contradiction. Recall that eve…
Figure 13
Figure 13. Figure 13: A gap-reducing sequence σ : G0, G1, . . . , G7 by the procedures (R1), (R2), and (R3) As one can observe from the example in [PITH_FULL_IMAGE:figures/full_fig_p020_13.png]
Figure 14
Figure 14. Figure 14: Tight examples j In [9], the authors construct an n-vertex graph G without (0 mod 4)-cycles such that e(G) = 19(n−1) 12 k as follows. They also denote some graphs reversing-equivalent to the graphs F8 and (F7; a, b)⊎ (F8; a, b) by L8 and L13, respectively. Extremal ex…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [9]

    On graphs without cycles of length 0 modulo 4

    E. Gy ˝ori, B. Li, N. Salia, C. Tompkins, K. V arga, and M. Zhu , On graphs without cycles of length 0 modulo 4, arXiv:2312.09999

    work page Pith review arXiv

  2. [1]

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

    work page

  3. [2]

    Bollob´as

    B. Bollob´as. Cycles modulo k, Bulletin of the London Mathematical Society , 9(1):97–98, 1977

    work page 1977

  4. [3]

    G. T. Chen and A. Saito , Graphs with a cycle of length divisible by three, Journal of Combi- natorial Theory, Series B , 60(2):277–292, 1994

    work page 1994

  5. [4]

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

    work page 1991

  6. [5]

    N. Dean, L. Lesniak, and A. Saito, Cycles of length 0 modulo 4 in graphs,Discrete Mathematics, 121(1–3):37–49, 1993. 21

    work page 1993

  7. [6]

    Erd˝os, Some recent problems and results in graph theory, combinatorics, and number theory, In Proc

    P. Erd˝os, Some recent problems and results in graph theory, combinatorics, and number theory, In Proc. Seventh SE Conf. Combinatorics, Graph Theory and Computing, Utilitas Math , 3–14, 1976

    work page 1976

  8. [7]

    G. F an, X. L v, and P. W ang, Cycles in 2-connected graphs, Journal of Combinatorial Theory, Series B , 92(2):379–394, 2004

    work page 2004

Show all 14 references
  1. [8]

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

    2024

  2. [10]

    B. Li, Y. Pan and L. Shi , A note on two cycles of consecutive even lengths in graphs, arXiv:2506.08692

    arXiv

  3. [11]

    O. R. Oellermann, L. W. Beineke, and R. J. Wilson , Menger’s theorem, In Topics in Structural Graph Theory, Cambridge University Press, 13–39, 2013

    2013

  4. [12]

    Saito, Cycles of length 2 modulo 3 in graphs, Discrete Mathematics, 101(1–3):285–289, 1992

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

    1992

  5. [13]

    Sudakov and J

    B. Sudakov and J. Verstra ¨ete, The extremal function for cycles of length ℓ mod k, The Electronic Journal of Combinatorics , 24(1), 2017

    2017

  6. [14]

    Verstra ¨ete, Extremal problems for cycles in graphs, In Recent trends in combinatorics , Springer, 83–116, 2016

    J. Verstra ¨ete, Extremal problems for cycles in graphs, In Recent trends in combinatorics , Springer, 83–116, 2016. Appendix We provide a sketch of the proof of Proposition 2.3. Some cases are written in a rough way, as they are straightforward yet tedious to check. Due to th...

    2016

Pith tools

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