AFTD Auto-Formalizing Theoretical Domains

temporal_path_five_requires_nine

theoremverifiedoriginal

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.

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

    lines 38–43

    uses Finset.forall_mem_insert, Finset.mem_singleton, forall_eq, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj, And.intro

      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) <;>
        decide
  2. 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`.

    lines 52–53

    uses Finset.forall_mem_insert, Finset.mem_singleton, forall_eq

      simp only [fiveTable, Finset.forall_mem_insert, Finset.mem_singleton, forall_eq]
      decide
  3. 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`.

    lines 60–62

    uses SimpleGraph.pathGraph_adj

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

    lines 63–67

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

    lines 68–72

    uses Finset.mem_univ

        have hfull : Finset.univ ⊆ M := by
          intro a ha
          obtain ⟨t, ht, he⟩ := hex a
          rw [← he]
          exact hcover t ht (Finset.mem_univ _)
  6. 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.

    lines 73–75

    uses Finset.card_le_card, Finset.card_univ, Fintype.card_fin

        have 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`.

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