LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-04 (gpt-5.6-sol-codex-subscription)

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.

Adding an edge between two nonadjacent vertices of a tree creates exactly one cycle

Statement

Let $T$ be a tree and let $u, v$ be nonadjacent vertices. Adding the edge $u v$ creates exactly one cycle.

Facts & Assumptions

Given: A tree $T$ and nonadjacent vertices $u, v \in V (T)$ .

[F1]

A tree is connected and acyclic (Trees, forests, leaves and isolated vertices).

[F2]

Paths and cycles have their usual vertex-simple meanings (Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges).

Proof

technique · direct

1.1

There is a $u$ - $v$ path $P$ in $T$ , and it is unique: if two distinct such paths existed, their first divergence and next reunion would yield a cycle.

F1F2

1.2

Every cycle in $T + u v$ must contain $u v$ , since $T$ itself is acyclic. Removing $u v$ from such a cycle leaves a $u$ - $v$ path in $T$ .

F1F2

2.1

The path $P$ together with the new edge $u v$ is a cycle in $T + u v$ .

step 1.1F2

3.1

By uniqueness in step 1.1, the path obtained in step 1.2 is $P$ . Hence the cycle in step 2.1 is the only cycle.

step 1.1step 1.2∎

Depends on

Used by

Dependency tree · two levels

6 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

Reinhard Diestel, Graph Theory, Preview Chapter 1 (standard reference, not scraped)