ExampleConstruction: AI-generatedVerification: 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.

A transitive tournament has a directed Hamilton path and no directed cycle

Example

On $V = {1, 2, \dots, n}$ with $n \geq 1$ , orient the edge between $i$ and $j$ as $i \to j$ exactly when $i < j$ . This transitive tournament has the directed Hamilton path $1, 2, \dots, n$ and has no directed cycle.

Facts & Assumptions

Given: The displayed orientation of the complete graph on $V$ .

[F1]

A tournament chooses exactly one arc direction between each distinct pair (A tournament is an orientation of a complete finite graph).

[F2]

Directed paths and cycles must follow all displayed arc directions (Directed walks, trails, paths and cycles, and strong connectivity).

[L1]

Every nonempty tournament has a directed Hamilton path (Redei's theorem: every nonempty tournament has a directed Hamilton path).

Verification

technique · direct

1.1

For each distinct pair $i, j$ , exactly one of $i < j$ and $j < i$ holds, so the construction is a tournament by [F1]. Each arc in the list $1, 2, \dots, n$ points forward, and the list contains every vertex once, so it is a directed Hamilton path, explicitly realizing [L1].

givenF1F2L1

1.2

Along every directed walk in this tournament, the vertex label strictly increases at each positive-length step. Such a walk cannot return to its initial label, so no directed cycle exists.

givenF2

2.1

Thus a tournament may have a directed Hamilton path while having no directed cycle.

step 1.1step 1.2∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

8 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

Encyclopedia of Mathematics, Tournament (standard reference, not scraped)