LemmaStatement: AI-generatedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

From Hamiltonicity and an invariant event to a prescribed cycle

Statement

Fix $d \geq 3$ . Along feasible orders $n$ , let $G_{n}$ be uniform on $Ω_{n, d}$ and let $Q_{n}$ be a property of graphs on $[n]$ invariant under every vertex relabeling. Assume $P (G_{n} \in Q_{n}) \to 1$ and $P (G_{n} is Hamiltonian) \to 1$ . Then for every sufficiently large feasible $n$ and every prescribed candidate Hamiltonian cycle $C_{n}$ on $[n]$ , there exists a simple $d$ -regular graph in $Q_{n}$ containing $C_{n}$ . This is an existence conclusion; it asserts no high probability for containing one fixed cycle.

Facts & Assumptions

[F1]

Feasible orders for labelled simple regular graphs supplies the unbounded feasible-order set.

[F2]

Hamiltonian cycles as finite cyclic-order events supplies the finite Hamiltonicity event and its cycle witnesses.

[F3]

Vertex relabeling preserves the uniform regular graph law maps any Hamiltonian cycle to any prescribed one and preserves regularity and invariant properties.

[F4]

Intersecting finitely many high-probability events gives positive probability and nonemptiness of the intersection of two events of probability tending to one.

Proof

Given: The objects and hypotheses in the Statement.

Goal: Establish every assertion of the Statement.

1.1givenF1F2F4

On the common finite graph space, intersect the event $Q_{n}$ with the Hamiltonicity event. Both have probability tending to one by hypothesis, so F4 gives an outcome $G$ in their intersection for every sufficiently large feasible $n$ . Choose a Hamiltonian cycle $D$ contained in $G$ . The cutoff depends on the two probabilities and is independent of the prescribed cycle.

2.1F3step 1.1∎

For any prescribed $C_{n}$ , F3 supplies $σ$ with $σ D = C_{n}$ . The graph $σ G$ is simple and $d$ -regular, belongs to $Q_{n}$ by its relabeling invariance, and contains $C_{n}$ . This proves the existence assertion for every prescribed cycle using the same eventual cutoff. It uses no claim about the frequency of a fixed cycle in the uniform model.

Depends on

Used by · 1

Hamiltonicity of a uniform fixed-degree regular graph

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.