False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-07-31

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.

FALSE: a shortest walk between two vertices may repeat a vertex and fail to be a path

Statement

FALSE. A shortest walk between two vertices may repeat a vertex and fail to be a path.

Facts & Assumptions

Given: Vertices $u, v$ in one connected component and a $u$ to $v$ walk $W$ of minimum length.

[L1]

Every walk contains a path between the same endpoints of no greater length, and if the walk repeats a vertex the path can be chosen strictly shorter (Every walk between two vertices contains a path between the same endpoints).

[F1]

The distance $d_{G} (u, v)$ is the minimum length of a $u$ to $v$ path (Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention).

Refutation

technique · contradiction

1.1

Suppose, for contradiction, that the minimum-length walk $W$ repeats a vertex and is not a path.

assume-contragiven

2.1

By [L1], deleting a closed segment from $W$ yields a $u$ to $v$ path of length strictly less than the length of $W$ . This path is also a walk, contradicting the minimality of $W$ .

step 1.1L1F1

3.1

Therefore every shortest walk is a path, and the claimed possibility cannot occur.

step 2.1discharge-contradiction∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

5 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

University of Lethbridge, Combinatorics: A Guided Tour, Paths and Cycles (standard reference, not scraped)