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.

Hamiltonian cycles as finite cyclic-order events

Statement

Let $n \geq 3$ and let $G$ be a simple graph on $[n]$ . A Hamiltonian cycle is an edge set ${{v_{1}, v_{2}}, \dots, {v_{n - 1}, v_{n}}, {v_{n}, v_{1}}}$ contained in $E (G)$ , where $(v_{1}, \dots, v_{n})$ lists every vertex once. Distinct such edge sets are counted once, regardless of starting point or direction. There are $n! / (2 n)$ candidate Hamiltonian cycles on $[n]$ .

More generally, let $(Ω, w)$ be any finite probability space and let $ω \mapsto G_{ω}$ assign a simple graph on $[n]$ to every outcome. For each candidate Hamiltonian cycle $C$ , define $A_{C} = {ω \in Ω : C \subseteq E (G_{ω})}$ . The event $H$ that the sampled graph contains at least one Hamiltonian cycle is the finite union $H = ⋃_{C} A_{C}$ , with probability $P (H) = \sum_{ω \in H} w (ω)$ .

Facts & Assumptions

[F1]

Pairings, simple-graph conditioning and model transfer specifies labelled simple graphs as sets of unordered two-element edges on the labelled vertex set.

[F2]

Finite symmetric networks and loop removal identifies simple graphs with symmetric zero-diagonal adjacency matrices.

[F3]

Finite probability spaces, outcome weights, events, and event probabilities defines a finite probability space $(Ω, w)$ by nonnegative outcome weights summing to one; every subset $A \subseteq Ω$ is an event with probability $P (A) = \sum_{ω \in A} w (ω)$ .

[F4]

The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ defines $0! = 1$ and $k! = k (k - 1)!$ for positive integers $k$ ; equivalently, $n!$ is the product of the first $n$ positive integers.

Proof

Given: The objects and hypotheses in the Statement.

Goal: Establish every assertion of the Statement.

1.1F1F2construct

An ordered listing of the vertices produces the displayed edge set, with distinct endpoints at every edge. Each vertex has exactly its predecessor and successor as neighbors in this edge set. Conversely, fixing a vertex on this cycle, its next vertex can be chosen in exactly two ways; every later vertex is then forced by continuing along the edge that was not just used. Thus each edge set has exactly $n$ choices of starting point and two choices of direction, including when $n = 3$ .

2.1F1F3F4step 1.1algebra∎

Successive choices give $n!$ ordered listings. The disjoint classes in step 1.1 each have size $2 n$ , so there are $n! / (2 n)$ candidate edge sets. For the specified assignment $ω \mapsto G_{ω}$ , each $A_{C}$ is a subset of $Ω$ , hence an event by [F3]. An outcome belongs to $⋃_{C} A_{C}$ exactly when its graph $G_{ω}$ contains a Hamiltonian cycle, so this finite union is $H$ . By [F3], its probability is $\sum_{ω \in H} w (ω)$ .

Depends on

Used by · 3

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.