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.

The Bondy-Chvatal closure is independent of the order of eligible edge additions

Statement

For every finite simple graph $G$ , all maximal sequences of eligible edge additions in the Bondy-Chvatal procedure terminate at the same graph. Consequently $\operatorname{cl}(G)$ is well defined.

Facts & Assumptions

Given: A finite simple graph $G$ on a fixed $n$ -vertex set.

[F1]

An absent edge $uv$ is eligible when $\deg(u)+\deg(v)\ge n$ , and a maximal sequence stops only when no eligible nonedge remains (The Bondy-Chvatal closure of a finite simple graph).

[F2]

Adding edges cannot decrease any vertex degree (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

[L1]

Induction proves a statement for all natural numbers from a base case and an induction step (The principle of mathematical induction).

[F3]

A finite simple graph has finitely many possible edges and hence finitely many nonedges (The cardinality $\lvert A\rvert$ of a finite set).

Proof

technique · induction on the number of nonedges

1.1

If $G$ has no nonedges, no addition is possible and every maximal sequence terminates at $G$ .

F1F3base

1.2

Assume the claimed uniqueness holds for every graph with fewer than $k$ nonedges, and let $G$ have $k>0$ nonedges. Once a nonedge is eligible, it remains eligible after other edges are added because degrees do not decrease.

F1F2ih

2.1

If $G$ has no eligible nonedge, every maximal sequence is empty. Otherwise compare two maximal sequences, whose first added edges are $e$ and $f$ . If $e=f$ , their tails start at the same graph $G+e$ , which has fewer than $k$ nonedges, so the induction hypothesis gives the same terminal graph.

step 1.2F1F3ihcases

2.2

If $e\ne f$ , persistence from step 1.2 makes $f$ eligible after adding $e$ and $e$ eligible after adding $f$ . Thus both first-step graphs can legally reach $G+e+f$ . Applying the induction hypothesis inside $G+e$ compares its given tail with the tail beginning by $f$ ; applying it inside $G+f$ compares its given tail with the tail beginning by $e$ . Both therefore have the same terminal graph as a maximal continuation from $G+e+f$ .

step 1.2F3ih

3.1

The cases in steps 2.1 and 2.2 establish uniqueness for graphs with $k$ nonedges. By induction, all finite graphs have a unique terminal graph, so the closure is independent of the addition order.

step 1.1step 2.1step 2.2L1discharge-induction∎

Depends on

Used by

A graph is Hamiltonian if and only if its Bondy-Chvatal closure is Hamiltonian Theorem

Cited to discharge well-definedness by The Bondy-Chvatal closure of a finite simple graph.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 33 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

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