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

If nonadjacent $u, v$ in an $n$ -vertex graph satisfy $\deg (u) + \deg (v) \geq n$ , then adding $u v$ preserves Hamiltonicity in both directions

Statement

Let $G$ be a finite simple graph on $n$ vertices, and let $u, v$ be nonadjacent vertices satisfying

$\deg_{G} (u) + \deg_{G} (v) \geq n .$

Then $G$ is Hamiltonian if and only if $G + u v$ is Hamiltonian.

Facts & Assumptions

Given: The graph $G$ , its order $n$ , and the eligible nonedge $u v$ in the statement.

[F1]

A Hamilton cycle contains every vertex exactly once before returning to its start (Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs).

[F2]

The degree of a vertex is the cardinality of its neighbourhood (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

[F3]

Cardinalities of finite sets obey the pigeonhole principle for two subsets of a common finite set (The cardinality $∣ A ∣$ of a finite set).

Proof

technique · direct

1.1

Every Hamilton cycle of $G$ is also a Hamilton cycle of $G + u v$ , so Hamiltonicity of $G$ implies Hamiltonicity of $G + u v$ .

1.2

Conversely, take a Hamilton cycle of $G + u v$ . If it avoids the new edge $u v$ , it is already a Hamilton cycle of $G$ . If it uses $u v$ , deleting that edge leaves a Hamilton path $v_{1} = u, v_{2}, \dots, v_{n} = v$ in $G$ .

F1cases

1.3

For $1 \leq i \leq n - 1$ , put $i$ in $A$ when $u v_{i + 1}$ is an edge of $G$ , and put $i$ in $B$ when $v_{i} v$ is an edge. Since $u$ and $v$ are nonadjacent, $∣ A ∣ = \deg_{G} (u)$ and $∣ B ∣ = \deg_{G} (v)$ . Both lie in an $(n - 1)$ -element index set, while $∣ A ∣ + ∣ B ∣ \geq n$ , so $A \cap B \neq \emptyset$ .

givenF2F3algebra

2.1

Choose $i \in A \cap B$ . Then $v_{1}, v_{2}, \dots, v_{i}, v_{n}, v_{n - 1}, \dots, v_{i + 1}, v_{1}$ is a Hamilton cycle in $G$ : the two joining edges are $v_{i} v$ and $u v_{i + 1}$ , and all other edges come from the path in step 1.2.

step 1.2step 1.3F1

3.1

The cases in step 1.2 and the construction in step 2.1 prove that Hamiltonicity of $G + u v$ implies Hamiltonicity of $G$ ; step 1.1 proves the other direction.

step 1.1step 1.2step 2.1∎

Depends on

Used by

Dependency tree · two levels

13 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

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

If nonadjacent u,vu,v in an nn-vertex graph satisfy deg⁡(u)+deg⁡(v)≥ndeg(u)+deg(v)≥n, then adding uvuv preserves Hamiltonicity in both directions