Alphabeta Math
LemmaStatement: 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.

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

Statement

Let GG be a finite simple graph on nn vertices, and let u,vu,v be nonadjacent vertices satisfying

degG(u)+degG(v)n.\deg_G(u)+\deg_G(v)\ge n.

Then GG is Hamiltonian if and only if G+uvG+uv is Hamiltonian.

Facts & Assumptions

Given: The graph GG, its order nn, and the eligible nonedge uvuv 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]
[F3]

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

Proof

technique · direct
1.1

Every Hamilton cycle of GG is also a Hamilton cycle of G+uvG+uv, so Hamiltonicity of GG implies Hamiltonicity of G+uvG+uv.

F1
1.2

Conversely, take a Hamilton cycle of G+uvG+uv. If it avoids the new edge uvuv, it is already a Hamilton cycle of GG. If it uses uvuv, deleting that edge leaves a Hamilton path v1=u,v2,,vn=vv_1=u,v_2,\ldots,v_n=v in GG.

F1cases
1.3

For 1in11\le i\le n-1, put ii in AA when uvi+1uv_{i+1} is an edge of GG, and put ii in BB when vivv_iv is an edge. Since uu and vv are nonadjacent, A=degG(u)|A|=\deg_G(u) and B=degG(v)|B|=\deg_G(v). Both lie in an (n1)(n-1)-element index set, while A+Bn|A|+|B|\ge n, so ABA\cap B\ne\varnothing.

givenF2F3algebra
2.1

Choose iABi\in A\cap B. Then v1,v2,,vi,vn,vn1,,vi+1,v1v_1,v_2,\ldots,v_i,v_n,v_{n-1},\ldots,v_{i+1},v_1 is a Hamilton cycle in GG: the two joining edges are vivv_iv and uvi+1uv_{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+uvG+uv implies Hamiltonicity of GG; step 1.1 proves the other direction.

step 1.1step 1.2step 2.1

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 32 results over 17 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