AFTD Auto-Formalizing Theoretical Domains

temporal_path_four_requires_six

theoremverifiedoriginal

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.

  1. 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.

    lines 18–19

    uses SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj

      simp only [fourGraph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj]
      decide
  2. `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.

    lines 26–28

    uses SimpleGraph.pathGraph_adj

      refine ⟨fourGraph, ?_, ?_⟩
      · intro t
        exact ⟨fourOrder t, fun a b => SimpleGraph.pathGraph_adj⟩
  3. 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.

    lines 29–30

    uses fourCertificate

      · intro w hw0 hw hex
        apply fourCertificate (fun i => w i.val) hw0
  4. 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`.

    lines 31–32

        · intro i
          exact hw i.val
  5. 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.

    lines 33–35

        · 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.

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

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