TheoremStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-02

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.

Ore's theorem: an $n$ -vertex graph with $n \geq 3$ and $\deg (u) + \deg (v) \geq n$ for every nonadjacent pair is Hamiltonian

Statement

Let $G$ be a finite simple graph on $n \geq 3$ vertices. If $\deg (u) + \deg (v) \geq n$ for every pair of nonadjacent vertices $u, v$ , then $G$ is Hamiltonian.

Facts & Assumptions

Given: An $n$ -vertex graph $G$ satisfying Ore's condition, with $n \geq 3$ .

[F1]

The Bondy-Chvatal procedure adds every currently eligible nonedge until none remains (The Bondy-Chvatal closure of a finite simple graph).

[L1]

A graph is Hamiltonian exactly when its closure is Hamiltonian (A graph is Hamiltonian if and only if its Bondy-Chvatal closure is Hamiltonian).

[F2]

The complete graph $K_{n}$ contains every edge between distinct vertices (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F3]

Degrees count neighbours and cannot decrease when edges are added (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

Proof

technique · direct

1.1

Every nonedge of $G$ is eligible by hypothesis. Eligibility persists as edges are added because degrees cannot decrease, so the closure procedure adds all missing edges and $cl (G) = K_{n}$ .

givenF1F2F3

1.2

Label the vertices of $K_{n}$ as $v_{1}, \dots, v_{n}$ . Since $n \geq 3$ , the cycle $v_{1}, v_{2}, \dots, v_{n}, v_{1}$ is a Hamilton cycle in $K_{n}$ .

F2given

2.1

Thus the closure of $G$ is Hamiltonian, and [L1] implies that $G$ is Hamiltonian.

step 1.1step 1.2L1∎

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 21 results over 15 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

Applied Combinatorics, Eulerian and Hamiltonian Graphs (standard reference, not scraped)

Ore's theorem: an nn-vertex graph with n≥3n≥3 and deg⁡(u)+deg⁡(v)≥ndeg(u)+deg(v)≥n for every nonadjacent pair is Hamiltonian