pith. sign in

arxiv: 2605.02731 · v1 · submitted 2026-05-04 · 🧮 math.CO

Existence of cycles of length divisible by 3 or 4

Ilkyoo Choi , Hojin Chu , Ringi Kim , Boram Park This is my paper

Pith reviewed 2026-05-08 18:10 UTC · model grok-4.3

classification 🧮 math.CO
keywords cycles of divisible lengthminimum degreedegree-2 verticesDean's conjecturegraph characterizationobstruction graphscycle lengths
0
0 comments X

The pith

All graphs with minimum degree 2 and at most three degree-2 vertices that avoid cycles of length divisible by 3 or 4 are fully characterized.

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

The paper strengthens earlier results related to Dean's conjecture on the existence of cycles whose lengths are multiples of a given k. For the cases k=3 and k=4 it gives a complete description of the graphs that meet the minimum-degree-2 condition, have at most three degree-2 vertices, yet contain no cycle whose length is a multiple of k. The description immediately yields two corollaries: every such graph with at most two degree-2 vertices must contain a cycle divisible by 3, and every such graph on at least nine vertices must contain a cycle divisible by 4. A sympathetic reader cares because the characterization replaces an existence statement with an explicit structural list, thereby settling the question for these small k under relaxed degree hypotheses.

Core claim

The authors characterize all graphs G with minimum degree at least 2 and at most three vertices of degree 2 that contain no cycle whose length is divisible by k, for each k in {3,4}. They prove that the only such graphs are certain explicit families, and they derive the two corollaries stated in the abstract as direct consequences of the lists.

What carries the argument

The explicit lists of exceptional graphs (with min-degree 2 and at most three degree-2 vertices) that contain no k-divisible cycle; these lists serve as the complete set of obstructions for k=3 and k=4.

If this is right

  • Every graph with minimum degree at least 2 and at most two degree-2 vertices contains a cycle whose length is divisible by 3.
  • Every graph on at least nine vertices with minimum degree at least 2 and at most three degree-2 vertices contains a cycle whose length is divisible by 4.
  • The known existence results for graphs with minimum degree 2 and at most k-2 degree-2 vertices (k=3,4) are extended by one additional degree-2 vertex, with the new exceptions fully listed.
  • The structural description replaces a pure existence claim with an exhaustive classification of the obstructions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The number of degree-2 vertices appears to be the controlling parameter that determines whether the obstructions can be avoided.
  • Similar exhaustive lists might be feasible for other small values of k once the minimum-degree threshold is lowered.
  • The corollaries suggest that the exceptional families for k=4 are all small, so the existence statement becomes unconditional for large enough order.

Load-bearing premise

That the only graphs satisfying the degree conditions and avoiding the desired cycles are exactly the families listed in the characterization.

What would settle it

A concrete graph with minimum degree at least 2, at most three vertices of degree 2, no cycle whose length is divisible by 3, and not belonging to any of the families described for k=3.

Figures

Figures reproduced from arXiv: 2605.02731 by Boram Park, Hojin Chu, Ilkyoo Choi, Ringi Kim.

Figure 1
Figure 1. Figure 1: Some exceptional graphs with root r Definition 1.6. Let r be a 2-vertex of a graph G. We say G is an exceptional graph with root r if there exists a sequence (G0, x0, y0), . . . ,(Gn, xn, yn) for some nonnegative integer n such that G0 = K2,3, Gn = G, and for each i, the vertices r, xi , and yi are distinct 2-vertices of Gi , and (1) if xiyi ̸∈ E(Gi), then Gi+1 is obtained from Gi by adding a path of lengt… view at source ↗
Figure 2
Figure 2. Figure 2: Graphs without (0 mod 4)-cycles 2 Preliminaries In this section, we introduce notation used throughout the paper and list several facts that will be used in the proofs. Given a walk W, its length, denoted ℓ(W), is the number of edges on W. For a path P : v0v1 . . . vm, let P[vi , vj ] denote the path vivi+1 . . . vj . For a cycle C : v0v1 . . . vmv0, let C[vi , vj ] denote the path vivi+1 . . . vj , where … view at source ↗
Figure 3
Figure 3. Figure 3: Illustrations of P(H; u, v), C(H; u), F(H; u, v). We begin by establishing several structural properties of exceptional graphs. Lemma 3.2. Let G be an exceptional graph with root r and {x, y} = V2(G) \ {r}. Then one of the following holds. (i) x and y are 2-twins, and LG(x, y) ≡ {1, 2} (mod 3). (ii) x and y are adjacent, and LG(x, y) ≡ {0, 1} (mod 3). Moreover, if G ̸= K2,3, then {0, 2} ⊆ LG−y(r, x) (mod 3… view at source ↗
Figure 4
Figure 4. Figure 4: Therefore, {u, v} is a vertex cut of G whose removal leaves at least two nontrivial components, v C1 C2 C3 view at source ↗
read the original abstract

Dean conjectured that for each integer $k \ge 3$, every graph with minimum degree at least $k$ has a cycle whose length is divisible by $k$; this conjecture is known to be true for all $k\neq 5$. For $k\in\{3,4\}$, stronger statements are true: every graph with minimum degree at least $2$ and at most $k-2$ vertices of degree $2$ has a cycle whose length is divisible by $k$. We further strengthen these results by characterizing all graphs with minimum degree at least $2$ and at most three vertices of degree $2$ that have no cycle of length divisible by $k$, for each $k\in\{3,4\}$. As a corollary, we obtain that every graph with minimum degree at least $2$ and at most two vertices of degree $2$ has a cycle whose length is divisible by $3$, and that every graph on at least nine vertices with minimum degree at least $2$ and at most three vertices of degree $2$ has a cycle whose length is divisible by $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

0 major / 3 minor

Summary. The manuscript characterizes all graphs with minimum degree at least 2 and at most three vertices of degree 2 that contain no cycle whose length is divisible by 3 (respectively, by 4). It strengthens prior degree-based existence results for Dean's conjecture in the cases k=3 and k=4, and derives corollaries asserting that every such graph with at most two degree-2 vertices has a 3-divisible cycle, while every such graph on at least nine vertices has a 4-divisible cycle.

Significance. If the stated characterization is complete, the work supplies an explicit, finite list of obstructions under mild degree conditions, furnishing a precise structural understanding of when k-divisible cycles are forced. This is a natural and useful strengthening of known results for small k, and the corollaries follow immediately from the classification. The approach of enumerating exceptions is standard and effective in this area of extremal graph theory.

minor comments (3)
  1. The abstract and corollaries refer to the exceptional graphs without indicating their total number or providing a compact summary table; adding such a table (perhaps in the introduction or a dedicated section) would improve readability and allow quick verification of the finite list.
  2. Illustrations or diagrams of the small exceptional graphs (especially for the k=4 case) would help readers visualize the structures that avoid the desired cycles.
  3. The introduction could include the original citation to Dean's conjecture at the first mention, rather than relying solely on later references.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of its significance as a strengthening of known results for small k, and recommendation of minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes a structural characterization of graphs with minimum degree at least 2 and at most three degree-2 vertices that avoid cycles whose lengths are divisible by 3 or 4. This is done via explicit enumeration of exceptional graphs and case analysis that strengthens prior degree-based results on Dean's conjecture. No equations, fitted parameters, or self-referential definitions appear; the argument does not reduce any claim to its own inputs by construction, and any citations to prior work (including the base statements for k=3,4) serve as external starting points rather than load-bearing self-references that close a loop.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests only on the standard definitions of graphs, minimum degree, and cycle length; no new entities or fitted constants are introduced.

axioms (1)
  • standard math Standard definitions of undirected graphs, vertex degrees, and cycle lengths.
    The entire argument presupposes the usual language of graph theory.

pith-pipeline@v0.9.0 · 5501 in / 1189 out tokens · 46752 ms · 2026-05-08T18:10:04.406956+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

27 extracted references · 27 canonical work pages

  1. [1]

    Allen, P

    P. Allen, P. Keevash, B. Sudakov, and J. Verstra¨ ete. Tur´ an numbers of bipartite graphs plus an odd cycle.J. Combin. Theory Ser. B, 106:134–162, 2014

    work page 2014

  2. [2]

    Bollob´ as

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

    work page 1977

  3. [3]

    J. A. Bondy. Basic graph theory: paths and circuits. InHandbook of combinatorics, Vol. 1, 2, pages 3–110, Elsevier Sci. B. V., Amsterdam, 1995

    work page 1995

  4. [4]

    J. A. Bondy and M. Simonovits. Cycles of even length in graphs.J. Combin. Theory Ser. B, 16:97–105, 1974

    work page 1974

  5. [5]

    Chen and A

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

    work page 1994

  6. [6]

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

    work page arXiv 2025

  7. [7]

    N. Dean. Which graphs are pancyclic modulok? InSixth International Conference on the Theory and Applications of Graphs, pages 315–326, Kalamazoo, Michigan, 1988

    work page 1988

  8. [8]

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

    work page 1993

  9. [9]

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

    work page 2010

  10. [10]

    P. Erd˝ os. Some recent problems and results in graph theory, combinatorics and number theory. In Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Com- puting, Utilitas Math., pages 3–14, Winnipeg, 1976

    work page 1976

  11. [11]

    Erd˝ os and T

    P. Erd˝ os and T. Gallai. On maximal paths and circuits of graphs.Acta Math. Acad. Sci. Hungar., 10:337–356, 1959

    work page 1959

  12. [12]

    Erd˝ os and M

    P. Erd˝ os and M. Simonovits. Compactness results in extremal graph theory.Combinatorica 2(3):275–288, 1982

    work page 1982

  13. [13]

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

    work page 2022

  14. [14]

    Gauthier.The structure of graphs with no cycles of length 0 (mod 3)

    G. Gauthier.The structure of graphs with no cycles of length 0 (mod 3). Ph.D. thesis, Princeton University, 2017

    work page 2017

  15. [15]

    Gy´ arf´ as

    A. Gy´ arf´ as. Graphs withkodd cycle lengths.Discrete Math., 103(1):41–48, 1992

    work page 1992

  16. [16]

    Gy˝ ori, B

    E. Gy˝ ori, 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:7–29, 2026

    work page 2026

  17. [17]

    Liu and J

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

    work page 2018

  18. [18]

    A. V. Kostochka, B. Sudakov, and J. Verstra¨ ete. Cycles in triangle-free graphs of large chromatic number.Combinatorica, 37(3):481–494, 2017. 13

    work page 2017

  19. [19]

    L¨ owenstein, D

    C. L¨ owenstein, D. Rautenbach, and I. Schiermeyer. Cycle length parities and the chromatic number. J. Graph Theory, 64(3):210–218, 2010

    work page 2010

  20. [20]

    Y. Luo, J. Ma, and Z. Zhao. Dean’s conjecture and cycles modulok,arXiv preprint, arXiv:2601.13552, 2026

    work page arXiv 2026

  21. [21]

    O. R. Oellermann. Menger’s theorem. In: L. W. Beineke and R. J. Wilson (Eds).Topics in structural graph theory, pages 13–39, Cambridge Univ. Press, Cambridge, 2013

    work page 2013

  22. [22]

    Sudakov and J

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

    work page 2017

  23. [23]

    Thomassen

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

    work page 1983

  24. [24]

    Thomassen

    C. Thomassen. Paths, circuits and subdivisions. InSelected topics in graph theory, 3, pages 97–131. Academic Press, San Diego, CA, 1988

    work page 1988

  25. [25]

    Thomassen

    C. Thomassen. On the presence of disjoint subgraphs of a specified type.J. Graph Theory, 12(1):101– 111, 1988

    work page 1988

  26. [26]

    Z. Tuza. Problems on cycles and colorings.Discrete Math., 313(19):2007–2013, 2013

    work page 2007

  27. [27]

    Verstra¨ ete

    J. Verstra¨ ete. Extremal problems for cycles in graphs. InRecent trends in combinatorics, pages 83–116, Springer, 2016. 14

    work page 2016