is_spanning_path_graph
def
A graph on n vertices is a spanning path if its vertices can be ordered so that exactly consecutive vertices are adjacent.
Statement
def is_spanning_path_graph {n : ℕ} (H : SimpleGraph (Fin n)) : Prop
- Defined in
- arXiv:2610.06228 (Hiding a Vertex from the Temporal Explorer), Sec. 7 (snapshots that are paths)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Used by 5
- temporal_path_many_targets_one_frame_trapFor every k ≥ 2 there is a temporal graph on N = k² + k vertices, all of whose snapshots are spanning paths, together with k designated…
- temporal_path_twelve_one_frame_target_trapThere is a temporal graph on twelve vertices, every snapshot a spanning path, such that every walk from vertex 0 visits at most one of the…
- is_spanning_path_graph_pathGraph_threeThe path graph on three vertices is a spanning path.
- temporal_path_four_requires_sixThere is a temporal graph on four vertices with spanning-path snapshots such that every temporal walk starting at vertex 0 needs at least…
- temporal_path_five_requires_nineThere is a temporal graph on five vertices with spanning-path snapshots such that every walk from vertex 0 needs at least nine steps to…
Lean source view module on GitHub
/-- `H` is a spanning path on `Fin n`: for some ordering `f` of the vertices, two vertices are adjacent exactly when they are consecutive in the ordering. -/ def is_spanning_path_graph {n : ℕ} (H : SimpleGraph (Fin n)) : Prop := ∃ f : Equiv.Perm (Fin n), ∀ a b, H.Adj a b ↔ ((f a : ℕ) + 1 = f b ∨ (f b : ℕ) + 1 = f a)