RemarkRemark: AI-adaptedProof: 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.

Typical regular graphs are Hamiltonian

PDF p. 9: Section 1.5, citation to Robinson and Wormald [45]

Statement

Fix an integer $d \geq 3$ . A uniformly random labelled simple $d$ -regular graph on $n$ vertices is Hamiltonian with high probability as $n \to \infty$ through feasible orders. Here a graph is $d$ -regular when every vertex has degree $d$ , and Hamiltonian means that it contains a cycle visiting every vertex exactly once. The uniform law gives equal probability to each simple $d$ -regular graph on the labelled vertex set ${1, \dots, n}$ ; an order is feasible when at least one such graph exists. With high probability means that the probability tends to one along those orders.

Statement references

Adjacency, degrees, graph Laplacian, and spectral notation

Uniform random regular graph convention

Hamiltonicity of a uniform fixed-degree regular graph

Facts & Assumptions

[F1]

For each fixed integer $d \geq 3$ , the probability that a uniformly sampled labelled simple $d$ -regular graph is Hamiltonian tends to one as its order grows through feasible values. A Hamiltonian cycle is a spanning cyclic ordering with edges between consecutive vertices, including the last and first (Hamiltonicity of a uniform fixed-degree regular graph).

[F2]

The uniform random regular model assigns equal mass to the labelled simple $d$ -regular graphs, and its high-probability limits are taken through feasible orders (Uniform random regular graph convention). The degree and regularity conventions agree with the graph notation (Adjacency, degrees, graph Laplacian, and spectral notation).

Proof

Given: A fixed integer $d \geq 3$ and the uniform labelled simple $d$ -regular graph model at feasible orders.

Goal: Show that the graph is Hamiltonian with high probability as its order tends to infinity.

1.1givenF1F2

By [F2], the model and feasible-order limit in the statement are exactly those in [F1]; the stated cycle condition is the spanning cyclic ordering in [F1]. Thus [F1] applies to the Hamiltonian event in this model.

2.1F1F2step 1.1∎

The probability of that event therefore tends to one through feasible orders. By the high-probability convention in [F2], this is the claimed conclusion.

Source notes

The article attributes the random regular graph Hamiltonicity result to Robinson and Wormald in Section 1.5; the proof above uses the independently sourced prerequisite, not the article's assertion.

Depends on

Used by · 1

Destroying cycle spurious minima by bounded-degree edge additions

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.

Sources

Expander graphs are globally synchronizing · PDF p. 9, Section 1.5, citation to Robinson and Wormald [45]