AFTD Auto-Formalizing Theoretical Domains

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

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)
See it in the graphDiscuss this resultChallenge it