pith. machine review for the scientific record. sign in

arxiv: 2605.11288 · v1 · submitted 2026-05-11 · 🧮 math.CO

Recognition: 3 theorem links

· Lean Theorem

On 2-factors of Hamiltonian graphs

Alberto Espuny D\'iaz, Ant\'onio Gir\~ao, Bertille Granet, Gal Kronenberg

Pith reviewed 2026-05-13 01:39 UTC · model grok-4.3

classification 🧮 math.CO
keywords Hamiltonian graphs2-factorscycle factorsminimum degree conditionsspanning cyclesgraph factors
0
0 comments X

The pith

Large Hamiltonian graphs with minimum degree n to a power slightly less than 1 contain 2-factors made of exactly k cycles.

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

The paper establishes that for any fixed integer k at least 2, there exists a sufficiently small positive epsilon such that every large enough n-vertex Hamiltonian graph whose minimum degree is at least n to the power of 1 minus epsilon has a 2-factor consisting of exactly k cycles. This supplies the first minimum-degree threshold for the property that is smaller than linear in n by a polynomial factor, improving on earlier results that demanded a linear fraction of the vertices in the degree. A sympathetic reader would care because the result shows that graphs much sparser than complete or dense graphs still allow flexible coverings by disjoint cycles that span all vertices. The same methods give an analogous guarantee when the host graph is not Hamiltonian but merely contains some 2-factor with at most k cycles.

Core claim

We show that, for a sufficiently small ε>0, any sufficiently large n-vertex Hamiltonian graph of minimum degree at least n^{1-ε} contains a 2-factor consisting of exactly k cycles. This is the first minimum-degree condition which is polynomially smaller than linear. Our methods yield an analogous result when the host graph is not required to contain a Hamilton cycle, but only a 2-factor consisting of at most k cycles.

What carries the argument

A 2-factor (spanning disjoint union of cycles) whose number of cycles can be adjusted from an initial Hamilton cycle or from an existing low-cycle 2-factor while respecting the minimum-degree lower bound.

Load-bearing premise

The assumption that epsilon is small enough and n is large enough, together with the graph being Hamiltonian or having a 2-factor with at most k cycles.

What would settle it

A Hamiltonian graph on a large n with minimum degree n^{0.9} that contains no 2-factor consisting of exactly three cycles would falsify the claim for that choice of exponent.

Figures

Figures reproduced from arXiv: 2605.11288 by Alberto Espuny D\'iaz, Ant\'onio Gir\~ao, Bertille Granet, Gal Kronenberg.

Figure 1
Figure 1. Figure 1: A Hamilton cycle (full black) with one or two implanted 𝐶4’s (dashed black). Performing 𝐶4 switches gives rise to a new 2-factor (highlighted) consisting of one or two cycles depending on the configuration. Suppose for simplicity that any two vertices have many common neighbours, which implies that any two vertices are contained in many 𝐶4’s. More precisely, we have the following property: if 𝑢𝑣 ∈ 𝐸(𝐺), th… view at source ↗
Figure 2
Figure 2. Figure 2: The cycles 𝐶 and 𝐶 ′ (full black) with three implanted 𝐶4’s (dashed black) corresponding to three disconnected red edges of 𝐻′ (left) or three crossing blue edges of 𝐻′ (right). Performing these 𝐶4-switches gives a 2-factor of 𝐺[𝑉(𝐶) ∪𝑉(𝐶 ′ )] (highlighted) consisting of three cycles. Lastly, if 𝐶 ≠ 𝐶 ′ and the blue subgraph of 𝐻′ has at least |𝑋 ∪ 𝑌| 1+𝜂 edges (see also [PITH_FULL_IMAGE:figures/full_fig_… view at source ↗
read the original abstract

Let $k\geq 2$. We show that, for a sufficiently small $\varepsilon>0$, any sufficiently large $n$-vertex Hamiltonian graph of minimum degree at least $n^{1-\varepsilon}$ contains a $2$-factor consisting of exactly $k$ cycles. This is the first minimum-degree condition which is polynomially smaller than linear. Our methods yield an analogous result when the host graph is not required to contain a Hamilton cycle, but only a $2$-factor consisting of at most $k$ cycles; this answers a question of Buci\'c, Jahn, Pokrovskiy and Sudakov.

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 / 1 minor

Summary. The paper proves that for fixed k ≥ 2 and sufficiently small ε > 0, every sufficiently large n-vertex Hamiltonian graph G with δ(G) ≥ n^{1-ε} contains a 2-factor consisting of exactly k cycles. It also establishes an analogous statement when the host graph is assumed only to contain a 2-factor with at most k cycles (rather than a Hamilton cycle), thereby answering a question of Bucić, Jahn, Pokrovskiy and Sudakov.

Significance. If the proofs are correct, the result is significant: it supplies the first minimum-degree condition that is polynomially sublinear for the existence of exact-k-cycle 2-factors in Hamiltonian graphs, improving on all prior linear-degree thresholds. The second theorem directly resolves the cited open question without additional ad-hoc assumptions.

minor comments (1)
  1. The abstract states the result cleanly but does not indicate the main proof ingredients (e.g., whether the argument proceeds via absorbing paths, regularity lemmas, or iterative cycle merging). Adding one sentence on the method would help readers assess the scope of the techniques.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of our paper and for acknowledging its potential significance in providing the first polynomially sublinear minimum-degree condition for exact-k-cycle 2-factors in Hamiltonian graphs, as well as for resolving the question of Bucić, Jahn, Pokrovskiy and Sudakov. We believe the proofs in the manuscript are correct and complete. As the report lists no specific major comments, we have no revisions or point-by-point responses to provide at this time. We remain available to supply additional details or clarifications on any aspect of the arguments if the referee or editor requests them.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents an asymptotic existence theorem establishing that sufficiently large Hamiltonian n-vertex graphs with minimum degree at least n^{1-ε} (for small ε>0) contain a 2-factor with exactly k cycles, along with a related result for graphs already possessing a 2-factor with at most k cycles. No equations, parameter fittings, self-definitional reductions, or load-bearing self-citations appear in the abstract or description; the central claim is a new combinatorial result that directly addresses an open question posed by external authors (Bucić et al.) without reducing to its own inputs or prior work by the same team. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only abstract available; no explicit axioms, parameters or invented entities can be extracted. The result rests on standard graph-theoretic background assumptions that are not detailed here.

pith-pipeline@v0.9.0 · 5406 in / 1073 out tokens · 26399 ms · 2026-05-13T01:39:05.082884+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    P. K. Agarwal, B. Aronov, J. Pach, R. Pollack and M. Sharir, Quasi-planar graphs have a linear number of edges.Combinatorica17.1 (1997), 1–9,doi:10.1007/BF01196127

    work page doi:10.1007/bf01196127 1997

  2. [2]

    Aigner and S

    M. Aigner and S. Brandt, Embedding arbitrary graphs of maximum degree two.J. Lond. Math. Soc., II. Ser.48.1 (1993), 39–51,doi:10.1112/jlms/s2-48.1.39

    work page doi:10.1112/jlms/s2-48.1.39 1993

  3. [3]

    N. Alon, M. Krivelevich and B. Sudakov, Turán numbers of bipartite graphs and related Ramsey-type questions.Comb. Probab. Comput.12.5-6 (2003), 477–494,doi: 10.1017/ S0963548303005741

    work page 2003

  4. [4]

    Brandt, G

    S. Brandt, G. Chen, R. Faudree, R. J. Gould and L. Lesniak, Degree conditions for 2-factors. J. Graph Theory24.2 (1997), 165–173,doi: 10.1002/(SICI)1097-0118(199702)24:2<165:: AID-JGT4>3.0.CO;2-O

    work page doi:10.1002/(sici)1097-0118(199702)24:2 1997

  5. [5]

    Bucić, E

    M. Bucić, E. Jahn, A. Pokrovskiy and B. Sudakov, 2-factors with 𝑘 cycles in Hamiltonian graphs. J. Comb. Theory, Ser. B144 (2020), 150–166,doi:10.1016/j.jctb.2020.02.002

    work page doi:10.1016/j.jctb.2020.02.002 2020

  6. [6]

    G. Chen, J. R. Faudree, R. J. Gould and A. Saito, 2-factors in claw-free graphs.Discuss. Math., Graph Theory20.2 (2000), 165–172,doi:10.7151/dmgt.1116

    work page doi:10.7151/dmgt.1116 2000

  7. [7]

    Chiba, On degree sum conditions for 2-factors with a prescribed number of cycles.Discrete Math.341.10 (2018), 2912–2918,doi:10.1016/j.disc.2018.06.045

    S. Chiba, On degree sum conditions for 2-factors with a prescribed number of cycles.Discrete Math.341.10 (2018), 2912–2918,doi:10.1016/j.disc.2018.06.045

    work page doi:10.1016/j.disc.2018.06.045 2018

  8. [8]

    Chiba, S

    S. Chiba, S. Jiang and J. Yan, Partitioning a graph into cycles with a specified number of chords. J. Graph Theory94.3 (2020), 463–475,doi:10.1002/jgt.22534

    work page doi:10.1002/jgt.22534 2020

  9. [9]

    Chiba and K

    S. Chiba and K. Yoshida, On partitioning a bipartite graph into a specified number of cycles and degree sum conditions for two vertices of distance three.Discrete Math.349.8 (2026), Id/No 115 075, 14 pages,doi:https://doi.org/10.1016/j.disc.2026.115075

    work page doi:10.1016/j.disc.2026.115075 2026

  10. [10]

    Corrádi and A

    K. Corrádi and A. Hajnal, On the maximal number of independent circuits in a graph.Acta Math. Acad. Sci. Hung.14 (1963), 423–439,doi:10.1007/BF01895727

    work page doi:10.1007/bf01895727 1963

  11. [11]

    DeBiasio, M

    L. DeBiasio, M. Ferrara and T. Morris, Improved degree conditions for 2-factors with 𝑘 cycles in Hamiltonian graphs.Discrete Math.320 (2014), 51–54,doi:10.1016/j.disc.2013.12.005

    work page doi:10.1016/j.disc.2013.12.005 2014

  12. [12]

    G. A. Dirac, Some theorems on abstract graphs.Proc. London Math. Soc. (3)2 (1952), 69–81, doi:10.1112/plms/s3-2.1.69

    work page doi:10.1112/plms/s3-2.1.69 1952

  13. [13]

    M. H. El-Zahar, On circuits in graphs.Discrete Math.50 (1984), 227–230,doi: 10.1016/ 0012-365X(84)90050-5

    work page 1984

  14. [14]

    R. J. Faudree, R. J. Gould, M. S. Jacobson, L. Lesniak and A. Saito, Toughness, degrees and 2-factors.Discrete Math.286.3 (2004), 245–249,doi:10.1016/j.disc.2004.05.008

    work page doi:10.1016/j.disc.2004.05.008 2004

  15. [15]

    ———, A note on 2-factors with two components.Discrete Math.300.1-3 (2005), 218–224,doi: 10.1016/j.disc.2005.06.005

    work page doi:10.1016/j.disc.2005.06.005 2005

  16. [16]

    M. R. Garey and D. S. Johnson,Computers and intractability. A Series of Books in the Mathem- atical Sciences, W . H. Freeman and Co., San Francisco, CA (1979), ISBN 0-7167-1045-5

    work page 1979

  17. [17]

    Goddard, M

    W . Goddard, M. Katchalski and D. J. Kleitman, Forcing disjoint segments in the plane.Eur. J. Comb.17.4 (1996), 391–395,doi:10.1006/eujc.1996.0032

    work page doi:10.1006/eujc.1996.0032 1996

  18. [18]

    Janson, T

    S. Janson, T. Łuczak and A. Ruciński,Random graphs. Wiley-Interscience Series in Dis- crete Mathematics and Optimization, Wiley-Interscience, New York (2000),doi: 10.1002/ 9781118032718. ON2-FACTORS OF HAMILTONIAN GRAPHS 17

    work page 2000

  19. [19]

    R. M. Karp,Reducibility among combinatorial problems, 85–103. Springer US, ISBN 978-1-4684- 2001-2 (1972),doi:10.1007/978-1-4684-2001-2_9

    work page doi:10.1007/978-1-4684-2001-2_9 2001

  20. [20]

    Pfender, 2-factors in Hamiltonian graphs.Ars Comb.72 (2004), 287–293

    F. Pfender, 2-factors in Hamiltonian graphs.Ars Comb.72 (2004), 287–293

    work page 2004

  21. [21]

    G. N. Sárközy, On 2-factors with 𝑘 components.Discrete Math.308.10 (2008), 1962–1972,doi: 10.1016/j.disc.2007.04.049

    work page doi:10.1016/j.disc.2007.04.049 2008

  22. [22]

    A. G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs. B. Bollobás (ed.), Advances in Graph Theory,Annals of Discrete Mathematics, vol. 3, 259–268, Elsevier (1978),doi: 10.1016/S0167-5060(08)70511-9

    work page doi:10.1016/s0167-5060(08)70511-9 1978

  23. [23]

    Thomassen, Chords of longest cycles in cubic graphs.J

    C. Thomassen, Chords of longest cycles in cubic graphs.J. Comb. Theory, Ser. B71.2 (1997), 211–214,doi:10.1006/jctb.1997.1776

    work page doi:10.1006/jctb.1997.1776 1997

  24. [24]

    Wang, Proof of the Erdős-Faudree conjecture on quadrilaterals.Graphs Comb.26.6 (2010), 833–877,doi:10.1007/s00373-010-0948-3

    H. Wang, Proof of the Erdős-Faudree conjecture on quadrilaterals.Graphs Comb.26.6 (2010), 833–877,doi:10.1007/s00373-010-0948-3

    work page doi:10.1007/s00373-010-0948-3 2010

  25. [25]

    Zhang and J

    J. Zhang and J. Yan, Disjoint cycles and2-factors with Fan-type condition in a graph.Discrete Math.345.4 (2022), Id/No 112 789, 11 pages,doi:10.1016/j.disc.2021.112789

    work page doi:10.1016/j.disc.2021.112789 2022