Hamilton cycles in regular graphs perturbed by a random 2-factor

Cicely (Cece) Henderson; Dingjia Mao; Patryk Morawski; Sean Longbrake

REVIEW 2 major objections 5 minor 26 references

Hamilton cycles in regular graphs perturbed by a random 2-factor

T0 review · 2 major / 5 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 The paper proves that for every integer $d \geq 2$, the union of any $n$-vertex $d$-regular graph with a uniformly random 2-factor is Hamiltonian with high probability, resolving a conjecture from [10].

desk verdict Resolves a real open conjecture with a sound but dense proof; needs a careful revision to fix a typo and to make Claim 3.4 rigorous. read the letter →

arxiv 2506.21756 v2 pith:B7J7P2PC submitted 2025-06-26 math.CO

Cicely (Cece) Henderson , Sean Longbrake , Dingjia Mao , Patryk Morawski This is my paper · ORCID

classification math.CO MSC 05C4505C80

keywords Hamiltoncyclesrandomlyperturbedgraphsrandom2-factorregularextension-closurealgorithmsecondmomentmethodnear-2-factorhighprobability

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 proves a positive answer to a conjecture from [10]: for every fixed $d \geq 2$, if $G$ is any $n$-vertex $d$-regular graph and $F$ is a uniformly random 2-factor on the same vertex set, then $G \cup F$ contains a Hamilton cycle with probability tending to 1. The point is that a completely arbitrary, possibly far-from-Hamiltonian regular graph is made Hamiltonian by adding only a very sparse and rigid random structure, namely a disjoint union of random cycles covering all vertices. This sits between dense deterministic sufficient conditions and results on purely random regular graphs, and it shows a universality property: the deterministic graph contributes almost nothing beyond its degree bound. The proof first uses an extension-closure algorithm to eliminate all short cycles of $F$, then uses the second moment method to merge the surviving long cycles into one Hamilton cycle.

What carries the argument

Phase I's engine is the extension-closure algorithm introduced in [6], adapted to near-2-factors: a spanning graph that is a disjoint union of cycles and exactly one path. An acceptable rotation at a path endpoint $v$ replaces an edge $\{w,x\}$ of $F$ by $\{v,w\}$, provided the new path and any newly created cycle remain longer than $n_0 = 100n/\log n$. The Traverse subprocedure exposes the preimage in $G$ of a path endpoint and the images of two of its neighbours in $G$, producing up to four candidate child endpoints; the proof shows each call succeeds with probability at least $1 - 1000/\log n$, so the number of paths follows the branching recurrence $S_{t+1} \approx 3.99 S_t$ of Lemma 2.3 and reaches $\sqrt{n}\log^4 n$ paths while exposing only $O(n^{3/5})$ vertices. A standard edge-colouring result (every graph of maximum degree $\Delta$ can be edge-coloured with $\Delta + 1$ colours) reduces an arbitrary $d$-regular $G$ to a spanning subgraph with all degrees between 2 and 3, and Lemma 2.5 supplies the edge that closes two collections of paths into one long cycle. Phase II's machinery is a second moment count over Hamilton cycles formed by deleting $m \approx 0.1 \log n$ edges from the long cycles and rejoining the resulting paths with random edges of $G$, with the bound from [13] on the admissible rejoining permutations controlling dependence between candidate cycles.

What would settle it

Run the Traverse procedure on a concrete family of $d$-regular graphs and record, for each call, whether all four candidate child endpoints are acceptable and avoid the set of previously exposed vertices; if the empirical success rate ever falls below $1 - 1000/\log n$ for a positive fraction of calls, the recurrence $S_{t+1} \approx 3.99 S_t$ breaks and Phase I cannot deliver its $\sqrt{n}\log^4 n$ paths. Equivalently, an explicit family for which every Hamilton cycle of $G \cup F$ provably requires exposing more than $O(n^{3/4})$ vertices would refute Theorem 1.2.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.2: for every fixed integer $d \geq 2$, if $G$ is any $n$-vertex $d$-regular graph and $F$ is a uniformly random 2-factor on the same vertex set, then $G \cup F$ is Hamiltonian with probability tending to 1 as $n \to \infty$. This resolves Conjecture 1.1 from [10] for all $d \geq 2$; the $d = 1$ case was already known by contiguity of the union to a random 3-regular graph. The proof is a two-phase argument. Phase I runs an extension-closure algorithm: starting from a short cycle of $F$, it grows a large collection of long paths by acceptable rotations, uses a connecting-edge lemma to close one of them into a long cycle, and iterates until every cycle has length at least $n_0 = 100n/\log n$, while exposing only $O(n^{3/4})$ vertices of the random bijection. Phase II then shows, by a second moment calculation over candidate Hamilton cycles built from $O(\log n)$ deleted edges of the long cycles, that at least one such cycle survives with high probability.

Load-bearing premise

The argument stands or falls on the claim that, even after conditioning on the $O(n^{3/5})$ vertices exposed earlier, each call of the path-growing procedure still succeeds with probability at least $1 - 1000/\log n$; if earlier exposures depress that success probability, the branching recurrence $S_{t+1} \approx 3.99 S_t$ fails and Phase I cannot grow the required $\sqrt{n}\log^4 n$ long paths.

Editorial extensions

If this is right

For every fixed $d \geq 2$, every $n$-vertex $d$-regular graph, however non-Hamiltonian, becomes Hamiltonian after adding one uniformly random 2-factor, with probability tending to 1.
Because the proof first reduces the graph to a spanning subgraph with minimum degree 2 and maximum degree 3, the conclusion applies to any graph that contains such a subgraph, not only to regular graphs.
The construction exposes only $O(n^{3/4})$ vertices of the random bijection and uses $O(\log n)$ random edges in the final merging step, so most of the perturbation's randomness is not needed.
With the $d = 1$ case already known by contiguity to random 3-regular graphs, the full conjecture from [10] is now resolved.

Reading between the lines

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

A direct stress test suggested by the proof is to condition the random 2-factor on having exactly $\Theta(\log n)$ cycles, all of length $\Omega(n/\log n)$; since the structural lemma from [10] is the only input about the structure of $F$, the argument should survive with the random bijection supplying the remaining randomness.
The concluding remarks conjecture that the same proof adapts to almost regular graphs with minimum degree at least 2 and maximum degree $o(\delta(G) \log n)$; if that holds, the result stops being about exact regularity and becomes a statement about graphs with a controlled degree range.
The use of even permutations in the admissible rejoining set suggests a parity-based cancellation in the second moment; one could ask whether the same counting yields many edge-disjoint Hamilton cycles in $G \cup F$ rather than just one.

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.

Desk Editor's Note

read the letter

Net: this is a serious paper that proves a genuine theorem. The result is exactly what it claims: for every fixed d ≥ 2, adding a uniformly random 2-factor to an n-vertex d-regular graph gives a Hamiltonian graph w.h.p. The constant-degree regime was previously open, so this is a real advance, not a routine extension. The proof architecture is sound — Cooper–Frieze extension-closure for Phase I, second moment for Phase II, with a Vizing reduction to keep degrees in {2,3}. The exposition is mostly careful and the phase separation is clean.

The main soft spot is the one the reader flagged: Claim 3.4 asserts a history-independent success probability for the rotations but does not fully justify it. The stress-test note convinced me this is fixable rather than fatal: the dangerous set on the current path has size O(n/log n), so a fresh rotation hits it with probability O(1/log n), and a union bound over previously exposed vertices gives the same constant. Still, the proof as written skips this conditioning argument, and I would want that formalized before calling the paper complete.

There is also a concrete typo in the proof of Lemma 3.6: the second run of Lemma 3.2 is written with v=v0, but it needs v=u0 to reach paths with endpoint u_L' and close the cycle. As written, property (T2) does not apply to any L' in L2. It is a one-character error and the intended meaning is clear from the surrounding text, but it should be corrected. Minor: Claim 3.4 says "all six" near-2-factors where the algorithm only produces four rotations; the recurrence itself uses four, so the statement is just imprecise.

Bottom line: the theorem is likely true, the architecture is coherent, and the remaining issues are a typo plus one claim that needs more rigour. I would send this to a good referee and expect acceptance after a careful revision.

Referee Report

2 major / 5 minor

Summary. The paper proves that for every integer d ≥ 2, the union of an arbitrary n-vertex d-regular graph G with a uniformly random 2-factor F on the same vertex set is Hamiltonian with high probability. This confirms Conjecture 6.2 of Draganić and Keevash, who had earlier resolved the case d = ω(log^3 n). The proof adapts the Cooper–Frieze extension-closure algorithm to first convert F, with high probability, into a 2-factor whose cycles are all long, while exposing only O(n^{3/4}) vertices of the random bijection π; then a second-moment argument shows that the remaining randomness of π can be used to connect these long cycles into a Hamilton cycle. The main technical engine is a paths-exploration lemma (Lemma 3.2) that grows many long acceptable paths from a fixed endpoint with a controlled exposure budget, together with a Vizing-theorem reduction from d-regular graphs to subgraphs of degree 2 or 3.

Significance. If the proof is correct, this is a clean and complete resolution of a conjecture that had attracted recent attention. The result is striking: every bounded-degree regular graph becomes Hamiltonian after a single random 2-factor is added. The proof is substantial but rests on standard tools—Vizing's theorem, Chernoff bounds, Pósa rotations, and the second moment method—and the exposure budget is carefully managed. The manuscript is generally well structured and presents the main ideas clearly. I regard the central theorem and proof strategy as very likely correct, provided the specific gaps identified below are addressed.

major comments (2)

[Section 3.2, proof of Lemma 3.6] In the paragraph beginning 'Finally, we let X'...' the second application of Lemma 3.2 is stated with v = v0. This is inconsistent with the stated goal of obtaining near-2-factors with P(L'') ∈ P(v_{L'}, u_{L'}). In property (T2) of Lemma 3.2, the first endpoint of the output path is the fixed endpoint u of the input path, while the parameter v is the endpoint from which the exploration starts. To obtain P(L'') ∈ P(v_{L'}, u_{L'}), one must apply Lemma 3.2 with v = u0, reading the input path P(L') ∈ P(u0, v_{L'}) as P(v_{L'}, u0). As written, neither endpoint of P(L') equals v0 in general, so the conclusion does not follow. The intended correction is a one-character swap, and the exposure budget is unchanged, but the current text is a genuine defect in the proof of this load-bearing step.
[Section 3.1, Claim 3.4] The claim that each execution of steps 8-10 in Algorithm 3 succeeds with probability at least 1 - 1000/log n 'independent of the history' is not rigorously established, and the subsequent stochastic domination of I by Bin(|L_{t-1}|, 1000/log n) is asserted without proof. The underlying size bound is sound—the unacceptable choices of x are contained in the two intervals of length n0 at the ends of the current path P(L), so the probability that a uniformly random exposed neighbor falls in the dangerous set is O(n0/n) = O(1/log n)—but the conditional probability step and the stochastic-domination argument should be formalized. Since Lemma 2.3 and the lower bound on |L_{tmax}| depend on this domination, this is a load-bearing point that needs a brief rigorous treatment, for example by stating a standard lemma for sums of conditionally Bernoulli random variables.

minor comments (5)

[Algorithm 1, line 6] The text says 'We expose w(j) = π(w(j)G) for each j ∈ [3]' but only two vertices w(1), w(2) are defined; the index should be [2].
[Section 3.1, Claim 3.4] The phrase 'we add all six near-2-factors Lj,k to Lt' is inconsistent with the definition, which produces four rotations (j ∈ [2], k ∈ [2]); it should read 'all four'.
[Section 2, Lemma 2.3 and throughout] The notation 'log4 n' is ambiguous: it should be $\log_4 n$ for the parameter tmax and $\log^4 n$ for powers of the natural logarithm, to avoid confusion in the growth analysis.
[Section 3.2, proof of Lemma 3.6] In the second application of Lemma 3.2, the expression 'X = (Xt−1 \ {u0, v0})' contains a stray parenthesis; the intended set is X_{t-1} \ {u0, v0}.
[Section 3.2, proof of Lemma 3.6] The reduction by Vizing's theorem states that taking 'exactly three' of the matchings gives a subgraph with 2 ≤ δ ≤ Δ ≤ 3. This is true because each vertex misses at most one colour, but the one-sentence justification could be made explicit for the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is a self-contained probabilistic construction with no fitted quantity renamed as a prediction.

full rationale

The derivation does not assume Theorem 1.2. The Phase I extension-closure algorithm (Lemma 3.2) is analyzed directly: Traverse exposes uniformly random vertices, rejection probabilities are bounded by sizes of forbidden sets, and growth of the path collection is stochastically dominated by the recurrence in Lemma 2.3; no parameter is fitted to Hamiltonicity data. The short-cycle elimination lemma uses the external Lemma 3.5 of Draganić-Keevash only for the structure of the random 2-factor, not for the Hamiltonian union, and Vizing's theorem and Frieze's lemma are cited standard external results. Phase II defines explicit Hamilton cycles via matchings and deleted edges, then computes E[H] and E[H^2] with Lemma 2.1; the second-moment ratio is shown to be 1+o(1), so H>0 w.h.p. is a derived probabilistic statement, not an input. The flagged issue in Section 3.2 (second invocation of Lemma 3.2 written with v=v0 instead of the endpoint needed for the closing paths) is an internal notational or consistency issue in the proof, not a circular step: it does not make any prediction equal to a fitted input or define a quantity in terms of the conclusion. Accordingly, no circular step is present.

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

The proof depends on a handful of chosen thresholds (n0, tmax, a) and on three external results: Vizing's theorem, the structure of random 2-factors, and Frieze's cyclic permutation lemma. No new entities are postulated. The constants are not fitted to data and any sufficiently large multiple would likely work, but they are hand-chosen to make the estimates close.

free parameters (3)

n0 = 100n/log n
Threshold separating short from long cycles in Lemma 3.2 and Lemma 3.6; chosen so that the number of short cycles is O(log n) and the probability of a random vertex falling near a path endpoint is O(1/log n).
tmax = (3/5) log^4 n
Number of iterations in the extension-closure tree-growing process; chosen so that the branching factor 3.99 gives a set of size at least √n log^4 n.
a and m_i = a = n/log n, m_i = 2⌊c_i/(20a)⌋+1
Phase II parameters that set the number of reconnection edges m = Θ(log n); this scaling makes the second moment calculation cancel to 1+o(1).

assumptions (4)

standard math Vizing's theorem: every graph with maximum degree Δ can be edge-colored with Δ+1 colors
Used in Lemma 3.6 to reduce a d-regular graph to a spanning subgraph with 2 ≤ δ ≤ Δ ≤ 3.
domain assumption Lemma 3.5 (Draganić-Keevash): a uniformly random 2-factor has O(log n) cycles, O(log log n) cycles of length 3, and at least one linear-length cycle w.h.p.
Controls the number of short cycles and provides the long cycle needed in the L2 step of Lemma 3.6.
domain assumption Lemma 3 in [13] (Frieze): the number of cyclic permutations R_M with φ_M composed remaining cyclic satisfies (m-2)! ≤ |R_M| ≤ (m-1)!
Bounds the number of candidate Hamilton cycles in the Phase II count.
standard math Standard Chernoff and binomial tail bounds (Lemma 2.2)
Used throughout for concentration in the tree process and second moment.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Hamilton cycles in regular graphs perturbed by a random 2-factor." pith.science (2026). https://pith.science/paper/B7J7P2PC

@misc{pith2026250621756,
  author       = {Pith},
  title        = {Pith review of: Hamilton cycles in regular graphs perturbed by a random 2-factor},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/B7J7P2PC}},
  note         = {Machine review of arXiv:2506.21756}
}

abstract

In this paper, we prove that for each $d \geq 2$, the union of a $d$-regular graph with a uniformly random $2$-factor on the same vertex set is Hamiltonian with high probability. This resolves a conjecture by Dragani\'c and Keevash for all values of $d$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 22 canonical work pages

[1]

Alon and J

N. Alon and J. H. Spencer. The probabilistic method. John Wiley & Sons, 2016

work page 2016
[2]

Bohman, A

T. Bohman, A. Frieze, and R. Martin. How many random edges make a dense graph Hamiltonian? Random Structures & Algorithms , 22(1):33–42, 2003

work page 2003
[3]

B¨ ottcher, R

J. B¨ ottcher, R. Montgomery, O. Parczyk, and Y. Person. Embedding spanning bounded degree graphs in randomly perturbed graphs. Mathematika, 66(2):422–447, 2020

work page 2020
[4]

Chv´ atal and P

V. Chv´ atal and P. Erd¨ os. A note on Hamiltonian circuits.Discret. Math., 2(2):111–113, 1972

work page 1972
[5]

C. Cooper. 1-pancyclic Hamilton cycles in random graphs. Random Structures & Algo- rithms, 3(3):277–287, 1992

work page 1992
[6]

Cooper and A

C. Cooper and A. Frieze. Hamilton cycles in a class of random directed graphs. J. Comb. Theory, Ser. B , 62(1):151–163, 1994

work page 1994
[7]

Cooper, A

C. Cooper, A. Frieze, and M. Molloy. Hamilton cycles in random regular digraphs. Com- binatorics, Probability and Computing , 3(1):39–49, 1994

work page 1994
[8]

Cooper, A

C. Cooper, A. Frieze, and B. Reed. Random regular graphs of non-constant degree: con- nectivity and Hamiltonicity. Combinatorics, Probability and Computing , 11(3):249–261, 2002

work page 2002

Show all 26 references

[9]

G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 3(2):69–81, 1952

1952
[10]

Dragani´ c and P

N. Dragani´ c and P. Keevash. P´ osa rotation through a random permutation.arXiv preprint arXiv:2502.00489, 2025

2025 arXiv
[11]

Dragani´ c, R

N. Dragani´ c, R. Montgomery, D. M. Correia, A. Pokrovskiy, and B. Sudakov. Hamiltonicity of expanders: optimal bounds and applications. arXiv preprint arXiv:2402.06603 , 2024

2024 arXiv
[12]

Espuny D ´ ıaz and A

A. Espuny D ´ ıaz and A. Gir˜ ao. Hamiltonicity of graphs perturbed by a random regular graph. Random structures & algorithms , 62(4):857–886, 2023

2023
[13]

A. Frieze. Hamilton cycles in the union of random permutations. Random Structures & Algorithms, 18(1):83–94, 2001

2001
[14]

A. Frieze. Hamilton cycles in random graphs: a bibliography. arXiv preprint arXiv:1901.07139, 2019

1901 arXiv
[15]

Frieze, R

A. Frieze, R. M. Karp, and B. Reed. When is the assignment bound tight for the asym- metric traveling-salesman problem? SIAM Journal on Computing , 24(3):484–493, 1995

1995
[16]

Janson, T

S. Janson, T. Luczak, and A. Rucinski. Random graphs. John Wiley & Sons, 2011

2011
[17]

Joos and J

F. Joos and J. Kim. Spanning trees in randomly perturbed graphs. Random Structures & Algorithms, 56(1):169–219, 2020. 16

2020
[18]

R. M. Karp. Reducibility among Combinatorial Problems , pages 85–103. Springer US, Boston, MA, 1972

1972
[19]

F. Knox, D. K¨ uhn, and D. Osthus. Edge-disjoint Hamilton cycles in random graphs. Random Structures & Algorithms , 46(3):397–445, 2015

2015
[20]

A. D. Korshunov. Solution of a problem of Erd˝ os and Renyi on Hamiltonian cycles in nonoriented graphs. In Doklady Akademii Nauk , volume 228, pages 529–532. Russian Academy of Sciences, 1976

1976
[21]

Krivelevich, M

M. Krivelevich, M. Kwan, and B. Sudakov. Bounded-degree spanning trees in randomly perturbed graphs. SIAM Journal on Discrete Mathematics , 31(1):155–171, 2017

2017
[22]

Krivelevich, B

M. Krivelevich, B. Sudakov, V. H. Vu, and N. C. Wormald. Random regular graphs of high degree. Random Structures & Algorithms , 18(4):346–363, 2001

2001
[23]

K¨ uhn and D

D. K¨ uhn and D. Osthus. A survey on Hamilton cycles in directed graphs.European Journal of Combinatorics , 33(5):750–766, 2012

2012
[24]

K¨ uhn and D

D. K¨ uhn and D. Osthus. Hamilton cycles in graphs and hypergraphs: an extremal per- spective. arXiv preprint arXiv:1402.4268 , 2014

2014 arXiv
[25]

L. P´ osa. Hamiltonian circuits in random graphs. Discrete Mathematics , 14(4):359–364, 1976

1976
[26]

V. G. Vizing. On an estimate of the chromatic class of a p-graph. Diskret analiz, 3:25–30, 1964. 17

1964

Pith tools

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

[1] [1]

Alon and J

N. Alon and J. H. Spencer. The probabilistic method. John Wiley & Sons, 2016

work page 2016

[2] [2]

Bohman, A

T. Bohman, A. Frieze, and R. Martin. How many random edges make a dense graph Hamiltonian? Random Structures & Algorithms , 22(1):33–42, 2003

work page 2003

[3] [3]

B¨ ottcher, R

J. B¨ ottcher, R. Montgomery, O. Parczyk, and Y. Person. Embedding spanning bounded degree graphs in randomly perturbed graphs. Mathematika, 66(2):422–447, 2020

work page 2020

[4] [4]

Chv´ atal and P

V. Chv´ atal and P. Erd¨ os. A note on Hamiltonian circuits.Discret. Math., 2(2):111–113, 1972

work page 1972

[5] [5]

C. Cooper. 1-pancyclic Hamilton cycles in random graphs. Random Structures & Algo- rithms, 3(3):277–287, 1992

work page 1992

[6] [6]

Cooper and A

C. Cooper and A. Frieze. Hamilton cycles in a class of random directed graphs. J. Comb. Theory, Ser. B , 62(1):151–163, 1994

work page 1994

[7] [7]

Cooper, A

C. Cooper, A. Frieze, and M. Molloy. Hamilton cycles in random regular digraphs. Com- binatorics, Probability and Computing , 3(1):39–49, 1994

work page 1994

[8] [8]

Cooper, A

C. Cooper, A. Frieze, and B. Reed. Random regular graphs of non-constant degree: con- nectivity and Hamiltonicity. Combinatorics, Probability and Computing , 11(3):249–261, 2002

work page 2002