pith. sign in

arxiv: 2606.02356 · v2 · pith:HFH4JUKAnew · submitted 2026-06-01 · 🧮 math.CO

On 2-connected graphs without cycles of length 1 modulo 3

Yandong Bai , Hojin Chu , Binlong Li , Boram Park , Homoon Ryu This is my paper

Pith reviewed 2026-06-28 13:53 UTC · model grok-4.3

classification 🧮 math.CO
keywords extremal graph theorycycle lengths modulo k2-connected graphsforbidden cyclesPetersen graphedge extremal function
0
0 comments X

The pith

The maximum number of edges in a 2-connected graph without cycles of length 1 modulo 3 is determined with a complete characterization of the extremal graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors determine the largest possible number of edges in an n-vertex 2-connected graph that contains no cycle whose length is congruent to 1 modulo 3. They give both the sharp upper bound on the edge count and identify all graphs that meet it. This reveals that the extremal 2-connected graphs have structures unlike the ones built from Petersen graph blocks in the general case. Combining the new result with the earlier general-case bound produces a full description of every extremal graph, even when 9 does not divide n-1. The paper also settles the corresponding problem for graphs avoiding cycles of length 2 modulo 4 in the 2-connected setting.

Core claim

In the 2-connected setting, the extremal number of edges in an n-vertex graph with no cycle of length 1 modulo 3 is determined exactly, and the graphs attaining this number are completely characterized. These extremal graphs differ structurally from those in the non-2-connected case. The same determination is made for the 2-connected graphs without cycles of length 2 modulo 4. As a consequence, the extremal numbers for 2-connected graphs without cycles of a fixed length modulo k are now known for every k at most 4.

What carries the argument

The extremal function for the number of edges in 2-connected graphs forbidding cycles of length ≡1 mod 3, together with the explicit structural characterization of the graphs attaining the maximum.

Load-bearing premise

That every extremal graph on more than 18 vertices in the general setting must contain a cut-vertex.

What would settle it

A single 2-connected graph on n vertices for some n > 18 with no cycle of length congruent to 1 modulo 3 and strictly more edges than the maximum stated by the characterization would disprove the claimed bound.

Figures

Figures reproduced from arXiv: 2606.02356 by Binlong Li, Boram Park, Hojin Chu, Homoon Ryu, Yandong Bai.

Figure 1
Figure 1. Figure 1: Graphs Hn, n ∈ {3} ∪ [5, 11]. Now we define the class Hn for all n ≥ 3, n ̸= 4: • For n ∈ {3, 5, 6, 7, 9, 10, 11}, Hn = {Hn}; • H8 = {H8, L2(H6)} (see [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Graph L2(H6). Recall that H10 is the Petersen graph. We denote by H − 10 the graph obtained from H10 by removing an arbitrary edge. Fact 2.5. If H ∈ H3 ∪ S15 n=5 Hn ∪ H′ 10 ∪ {H − 10}, then {x, y} is a 2-extendable pair if and only if H has an (x, y)-3-thread, unless H ∼= H8 and x, y have distance 2 in H and both have degree 2. Proof. The assertion can be proved by checking the graphs in H3 ∪ S15 n=5 Hn ∪ … view at source ↗
Figure 3
Figure 3. Figure 3: All non-isomorphic graphs in the class H′ 10 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: All non-isomorphic graphs in the class H12. 6 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The unique graph in Hn, n ≥ 13 is odd and k = 1 2 (n − 11). Proof. We denote by Πk the graph obtained from a Petersen graph P with an edge xy by adding a new vertex z, the edge xz, and k internally vertex-disjoint (y, z)-3-threads whose internal vertices are disjoint from P. Let H be a graph in Hn. We will show that H ∼= Πk. If n = 13, then H is a 3-extension of the Petersen graph H10. Note that H10 is edg… view at source ↗
Figure 6
Figure 6. Figure 6: Graphs K∗ 4 , Wˆ 4, K′ 3,3 and Kˆ (0) 3,3 . Lemma 3.4. Let G be an essentially 3-connected graph without (1 mod 3)-cycles. If G does not contain two vertex-disjoint cycles, then G is isomorphic to one of the following graphs, H7, H8, H9, H11, K∗ 4 , Wˆ 4, K′ 3,3 , Kˆ (i) 3,p with p ≥ 3 and i ∈ [0, 3]. (1) The proof of Lemma 3.4 will be given in Subsection 4.2. 4 Proofs An inner-vertex in a block is a verte… view at source ↗
Figure 7
Figure 7. Figure 7: Constructions of G in Fact 4.1 (2) Suppose first that τ = 0. If there are two edges incident to x2 that are not subdivided, say x2y1, x2y2, then x1y1x2y2x1 converts to a 4-cycle, a contradiction. It follows that at least two edges incident to x2 14 [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Constructions of G in Case 1 Suppose first that τ = 0. Then both H − v1 and H − v2 convert to an H7, implying that all edges between {v1, v2} and {v3, v4, v5} are subdivided. That is, G ∼= H11, as desired. Suppose second that τ = 2. Then both H − v1 and H − v2 convert to an H7 or H8. In each case τ (v3v1v4) = τ (v4v2v5) = 1. Now v3v1v4v2v5v3 converts to a 7-cycle, a contradiction. 15 [PITH_FULL_IMAGE:figu… view at source ↗
Figure 9
Figure 9. Figure 9: Constructions of G in Case 3 Suppose first that τ = 0. If τ (uv2v1) = 0, then uvpv1v2u converts to a 4-cycle; if τ (uv2v1) = 1, then uv1v2u converts to a 4-cycle, both contradictions. So we conclude that τ (uv2v1) = 2, and similarly, τ (uvp−1vp) = 2. That is, all four edges uv2, v1v2, uvp−1, vp−1vp are subdivided. Now vp−1uv2, vp−1vpv1v2, vp−1vpuv1v2 convert to three (vp−1, v2)-paths of length 4, 5, 6, res… view at source ↗
Figure 10
Figure 10. Figure 10: Graph Fk. Theorem 5.3. For n ≥ 3, ex2(n, C2 mod 4) =    [PITH_FULL_IMAGE:figures/full_fig_p018_10.png] view at source ↗
read the original abstract

Burr and Erd\H{o}s conjectured in 1976 that for all integers $k>\ell\geq 0$ such that $k\mathbb{Z}+\ell$ contains an even integer, every $n$-vertex graph without cycles of length $\ell$ modulo $k$ has at most a linear number of edges in $n$. Bollob\'{a}s confirmed the conjecture in 1977, and Erd\H{o}s further asked for the exact extremal number. To the best of our knowledge, this problem has been solved only for all residues when $k\leq 4$, and for $\ell\in \{0,2\}$ when $k\geq 5$ is odd. In particular, Bai {\it et al.} [arXiv:2503.03504] proved that if $G$ is an $n$-vertex graph with no cycles of length $1$ modulo $3$, then $e(G)\le \frac{5}{3}(n-1)$, and when $9\mid (n-1)$ the equality holds if and only if each block of $G$ is isomorphic to the Petersen graph. Note that for $n> 18$ every extremal graph contains a cut-vertex. In this paper, we investigate the 2-connected setting and determine the maximum number of edges in a 2-connected graph with no cycles of length $1$ modulo $3$. Our results provide a sharp extremal bound and a complete characterization of the extremal graphs, revealing structural differences from the general case. Combining this with the result of Bai {\it et al.}, we also obtain a complete characterization of all extremal graphs in the general setting, including the cases where $9\nmid (n-1)$. Finally, we determine the maximum number of edges in a $2$-connected graph with no cycles of length $2$ modulo $4$, whose extremal graphs differ substantially from those in the general setting. Consequently, the extremal numbers for $2$-connected graphs with no cycle of a fixed length modulo $k$ are now determined for all $k\leq 4$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper determines the maximum number of edges in a 2-connected n-vertex graph with no cycles of length 1 modulo 3, provides a sharp extremal bound together with a complete characterization of the extremal graphs, and combines the new 2-connected results with Bai et al. to obtain a complete characterization of all extremal graphs in the general (not necessarily 2-connected) setting, including the cases where 9 does not divide (n-1). It also determines the extremal number and extremal graphs for 2-connected graphs with no cycles of length 2 modulo 4.

Significance. If the results hold, the work completes the extremal function and structural classification for forbidden cycle lengths 1 mod 3 and 2 mod 4, both in the general and 2-connected settings, for all k ≤ 4. The explicit contrast between 2-connected and general extremal graphs supplies concrete structural information and falsifiable predictions.

major comments (1)
  1. [Introduction] Introduction (paragraph citing Bai et al.): the separation of the 2-connected analysis and the claimed completion of the general characterization when 9 does not divide (n-1) rest on the statement that 'for n>18 every extremal graph contains a cut-vertex.' This structural fact is attributed to Bai et al. but is neither re-derived nor given a precise theorem citation inside the manuscript; because the fact is load-bearing for both the separation and the completeness claim, an independent verification or explicit reference to the exact result in Bai et al. is required.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need for a more precise citation in the introduction. We address the major comment below.

read point-by-point responses

  1. Referee: [Introduction] Introduction (paragraph citing Bai et al.): the separation of the 2-connected analysis and the claimed completion of the general characterization when 9 does not divide (n-1) rest on the statement that 'for n>18 every extremal graph contains a cut-vertex.' This structural fact is attributed to Bai et al. but is neither re-derived nor given a precise theorem citation inside the manuscript; because the fact is load-bearing for both the separation and the completeness claim, an independent verification or explicit reference to the exact result in Bai et al. is required.

    Authors: We agree that a precise theorem citation is needed for this load-bearing structural fact. In the revised manuscript we will add an explicit reference to the specific theorem in Bai et al. [arXiv:2503.03504] establishing that for n>18 every extremal graph contains a cut-vertex. This will clarify the separation of cases and support the completeness claim for all n without requiring re-derivation in the present paper. revision: yes

Circularity Check

0 steps flagged

No significant circularity; 2-connected analysis is independent

full rationale

The paper derives a sharp extremal bound and complete characterization for 2-connected graphs without 1 mod 3 cycles through new combinatorial arguments, as stated in the abstract. It cites Bai et al. (arXiv:2503.03504) for the general-case bound and the note on cut-vertices for n>18 solely to separate the 2-connected case and extend the general characterization to when 9 does not divide (n-1). No equation, parameter, or prediction in the text reduces by construction to a fit or self-definition within this paper; the cited prior result functions as external support rather than a load-bearing reduction of the new claims. The derivation chain for the 2-connected results remains self-contained against the provided source text.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper is a pure proof paper in extremal graph theory. It relies on background theorems rather than introducing fitted parameters or new entities.

axioms (2)
  • standard math Standard results on blocks, cut-vertices, and 2-connectivity in graphs
    Invoked to relate 2-connected graphs to their block decompositions and to separate the 2-connected case from the general case.
  • domain assumption The extremal result of Bai et al. (arXiv:2503.03504) for arbitrary graphs
    Combined with the new 2-connected result to obtain the complete general-case characterization.

pith-pipeline@v0.9.1-grok · 5942 in / 1495 out tokens · 39006 ms · 2026-06-28T13:53:24.175246+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references

  1. [1]

    Y. Bai, A. Grzesik, B. Li, and M. Prorok , Cycle lengths in graphs of given minimum degree, arXiv :2511.03085

    arXiv

  2. [2]

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

    arXiv

  3. [3]

    Bollob\' a s , Cycles modulo k , Bull

    B. Bollob\' a s , Cycles modulo k , Bull. London Math. Soc. 9(1) (1977):97--98

    1977

  4. [4]

    Chen and A

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

    1994

  5. [5]

    H. Chu, B. Park, and H. Ryu , On 2 -connected graphs avoiding cycles of length 0 modulo 4 , arXiv :2507.12798

    arXiv

  6. [6]

    C. R. J. Clapham, A. Flockhart, and J. Sheehan , Graphs without four-cycles, J. Graph Theory 13(1) (1989):29--47

    1989

  7. [7]

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

    1991

  8. [8]

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

    1993

  9. [9]

    Erd o s , Some recent problems and results in graph theory, combinatorics, and number theory, In Proc

    P. Erd o s , Some recent problems and results in graph theory, combinatorics, and number theory, In Proc. Seventh SE Conf. Combinatorics, Graph Theory and Computing, Utilitas Math. (1976):3--14

    1976

  10. [10]

    Fan , New sufficient conditions for cycles in graphs, J

    G. Fan , New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37(3) (1984):221--227

    1984

  11. [11]

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

    2022

  12. [12]

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

    2024

  13. [13]

    Gy o ri, B

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

    2026

  14. [14]

    B. Li, Y. Pan, and L. Shi , A note on two cycles of consecutive even lengths in graphs, Discrete Math. 349(3) (2026):114820

    2026

  15. [15]

    Lov\' a sz , On graphs not containing independent circuits, Mat

    L. Lov\' a sz , On graphs not containing independent circuits, Mat. Lapok 16 (1965):289--299

    1965

  16. [16]

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

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

    1992