temporal_path_five_requires_nine
There is a temporal graph on five vertices with spanning-path snapshots such that every walk from vertex 0 needs at least nine steps to visit all vertices.
Statement
theorem temporal_path_five_requires_nine :
∃ G : ℕ → SimpleGraph (Fin 5),
(∀ t, is_spanning_path_graph (G t)) ∧
∀ w : ℕ → Fin 5, w 0 = 0 → is_temporal_walk G w →
¬ temporal_walk_explores_by w 8- Related work
- OP-80, arXiv:2610.06228 Sec. 7. An explicit finite obstruction from this deep session; no asymptotic advance is claimed.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- temporal_target_state_table_soundIf a finite table of endpoint/target-set pairs contains the initial state and is closed under every legal temporal step, then every…
- is_spanning_path_graphA graph on n vertices is a spanning path if its vertices can be ordered so that exactly consecutive vertices are adjacent.
- is_temporal_walkA temporal walk in a temporal graph (G_t)_t: at every time step t the agent either waits or traverses one edge of the snapshot G_t.
- temporal_walk_explores_byA walk explores the temporal graph by time T if every vertex is visited at some time t ≤ T.
The proof, explained
The theorem proves that there exists a temporal graph on 5 vertices whose snapshots are all spanning paths, yet no temporal walk starting from vertex 0 can visit all 5 vertices within 8 steps. The witness graph `fiveGraph` is defined by permuting a 5-vertex path graph at each time step. A reachability table `fiveTable` precomputes all reachable pairs of (current vertex, visited vertices) at each time t ≤ 8, verified by computational reflection (`decide`) to be closed under walk transitions (`fiveClosed`) and to contain only states with at most 4 visited vertices at time 8 (`fiveCard`). Using the soundness of reachability tables (`temporal_target_state_table_sound`), any temporal walk visiting all 5 vertices by time 8 would require a state at time 8 containing all 5 vertices, contradicting the precomputed bound of at most 4.
The reachability table `fiveTable` is closed under all valid transitions from time t to t + 1 for t < 8. automation
We perform a case split over all eight time steps t ∈ {0, ..., 7} using `fin_cases`. For each time step, we unfold the definitions of `fiveTable` and `fiveGraph`, simplify set memberships and graph adjacencies using `SimpleGraph.comap_adj` and `SimpleGraph.pathGraph_adj`, decompose the goal into individual vertex transitions with `And.intro`, and verify that each transition remains within the table by computational evaluation via `decide`.
uses
Finset.forall_mem_insert,Finset.mem_singleton,forall_eq,SimpleGraph.comap_adj,SimpleGraph.pathGraph_adj,And.introintro t fin_cases t <;> simp only [fiveTable, Finset.forall_mem_insert, Finset.mem_singleton, forall_eq] <;> simp only [fiveGraph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj] <;> (repeat' apply And.intro) <;> decide
Every state reachable at time 8 has visited at most 4 vertices. automation
We unfold the definition of `fiveTable 8` and rewrite finite set memberships with `Finset.forall_mem_insert`, `Finset.mem_singleton`, and `forall_eq`. The resulting finite conjunction of cardinality checks |S| ≤ 4 for all elements of `fiveTable 8` is verified by `decide`.
uses
Finset.forall_mem_insert,Finset.mem_singleton,forall_eqsimp only [fiveTable, Finset.forall_mem_insert, Finset.mem_singleton, forall_eq] decide
Witness the temporal graph using `fiveGraph` and show that every snapshot is a spanning path.
We provide `fiveGraph` as the required sequence of graphs. For each time t, `fiveGraph t` is defined by pulling back the standard 5-vertex path graph along the permutation `fiveOrder t`. Showing it is a spanning path graph requires exhibiting this permutation, which satisfies the adjacency condition by `SimpleGraph.pathGraph_adj`.
uses
SimpleGraph.pathGraph_adjrefine ⟨fiveGraph, ?_, ?_⟩ · intro t exact ⟨fiveOrder t, fun a b => SimpleGraph.pathGraph_adj⟩
Assume for contradiction that a walk explores all vertices by time 8, and bound its visited set size to at most 4.
We assume for contradiction that there exists a temporal walk w starting at vertex 0 that visits every vertex by time 8. Applying the soundness theorem for target state tables (`temporal_target_state_table_sound`) with the inductive invariant `fiveClosed`, the pair (w 8, M) consisting of the endpoint and the set of visited vertices must belong to `fiveTable 8`. By `fiveCard`, the cardinality of M is at most 4.
uses
temporal_target_state_table_sound,fiveClosed,fiveCard· intro w hw0 hw hex obtain ⟨M, hM, hcover⟩ := temporal_target_state_table_sound fiveGraph Finset.univ 0 8 fiveTable {0} (by decide) (by simp) fiveClosed w hw0 hw have hcard := fiveCard (w 8, M) hM change M.card ≤ 4 at hcard
The visited set M at time 8 must contain all vertices of the graph.
For any vertex a, the exploration assumption gives a time t ≤ 8 at which w t = a. The coverage property provided by the soundness lemma guarantees that every vertex visited up to time 8 belongs to M, so a ∈ M, establishing univ ⊆ M.
uses
Finset.mem_univhave hfull : Finset.univ ⊆ M := by intro a ha obtain ⟨t, ht, he⟩ := hex a rw [← he] exact hcover t ht (Finset.mem_univ _)
A contradiction arises because M must contain at least 5 vertices but has at most 4. automation
From univ ⊆ M, the monotonicity of cardinality (`Finset.card_le_card`) implies that |univ| ≤ |M|. Since `Finset.univ` has cardinality 5 on `Fin 5` (by `Finset.card_univ` and `Fintype.card_fin`), we have 5 ≤ |M| ≤ 4. The `omega` tactic detects this linear integer arithmetic contradiction and closes the proof.
uses
Finset.card_le_card,Finset.card_univ,Fintype.card_finhave hge := Finset.card_le_card hfull simp only [Finset.card_univ, Fintype.card_fin] at hge omega
Finset.forall_mem_insert- A property holds for all elements of `insert a s` if and only if it holds for `a` and for all elements of `s`.
Finset.mem_singleton- An element belongs to the singleton set `{a}` if and only if it equals `a`.
forall_eq- A universally quantified statement `∀ x, x = a → p x` is logically equivalent to `p a`.
SimpleGraph.comap_adj- Vertices `u` and `v` are adjacent in the pullback graph `comap f G` if and only if `f u` and `f v` are adjacent in `G`.
SimpleGraph.pathGraph_adj- Vertices in a path graph are adjacent if and only if their indices differ by 1.
And.intro- From proofs of propositions `a` and `b`, constructs a proof of their conjunction `a ∧ b`.
temporal_target_state_table_sound- If a reachability table contains the start state and is closed under walk transitions, then any temporal walk's final position and accumulated visited set are tracked by the table.
fiveClosed- The reachability table `fiveTable` is closed under one-step transitions of temporal walks in `fiveGraph` for all times t < 8.
fiveCard- Every state reachable at time 8 in `fiveTable` has visited at most 4 vertices.
Finset.mem_univ- Every element of a finite type belongs to its universal finset `Finset.univ`.
Finset.card_le_card- If one finset is a subset of another, its cardinality is less than or equal to the other's cardinality.
Finset.card_univ- The cardinality of the universal finset `Finset.univ` equals the cardinality of the underlying finite type.
Fintype.card_fin- The cardinality of `Fin n` is equal to `n`.
- The transitions of the reachability table across all eight time steps (`fiveClosed`) and the cardinality check at time 8 (`fiveCard`) are verified by exhaustive computation via `decide` rather than symbolic graph-theoretic arguments.
- The final contradiction between 5 ≤ |M| and |M| ≤ 4 is discharged by the Presburger arithmetic tactic `omega`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private def fiveOrder (t : ℕ) : Equiv.Perm (Fin 5) := match t with | 0 | 2 => ((Equiv.swap 1 4).trans (Equiv.swap 2 1)).trans (Equiv.swap 3 2) | 1 => ((Equiv.swap 0 1).trans (Equiv.swap 0 2)).trans (Equiv.swap 3 4) | 3 | 4 => ((Equiv.swap 0 2).trans (Equiv.swap 1 3)).trans (Equiv.swap 0 1) | 5 => Equiv.swap 2 3 | _ => (Equiv.swap 0 2).trans (Equiv.swap 0 3)private def fiveGraph (t : ℕ) : SimpleGraph (Fin 5) := (SimpleGraph.pathGraph 5).comap (fiveOrder t)private instance fiveGraphDec (t : ℕ) : DecidableRel (fiveGraph t).Adj := fun a b => decidable_of_iff (((fiveOrder t a : Fin 5) : ℕ) + 1 = fiveOrder t b ∨ ((fiveOrder t b : Fin 5) : ℕ) + 1 = fiveOrder t a) SimpleGraph.pathGraph_adj.symmprivate def fiveTable : ℕ → Finset (Fin 5 × Finset (Fin 5)) | 0 => {(0, {0})} | 1 => {(0, {0}), (2, {0, 2})} | 2 => {(0, {0}), (0, {0, 2}), (1, {0, 1}), (2, {0, 2})} | 3 => {(0, {0}), (0, {0, 2}), (1, {0, 1}), (2, {0, 2}), (3, {0, 2, 3}), (4, {0, 1, 4})} | 4 => {(0, {0}), (0, {0, 1}), (0, {0, 2}), (1, {0, 1}), (1, {0, 1, 2}), (1, {0, 1, 4}), (2, {0, 2}), (2, {0, 2, 3}), (3, {0, 2, 3}), (4, {0, 1, 4})} | 5 => {(0, {0}), (0, {0, 1}), (0, {0, 1, 2}), (0, {0, 1, 4}), (0, {0, 2}), (0, {0, 2, 3}), (1, {0, 1}), (1, {0, 1, 2}), (1, {0, 1, 4}), (2, {0, 1, 2}), (2, {0, 2}), (2, {0, 2, 3}), (3, {0, 2, 3}), (4, {0, 1, 2, 4}), (4, {0, 1, 4})} | 6 => {(0, {0}), (0, {0, 1}), (0, {0, 1, 2}), (0, {0, 1, 4}), (0, {0, 2}), (0, {0, 2, 3}), (1, {0, 1}), (1, {0, 1, 2}), (1, {0, 1, 2, 3}), (1, {0, 1, 4}), (2, {0, 1, 2}), (2, {0, 1, 2, 4}), (2, {0, 2}), (2, {0, 2, 3}), (3, {0, 1, 2, 3}), (3, {0, 1, 3}), (3, {0, 1, 3, 4}), (3, {0, 2, 3}), (4, {0, 1, 2, 4}), (4, {0, 1, 4}), (4, {0, 2, 3, 4}), (4, {0, 2, 4})} | 7 => {(0, {0}), (0, {0, 1}), (0, {0, 1, 2}), (0, {0, 1, 2, 3}), (0, {0, 1, 2, 4}), (0, {0, 1, 4}), (0, {0, 2}), (0, {0, 2, 3}), (1, {0, 1}), (1, {0, 1, 2}), (1, {0, 1, 2, 3}), (1, {0, 1, 3}), (1, {0, 1, 3, 4}), (1, {0, 1, 4}), (2, {0, 1, 2}), (2, {0, 1, 2, 4}), (2, {0, 2}), (2, {0, 2, 3}), (2, {0, 2, 3, 4}), (2, {0, 2, 4}), (3, {0, 1, 2, 3}), (3, {0, 1, 3}), (3, {0, 1, 3, 4}), (3, {0, 2, 3}), (4, {0, 1, 2, 4}), (4, {0, 1, 4}), (4, {0, 2, 3, 4}), (4, {0, 2, 4})} | 8 => {(0, {0}), (0, {0, 1}), (0, {0, 1, 2}), (0, {0, 1, 2, 3}), (0, {0, 1, 2, 4}), (0, {0, 1, 3}), (0, {0, 1, 3, 4}), (0, {0, 1, 4}), (0, {0, 2}), (0, {0, 2, 3}), (0, {0, 2, 3, 4}), (0, {0, 2, 4}), (1, {0, 1}), (1, {0, 1, 2}), (1, {0, 1, 2, 3}), (1, {0, 1, 2, 4}), (1, {0, 1, 3}), (1, {0, 1, 3, 4}), (1, {0, 1, 4}), (2, {0, 1, 2}), (2, {0, 1, 2, 3}), (2, {0, 1, 2, 4}), (2, {0, 2}), (2, {0, 2, 3}), (2, {0, 2, 3, 4}), (2, {0, 2, 4}), (3, {0, 1, 2, 3}), (3, {0, 1, 3}), (3, {0, 1, 3, 4}), (3, {0, 2, 3}), (4, {0, 1, 2, 4}), (4, {0, 1, 4}), (4, {0, 2, 3, 4}), (4, {0, 2, 4})} | _ => ∅set_option maxRecDepth 100000 inset_option maxHeartbeats 0 inset_option synthInstance.maxSize 100000 inprivate theorem fiveClosed : ∀ t : Fin 8, ∀ p ∈ fiveTable t.val, ∀ u : Fin 5, u = p.1 ∨ (fiveGraph t.val).Adj p.1 u → (u, if u ∈ Finset.univ then insert u p.2 else p.2) ∈ fiveTable (t.val + 1) := by intro t fin_cases t <;> simp only [fiveTable, Finset.forall_mem_insert, Finset.mem_singleton, forall_eq] <;> simp only [fiveGraph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj] <;> (repeat' apply And.intro) <;> decideset_option maxRecDepth 100000 inset_option maxHeartbeats 0 inset_option synthInstance.maxSize 100000 inprivate theorem fiveCard : ∀ p ∈ fiveTable 8, p.2.card ≤ 4 := by simp only [fiveTable, Finset.forall_mem_insert, Finset.mem_singleton, forall_eq] decidetheorem temporal_path_five_requires_nine : ∃ G : ℕ → SimpleGraph (Fin 5), (∀ t, is_spanning_path_graph (G t)) ∧ ∀ w : ℕ → Fin 5, w 0 = 0 → is_temporal_walk G w → ¬ temporal_walk_explores_by w 8 := by refine ⟨fiveGraph, ?_, ?_⟩ · intro t exact ⟨fiveOrder t, fun a b => SimpleGraph.pathGraph_adj⟩ · intro w hw0 hw hex obtain ⟨M, hM, hcover⟩ := temporal_target_state_table_sound fiveGraph Finset.univ 0 8 fiveTable {0} (by decide) (by simp) fiveClosed w hw0 hw have hcard := fiveCard (w 8, M) hM change M.card ≤ 4 at hcard have hfull : Finset.univ ⊆ M := by intro a ha obtain ⟨t, ht, he⟩ := hex a rw [← he] exact hcover t ht (Finset.mem_univ _) have hge := Finset.card_le_card hfull simp only [Finset.card_univ, Fintype.card_fin] at hge omega