Alphabeta MathHow 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.
has a Hamilton path but no Hamilton cycle
Statement refuted
Every finite simple graph with a Hamilton path has a Hamilton cycle.
Counterexample
The path graph has vertices and edges .
Facts & Assumptions
Given: The path graph .
The graph has the displayed vertices and consecutive edges (Empty and complete graphs, complete bipartite graphs, and the convention that and have vertices).
A Hamilton path contains every vertex exactly once (Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs).
A Hamiltonian graph satisfies the vertex-deletion component bound (If has a Hamilton cycle, then deleting any nonempty proper vertex set leaves at most connected components).
Verification
The path uses both edges and contains every vertex exactly once, so it is a Hamilton path.
Deleting the middle vertex leaves two isolated vertices, hence two components. This violates [L1] for the singleton set , so has no Hamilton cycle.
Therefore a Hamilton path need not extend to a Hamilton cycle.
Depends on
- Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs
- Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices
- If $G$ has a Hamilton cycle, then deleting any nonempty proper vertex set $S$ leaves at most $|S|$ connected components
Used by
Nothing in the library uses this result yet.
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 20 results over 13 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)