{"id":"ca3803c9-bf2c-45b0-a59f-53b63a1c7167","arxiv_id":"2606.05835","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Strengthened Chvátal–Erdős, McDiarmid–Yolov, connected-dominating-set, and bipartite Hamiltonicity conditions all force the Hamilton cycles to span the entire cycle space.","lead":"A graph's cycles can be added together like vectors; this paper shows that for several classical families of dense, well-connected graphs, the longest possible cycles (Hamilton cycles) alone generate every other cycle. It proves strengthened versions of two famous Hamiltonian-cycle criteria (Chvátal–Erdős and McDiarmid–Yolov), and extends the recent 'Hamilton-cycle generation' framework to bipartite graphs for the first time.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Bipartite extension of Lemma 2.1 (Remark 2.2) is asserted, not proved; if it fails, Theorem 1.11 collapses.","rationale":"The reader correctly identifies the bipartite extension of Lemma 2.1 as the weakest assumption. This lemma is the common foundation for all theorems, and for the bipartite Theorem 1.11 it is imported with only a sketch. The paper's Remark 2.2 gives a plausible reason why (C1) should follow from (C3) in bipartite graphs, but it does not show that the rest of the proof (especially (C3)) carries over. Since [8] is not included, the claim 'applies essentially verbatim' is unverifiable from the manuscript alone. This is a genuine, addressable gap rather than a demonstrated error. The reader's CONDITIONAL verdict is appropriate: the authors should either supply the missing proof or cite a published bipartite version. I did not find a reason to upgrade to REJECT; the argument is coherent and the other theorems (odd n) do not depend on this extension. I concur with the reader that this is the single most load-bearing point.","tokens_in":21360,"tokens_out":16947,"duration_ms":145245,"concrete_test":"Obtain the full proof of Lemma 2.1 from [8] and annotate every line that invokes 'n is odd.' If any such use occurs in the proof of (C3) or in the construction of R (rather than only in deriving (C1) from (C2)), then Remark 2.2 is false and Theorem 1.11 must be reproved. Alternatively, attempt an independent derivation of the bipartite analogue: given a balanced bipartite Hamiltonian G with C_{2n}(G) ≠ C(G), construct the edge subset R from the nonzero linear functional vanishing on all Hamilton cycles, and prove (C2) and (C3) using only bipartiteness. If the derivation fails at any step, the theorem lacks support.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 2.1 is the foundation of the entire Christoph–Nenadov–Petrova recipe. The paper extends it from odd n to bipartite G in Remark 2.2 with only a two-sentence argument: it claims the [8] proof applies 'essentially verbatim' and that (C1) follows from (C3) using the bipartition. But the paper does not reproduce the proof of Lemma 2.1, nor does it verify that the construction of R and the proof of (C3) in [8] are independent of the parity of n. If oddness of n is used in [8] to establish (C3) (for instance, through parity of the all-ones vector in the Hamilton cycle span), then the bipartite version may be false and Theorem 1.11 has no valid starting point. This is load-bearing because every later step (S2) and (S3) presupposes an R satisfying (C1)–(C3). Without (C1), the parity switcher argument cannot even begin.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies when the subspace of the cycle space spanned by Hamilton cycles, C_n(G), equals the full cycle space C(G). Since this can only happen for odd n or bipartite G, the authors work in those settings. They prove four families of results: (i) Theorem 1.2, a Chvátal–Erdős-type connectivity condition; (ii) Theorem 1.4, a minimum-degree plus connectivity condition; (iii) Theorem 1.5, a connected dominating sets condition; (iv) Theorem 1.8, a McDiarmid–Yolov-type condition; and (v) Theorem 1.11, a balanced bipartite version. The proofs follow the Christoph–Nenadov–Petrova recipe: assume C_n(G) ≠ C(G), obtain a subgraph R satisfying (C1)–(C3), construct a short parity switcher, find disjoint paths and a Hamilton path of the remainder, and derive a contradiction. The paper also gives a tightness example for Theorem 1.5 and discusses open problems.","tokens_in":21484,"tokens_out":24512,"duration_ms":224047,"significance":"If correct, these are substantial results: they show that mild strengthenings of several classical Hamiltonicity criteria imply the much stronger property that Hamilton cycles generate the entire cycle space. The systematic use of the CNP recipe is well executed, and the appeal to external Hamiltonicity benchmarks (Chvátal–Erdős, McDiarmid–Yolov, Ordaz–Amar–Raspaud) avoids circularity. The tightness example for Theorem 1.5 is a useful addition. The main weakness is that the bipartite extension of the foundational dichotomy lemma is asserted, not proved; since Theorem 1.11 and Remark 2.4 depend on it, this is a load-bearing gap that must be addressed before the paper can be accepted.","major_comments":[{"comment":"Lemma 2.1 is stated for 'n odd or G bipartite', but the proof is cited only from [8] for odd n. Remark 2.2 asserts that the [8] proof applies 'essentially verbatim' to the bipartite case and gives a two-sentence argument only for (C1). This is not sufficient: the construction of R and in particular the proof of (C3) may depend on the parity of n in ways not visible from the remark. Since Lemma 2.1 supplies the subgraph R on which the entire parity-switcher recipe rests, Theorem 1.11 (and the bipartite applicability claimed in Remark 2.4) have no valid starting point unless the bipartite version is proved in the manuscript or cited to a source that contains it. Please include a complete proof or adjust the claims.","section":"§2.1, Remark 2.2 (used in §5)"},{"comment":"The construction of the Hamilton path in G' applies Theorem 3.3 inside each V_i \\ W with terminal pairs (w_{j-1}, u_j). However, when w_{j-1} = u_j, the same vertex appears twice as a terminal, contrary to the hypothesis of Theorem 3.3 that the 2r vertices are distinct. The text says 'the path P^i_j consists of a single vertex' and appeals to Property (5), but it does not explain how to reduce to the distinct-terminal setting, e.g., by deleting the trivial vertices and applying Theorem 3.3 to the remaining graph. This step is essential for Step (S3) of Theorem 1.4 and should be made explicit.","section":"§3, proof of Theorem 1.4, Step (S3)"}],"minor_comments":[{"comment":"The line 'assume that κ(G) ≥ c min{max{α, log n}, α²}' is inconsistent with the theorem's 'or' formulation; it should likely be 'κ(G) ≥ c max{α, log n} or κ(G) ≥ c α²'. In the first case, the condition should be κ(G) ≥ c max{α, log n} (not merely κ ≥ c log n) so that the α-term needed for Theorem 3.3 is available. The intended argument is clear, but the text should be corrected.","section":"§3, proof of Theorem 1.2"},{"comment":"In the proof that R is 2-connected, the equality deg_R(v,S) = e_R(S, T ∪ {v}) relies on the fact that S is a component of R - v, so e_R(S,T)=0. This should be stated explicitly; otherwise the displayed chain of inequalities is confusing.","section":"§4, proof of Lemma 4.2"},{"comment":"In the minimality argument at the end of Lemma 3.6, the parity of |P_i| is used implicitly: since the endpoints v_{s_i}, v_{t_i} are even-indexed vertices, |P_i| is even. This should be stated, as it is needed to verify that the shorter cycle has even length.","section":"§3, proof of Lemma 3.6"},{"comment":"The phrase 'every independent set of G of maximum size is of the form I ∪ {x} for some x ∈ A' is slightly informal; it means every maximum independent set has that form. This is clear from context, but could be rephrased.","section":"§3, Theorem 1.5 tightness example"}],"recommendation":"major_revision","confidential_remarks":"The paper is generally well written and the odd-n results appear sound on inspection. The main obstacle is the unproved bipartite extension of Lemma 2.1; Theorem 1.11 collapses if that extension fails. If the authors can supply a complete proof (or cite a version that covers bipartite graphs), I would support acceptance. The Step (S3) issue in Theorem 1.4 and the typos in Theorem 1.2 should also be fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. Theorems 1.2, 1.4, 1.5, 1.8, and 1.11 are new, and the paper does real work adapting the Christoph–Nenadov–Petrova machinery to each setting. I checked the central steps: Lemma 3.6's parity bookkeeping is sound, the α² case in Theorem 1.2 works, and the balance argument in Theorem 1.11 keeps the residual graph balanced. The authors are also honest about what they don't know: Conjecture 1.3, non-optimal constants, and a genuine obstruction example at the end. This is a serious paper.\n\nThe soft spot is the bipartite extension of Lemma 2.1. Remark 2.2 asserts the [8] proof applies 'essentially verbatim' to bipartite graphs, with a two-sentence justification for (C1). The justification for (C1) is fine: if R=G and G is bipartite with its natural bipartition, then R=G[A,B], contradicting (C3). But the paper does not show that the proof of (C3) in [8] is independent of oddness. If that proof uses the parity of n anywhere, Theorem 1.11 has no starting point. I can't confirm it does; I also can't rule it out without reading [8] side by side. This is the one load-bearing gap, and it needs referee attention.\n\nSmaller issues: Theorem 1.2's constant is not explicit because it inherits an existential c' from the authors' own Theorem 3.3 [1]. Claim 3.7's property (5) is asserted as straightforward to verify but is the least-supported step in Theorem 1.4's proof. And Lemma 4.2 case (4) has a corner case when a=b=1 and deg_R(v7,V(C))=6; the existence of the sets A and B may fail, though this is at the edge of the parameter range and likely fixable. None of these look fatal.\n\nThe citation pattern is honest. The load-bearing self-citations are to the authors' own [1] and [19,20], but they are external results, not fitted to target. There's no circularity: the target C_n=C never appears as an input.\n\nBottom line: send it to peer review. It's the first bipartite result in this program and the CE/McDiarmid-Yolov versions are new. The bipartite lemma needs a careful check; the rest is solid modulo the minor gaps above.","headline":"Genuine new results extending the CNP recipe to Chvátal–Erdős, McDiarmid–Yolov, CDS, and bipartite settings; the main gap is an unproved bipartite extension of the foundational lemma.","tokens_in":22240,"tokens_out":4507,"would_cite":true,"duration_ms":41283,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C45","05C38","05C40","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"Four mild strengthenings of standard Hamiltonicity criteria force every cycle to be a sum of Hamilton cycles.","keywords":["cycle space","Hamilton cycles","Hamiltonian graph","vertex connectivity","independence number","bipartite independence number","connected dominating set","parity switcher"],"falsifier":"Find a balanced bipartite Hamiltonian graph G with C_{2n}(G) ≠ C(G) and verify that no proper subgraph R has both properties: every Hamilton cycle uses an even number of R-edges, and every cut has at least half its G-edges in R. Such a graph would refute the bipartite dichotomy lemma and invalidate Theorem 1.11; a smaller refutation would be a graph meeting α_BIP(G) ≤ 2δ(G)−24 for which some cycle is not an F2-sum of Hamilton cycles.","tokens_in":20985,"feed_emoji":"🔄","tokens_out":6135,"duration_ms":59700,"temperature":0.7,"pith_summary":"This paper tackles a stronger question than Hamiltonicity: when does every cycle of a graph arise as the symmetric difference (binary sum) of its Hamilton cycles? Working over the two-element field, the cycle space is spanned by all cycles; the paper asks when the Hamilton cycles alone span it. It proves that several known sufficient conditions for Hamiltonicity, each strengthened by a constant factor, guarantee this spanning property for graphs with an odd number of vertices — and for balanced bipartite graphs in one case. The conditions include high connectivity against independence number, high minimum degree against bipartite independence number, many pairwise disjoint connected dominating sets, and an effective bipartite version of the classic condition. The proofs all run through one construction: a small parity-switcher that toggles whether a Hamilton cycle uses an odd number of edges from a special subgraph.","feed_headline":"Four Hamiltonian conditions force Hamilton cycles to span every cycle","feed_subtitle":"Under mild added degree or connectivity, every cycle is a binary sum of Hamilton cycles.","key_machinery":"The central object is the R-parity switcher: an even cycle with an odd number of edges of the special subgraph R, together with vertex-disjoint short paths pairing opposite vertices. Because the switcher contains two Hamilton paths between the same endpoints, one with an odd and one with an even number of R-edges, it combines with any Hamilton path on the remaining vertices to switch the parity of a Hamilton cycle. The entering wedge is a dichotomy lemma asserting that failure of the spanning property forces such an R; the paper extends this lemma to bipartite graphs and then reduces every theorem to finding a small parity switcher and a Hamilton path through the leftover vertices.","core_discovery":"The central claim is that C_n(G) = C(G) under four (and in the bipartite case, a fifth) moderate strengthenings of known Hamiltonian criteria. In words: every cycle of G is an F2-linear combination of Hamilton cycles. For example, an odd-vertex graph whose vertex connectivity is at least c·max{α(G), log n} or at least c·α(G)², for a sufficiently large absolute constant c, has this property; so does an odd graph with δ(G) ≥ max{2ᾱ(G)+9, ᾱ(G)+18}, and a balanced bipartite graph with α_BIP(G) ≤ 2δ(G)−24. The proof proceeds by contradiction through a five-step reduction: from failure of the spanning property, extract a proper subgraph R that every Hamilton cycle meets evenly, then force a Hamilt","pith_inferences":["Inference: a promising route to the paper's Conjecture 1.3 is to remove the log-factor in Theorem 1.2 by using disjoint connected dominating sets instead of spanning linkability; Theorem 1.5 already suggests that many dominating sets can replace a large connectivity threshold.","Inference: if the bipartite dichotomy lemma holds, the same five-step recipe should adapt to other Hamiltonian criteria for balanced bipartite graphs, such as a bipartite analogue of the n/2 minimum-degree condition, yielding additional bipartite spanning theorems.","Inference: the obstruction based on two cliques joined by a 2-edge matching suggests studying the family of Hamilton-generated graphs outside the constant-factor regime; a testable conjecture is that 3-connectedness plus n ≥ c·α(G)² suffices, as raised in the paper's Problem 1."],"forward_implications":["For graphs satisfying the conditions of Theorem 1.2 or 1.4, every cycle is an F2-sum of Hamilton cycles; in particular, every edge lies in some Hamilton cycle.","Any graph with 16α(G)+12 pairwise disjoint connected dominating sets has the spanning property, and the constants 16 and 12 are tight up to a constant factor: a construction with α(G)−1 disjoint connected dominating sets is non-Hamiltonian and therefore fails it.","For odd graphs with δ(G) ≥ max{2ᾱ(G)+9, ᾱ(G)+18}, the minimum-degree-versus-bipartite-independence criterion, strengthened by a constant factor, implies the full spanning property.","For balanced bipartite graphs with α_BIP(G) ≤ 2δ(G)−24, the Hamilton cycles on 2n vertices generate the entire cycle space.","The paper also exhibits a graph satisfying the pancyclicity-style n ≥ f(α(G)) condition that fails the spanning property, so the strengthened criteria are not vacuous."],"fun_headline_variants":["Tight conditions make Hamilton cycles generate every cycle","When Hamilton cycles span the whole cycle space","Odd graphs: mild criteria force full cycle span from Hamiltonians","Hamilton cycles as basis for all cycles under mild conditions","Strengthened Hamiltonian criteria give full cycle span"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire recipe rests on the bipartite extension of the dichotomy lemma, which the paper asserts follows from the odd case 'essentially verbatim' but does not prove; if that extension fails, Theorem 1.11 and the claimed bipartite applicability of the recipe collapse.","fun_headline_variants_meta":{"raw":{"variants":["Tight conditions make Hamilton cycles generate every cycle","When Hamilton cycles span the whole cycle space","Odd graphs: mild criteria force full cycle span from Hamiltonians","Hamilton cycles as basis for all cycles under mild conditions","Strengthened Hamiltonian criteria give full cycle span"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000736,"raw_usage":{"total_tokens":3228,"prompt_tokens":948,"completion_tokens":2280,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":692,"completion_tokens_details":{"reasoning_tokens":2205}},"tokens_in":692,"tokens_out":2280,"duration_ms":15636,"temperature":1.0,"reasoning_tokens":2205,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T12:23:49.507020+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a balanced bipartite Hamiltonian graph G with C_{2n}(G) ≠ C(G) and verify that no proper subgraph R has both properties: every Hamilton cycle uses an even number of R-edges, and every cut has at least half its G-edges in R. Such a graph would refute the bipartite dichotomy lemma and invalidate Theorem 1.11; a smaller refutation would be a graph meeting α_BIP(G) ≤ 2δ(G)−24 for which some cycle is not an F2-sum of Hamilton cycles.","supporting_citations":[],"review_version":2}