temporal_path_four_requires_six
There is a temporal graph on four vertices with spanning-path snapshots such that every temporal walk starting at vertex 0 needs at least six steps to visit all four vertices.
Statement
theorem temporal_path_four_requires_six :
∃ G : ℕ → SimpleGraph (Fin 4),
(∀ t, is_spanning_path_graph (G t)) ∧
∀ w : ℕ → Fin 4, w 0 = 0 → is_temporal_walk G w →
¬ temporal_walk_explores_by w 5- Related work
- OP-80, arXiv:2610.06228 Sec. 7 (path snapshots). An explicit finite obstruction computed in the deep session; this is a small case, not an asymptotic advance.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- 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.
- 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 is proved by constructing an explicit temporal graph `fourGraph` on four vertices whose snapshots are all spanning paths isomorphic to P₄ via time-dependent vertex permutations. To show that exploring all four vertices starting from vertex 0 requires at least six steps, the proof establishes a finite certificate lemma (`fourCertificate`) stating that no valid temporal walk of length 5 can visit all four vertices. Because the domain of 5-step walks on four vertices is finite, this certificate is verified by computational exhaustion using `decide`. Finally, any temporal walk exploring the graph by time 5 is restricted to its first six positions, directly contradicting the certificate.
No 5-step temporal walk on `fourGraph` starting at vertex 0 can visit all four vertices. automation
After simplifying the edge relation of `fourGraph` into arithmetic conditions on the vertex permutations via `SimpleGraph.comap_adj` and `SimpleGraph.pathGraph_adj`, the tactic `decide` checks all 4⁶ = 4096 candidate sequences of six vertices from Fin 4, verifying by exhaustive computation that no sequence starting at 0 that respects the temporal walk condition visits all four vertices.
uses
SimpleGraph.comap_adj,SimpleGraph.pathGraph_adjsimp only [fourGraph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj] decide
`fourGraph` is a temporal graph whose snapshots are all spanning paths.
We instantiate the existential witness with `fourGraph`. For each time step t, `fourGraph t` is defined by pulling back the standard path graph P₄ along the permutation `fourOrder t`. Because `fourOrder t` is a permutation of the four vertices, it witnesses that each snapshot is isomorphic to P₄ via `SimpleGraph.pathGraph_adj`, establishing that every snapshot is a spanning path graph. This leaves the exploration lower bound as the remaining goal.
uses
SimpleGraph.pathGraph_adjrefine ⟨fourGraph, ?_, ?_⟩ · intro t exact ⟨fourOrder t, fun a b => SimpleGraph.pathGraph_adj⟩
Assuming for contradiction that a walk explores the graph by time 5, its restriction to the first six time steps contradicts `fourCertificate`.
We assume for contradiction that there exists a temporal walk w starting at 0 (w 0 = 0) that visits all four vertices by time 5. Restricting w to the first six time steps {0, 1, 2, 3, 4, 5} yields a walk of length 5 starting at 0. Applying `fourCertificate` to this restricted walk reduces the desired contradiction to showing that the restriction is a valid temporal walk and that it visits all four vertices.
uses
fourCertificate· intro w hw0 hw hex apply fourCertificate (fun i => w i.val) hw0
The restricted walk is a valid temporal walk for the first 5 steps.
For each step i ∈ {0, 1, 2, 3, 4}, the walk must either stay at the same vertex or follow an edge of `fourGraph i`. This holds directly from the assumption that w is a temporal walk on `fourGraph`.
· intro i exact hw i.val
The restricted walk visits every vertex in Fin 4, completing the contradiction.
For any vertex a ∈ Fin 4, the exploration hypothesis yields a time t ≤ 5 with w t = a. Linear arithmetic (`omega`) deduces t < 6, making t a valid index in Fin 6. Thus the restricted walk visits a, which contradicts `fourCertificate` and concludes the proof.
· intro a obtain ⟨t, ht, he⟩ := hex a exact ⟨⟨t, by omega⟩, he⟩
SimpleGraph.comap_adj- Two vertices u and v are adjacent in the pullback graph comap(f, G) if and only if their images f(u) and f(v) are adjacent in G.
SimpleGraph.pathGraph_adj- Two vertices u and v in the standard path graph on n vertices are adjacent if and only if their values in ℕ differ by 1.
fourCertificate- No sequence of six vertices in Fin 4 starting at vertex 0 that forms a valid temporal walk on `fourGraph` for the first five steps can visit all four vertices.
- The certificate lemma `fourCertificate` (lines 18–19) relies on the automated decision procedure `decide`. Because the domain `Fin 6 → Fin 4` is finite (with 4⁶ = 4096 elements), Lean establishes the lemma by exhaustively evaluating the universal statement over all candidate sequences.
- At line 35, the linear arithmetic tactic `omega` is used within an anonymous constructor to prove the bound t < 6 from the exploration hypothesis t ≤ 5, allowing the time step to index into `Fin 6`.
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 fourOrder (t : ℕ) : Equiv.Perm (Fin 4) := match t with | 0 => Equiv.refl _ | 1 => Equiv.swap 0 1 | 2 => (Equiv.swap 1 2).trans (Equiv.swap 0 1) | _ => Equiv.swap 0 2private def fourGraph (t : ℕ) : SimpleGraph (Fin 4) := (SimpleGraph.pathGraph 4).comap (fourOrder t)set_option maxRecDepth 100000 inset_option maxHeartbeats 0 inprivate theorem fourCertificate : ∀ v : Fin 6 → Fin 4, v 0 = 0 → (∀ i : Fin 5, v i.succ = v i.castSucc ∨ (fourGraph i.val).Adj (v i.castSucc) (v i.succ)) → ¬ (∀ a : Fin 4, ∃ i : Fin 6, v i = a) := by simp only [fourGraph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj] decidetheorem temporal_path_four_requires_six : ∃ G : ℕ → SimpleGraph (Fin 4), (∀ t, is_spanning_path_graph (G t)) ∧ ∀ w : ℕ → Fin 4, w 0 = 0 → is_temporal_walk G w → ¬ temporal_walk_explores_by w 5 := by refine ⟨fourGraph, ?_, ?_⟩ · intro t exact ⟨fourOrder t, fun a b => SimpleGraph.pathGraph_adj⟩ · intro w hw0 hw hex apply fourCertificate (fun i => w i.val) hw0 · intro i exact hw i.val · intro a obtain ⟨t, ht, he⟩ := hex a exact ⟨⟨t, by omega⟩, he⟩