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.
Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs
Definition
Let be a finite simple graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets). A Hamilton path is a path that contains every vertex of exactly once. A Hamilton cycle is a cycle that contains every vertex of exactly once before returning to its initial vertex. A graph is Hamiltonian when it has a Hamilton cycle.
A graph with at least two vertices is Hamilton-connected when, for every two distinct vertices and , it has a Hamilton path whose endpoints are and . Paths and cycles use the conventions of Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges, so a Hamilton cycle has at least three vertices. Every Hamiltonian graph is connected in the sense of Connected graphs and connected components defined by the existence of vertex paths.
Depends on
Used by
- Every Hamiltonian graph on at least three vertices is 2-connected Corollary
- K₄ is Hamiltonian but has no Euler circuit Counterexample
- P₃ has a Hamilton path but no Hamilton cycle Counterexample
- Two disjoint copies of Kₘ show that Dirac's bound cannot be lowered to n/2-1 for even n=2m≥4 Counterexample
- K_3,3 has a Hamilton cycle Example
- If nonadjacent u,v in an n-vertex graph satisfy deg(u)+deg(v)≥ n, then adding uv preserves Hamiltonicity in both directions Lemma
- A graph is Hamiltonian if and only if its Bondy-Chvatal closure is Hamiltonian Theorem
- If G has a Hamilton cycle, then deleting any nonempty proper vertex set S leaves at most |S| connected components Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 15 results over 11 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)