{"id":"ccda5549-aa62-496a-9e50-671dda9958ac","arxiv_id":"2506.21756","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For every integer d ≥ 2, the union of any d-regular graph on n vertices with a uniformly random 2-factor is Hamiltonian with high probability.","lead":"This paper proves that adding a single random 2-factor to any d-regular graph makes it Hamiltonian with probability tending to one, for every d at least 2. The result settles a conjecture by Draganić and Keevash about randomly perturbed regular graphs.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"In §3.2, the second call to Lemma 3.2 is written with v=v0, but the desired paths P(L'')∈P(v_L',u_L') require v=u0; the written step is inconsistent, though the intended argument is clear.","rationale":"The paper gives a plausible proof of the Draganić–Keevash conjecture, and the major probabilistic machinery in Lemma 3.2 and the second-moment calculation in Section 4 are coherent. The reader's weakest assumption—independence of the Traverse success events in Claim 3.4—is a reasonable place to demand rigor, but the proof sketch supplies the needed uniform conditional bound: the set of vertices on the current path within n0 of either endpoint has size at most 2n0, so the probability that a uniformly random neighbor image lands there is at most 200/log n; all other failure sources have probability o(1/log n). Hence the stochastic domination by Bin(|L_{t-1}|,1000/log n) is valid, and Lemma 2.3 applies. The genuinely load-bearing written defect is the endpoint error in the second tree-growing call in §3.2. This does not undermine the central claim once corrected, but a careful reader cannot verify the short-cycle elimination step from the text as it stands. Since the fix is minor and the proof structure remains sound, the conditional verdict is unchanged.","tokens_in":16460,"tokens_out":48999,"duration_ms":531598,"concrete_test":"Re-derive the second application of Lemma 3.2 in Lemma 3.6 with v=u0 instead of v=v0, and check that property (T2) then applies to each L'∈L2, producing paths P(L'')∈P(v_L',u_L') with u_L'∈S and |B3|=O(n^{3/5}). If the derivation goes through with this swap, the only required revision is the corrected endpoint.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The single most concrete defect is in the proof of Lemma 3.6. After the first application of Lemma 3.2 with v=v0, each L'∈L2 has path P(L')∈P(u0,v_L'). To obtain a near-2-factor L'' with P(L'')∈P(v_L',u_L'), Lemma 3.2 must be invoked with fixed endpoint v=u0, so that, after reversing the orientation, L' satisfies P(L')∈P(v_L',u0) and the algorithm extends from u0 to new endpoints u_L'. The manuscript instead says the second run uses v=v0; with that parameter, property (T2) of Lemma 3.2 does not apply to any L'∈L2 because neither endpoint of P(L') equals v0 in general. Thus the construction of the paths needed for the final closing step does not follow as written. The fix is a one-character swap, and the exposure budget is unchanged since the second run still exposes O(n^{3/5}) vertices. The reader's independence concern in Claim 3.4 is less serious: conditional on any history, the dangerous set on the current path has size at most 2n0, so each of the two exposed neighbors hits it with probability ≤200/log n, and the total failure probability is uniformly ≤1000/log n; this supports the stochastic domination by Bin(|L_{t-1}|,1000/log n), though the claim should be formalized.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16817,"tokens_out":38161,"duration_ms":424851,"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":[{"comment":"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":"Section 3.2, proof of Lemma 3.6"},{"comment":"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.","section":"Section 3.1, Claim 3.4"}],"minor_comments":[{"comment":"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":"Algorithm 1, line 6"},{"comment":"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":"Section 3.1, Claim 3.4"},{"comment":"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":"Section 2, Lemma 2.3 and throughout"},{"comment":"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":"Section 3.2, proof of Lemma 3.6"},{"comment":"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.","section":"Section 3.2, proof of Lemma 3.6"}],"recommendation":"major_revision","confidential_remarks":"The paper resolves a well-known conjecture and is likely correct after the fixes above. The v0/u0 slip is clearly typographical, and Claim 3.4 can be repaired without changing the proof structure. I would be happy to review a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThere 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.\n\nBottom 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.","headline":"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.","tokens_in":17341,"tokens_out":1975,"would_cite":true,"duration_ms":21557,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C45","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"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].","keywords":["Hamilton cycles","randomly perturbed graphs","random 2-factor","regular graphs","extension-closure algorithm","second moment method","near-2-factor","high probability"],"falsifier":"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.","tokens_in":16313,"feed_emoji":"🎲","tokens_out":18817,"duration_ms":169922,"temperature":0.7,"pith_summary":"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.","feed_headline":"One random 2-factor forces a Hamilton cycle in every regular graph","feed_subtitle":"For any d-regular graph with d ≥ 2, adding a uniformly random 2-factor yields a Hamilton cycle with high probability.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the conjecture being resolved and the structural lemma on a random 2-factor's cycle count, which initializes Phase I.","marker":"[10]"},{"why":"Introduces the extension-closure algorithm whose Traverse procedure and acceptable-rotation arguments Phase I adapts.","marker":"[6]"},{"why":"Gives the edge-colouring theorem used to reduce an arbitrary d-regular graph to a spanning subgraph with degrees between 2 and 3.","marker":"[26]"},{"why":"Provides the bound on the number of admissible rejoining permutations that controls dependence in the Phase II second moment estimate.","marker":"[13]"},{"why":"Used for the d = 1 case, where contiguity to a random 3-regular graph gives Hamiltonicity and completes the conjecture.","marker":"[16]"}],"fun_headline_variants":["Random 2-factor guarantees Hamilton cycle in any regular graph","Adding a random 2-factor makes every regular graph Hamiltonian","Conjecture resolved: random 2-factor yields Hamilton cycle in regular graphs","For all d≥2, regular graph plus random 2-factor is Hamiltonian"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Random 2-factor guarantees Hamilton cycle in any regular graph","Adding a random 2-factor makes every regular graph Hamiltonian","Conjecture resolved: random 2-factor yields Hamilton cycle in regular graphs","For all d≥2, regular graph plus random 2-factor is Hamiltonian"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000908,"raw_usage":{"total_tokens":3851,"prompt_tokens":843,"completion_tokens":3008,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":459,"completion_tokens_details":{"reasoning_tokens":2933}},"tokens_in":459,"tokens_out":3008,"duration_ms":22521,"temperature":1.0,"reasoning_tokens":2933,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:20:19.253206+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Cooper and A","cited_arxiv_id":null,"evidence_quote":"Introduces the extension-closure algorithm whose Traverse procedure and acceptable-rotation arguments Phase I adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the edge-colouring theorem used to reduce an arbitrary d-regular graph to a spanning subgraph with degrees between 2 and 3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the bound on the number of admissible rejoining permutations that controls dependence in the Phase II second moment estimate."}],"review_version":1}