temporal_connected_explore_sq
Every temporal graph on n vertices all of whose snapshots are connected can be explored from any start vertex within (n − 1)² time steps.
Statement
theorem temporal_connected_explore_sq :
∀ (n : ℕ) (G : ℕ → SimpleGraph (Fin n)), (∀ t, (G t).Connected) →
∀ s : Fin n, ∃ w : ℕ → Fin n, w 0 = s ∧ is_temporal_walk G w ∧
temporal_walk_explores_by w ((n - 1) ^ 2)- Formalizes
- On Temporal Graph Exploration (ICALP 2015), the O(n²) upper bound for always-connected temporal graphs, recalled as [24] in arXiv:2610.06228, Sec. 1; the Lean states the explicit bound (n − 1)² from the standard reachability argument
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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
Every temporal graph with connected snapshots can be explored within (n − 1)² time steps by visiting vertices sequentially. First, snapshot connectedness guarantees that the reachable set from any vertex grows by at least one at each step until it covers the entire graph, so any single target vertex can be reached within n − 1 steps. By induction on list length, concatenating these single-target walks produces a temporal walk visiting any list of vertices within length times n − 1 steps. Finally, applying this to the list of all n − 1 vertices other than the starting vertex yields a complete exploration within (n − 1)² steps.
Define R(j) as the set of vertices reachable from v at time t0 + j via a temporal walk of length j
We define R(j) ⊆ Fin n to be the finset of all vertices y for which there exists a temporal walk p starting at v at time t0 such that p(j) = y.
classical let R : ℕ → Finset (Fin n) := fun j => Finset.univ.filter fun y => ∃ p : ℕ → Fin n, p 0 = v ∧ (∀ i < j, p (i + 1) = p i ∨ (G (t0 + i)).Adj (p i) (p (i + 1))) ∧ p j = y
The reachable sets are monotonic: R(j) ⊆ R(j + 1) for all j
Given y ∈ R(j) witnessed by a path p, extending p by remaining at y at step j produces a valid temporal walk of length j + 1 reaching y at time j + 1. Case analysis on whether an index i is strictly less than j or equal to j confirms each step is either stationary or a graph edge.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Nat.lt_or_ge,if_truehave hmono : ∀ j, R j ⊆ R (j + 1) := by intro j y hy simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hy ⊢ obtain ⟨p, hp0, hp, hpj⟩ := hy refine ⟨fun i => if i ≤ j then p i else y, by simp [hp0], fun i hi => ?_, by simp⟩ rcases Nat.lt_or_ge i j with h | h · have := hp i h simp only [show i ≤ j from h.le, show i + 1 ≤ j from h, if_true] exact this · obtain rfl : i = j := by omega left; simp [hpj]
The starting vertex v belongs to R(0)
The constant walk at v has length 0 and vacuously satisfies all step conditions, so v ∈ R(0).
uses
Finset.mem_filter,Finset.mem_univ,true_and,Nat.not_lt_zerohave hv : v ∈ R 0 := by simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨fun _ => v, rfl, fun i hi => absurd hi (Nat.not_lt_zero _), rfl⟩
As long as R(j) is not the entire vertex set, its cardinality strictly increases: |R(j)| < |R(j + 1)|
If R(j) ≠ univ, pick a vertex z ∉ R(j). Since v ∈ R(j) by monotonicity and the snapshot G(t0 + j) is connected, there is a walk from v to z in that snapshot. This walk crosses the boundary of R(j) via some directed edge d from R(j) to its complement. Extending the temporal walk reaching d.fst at time j by following d at step j places d.snd into R(j + 1). Since d.snd ∉ R(j), R(j) is a strict subset of R(j + 1), so its cardinality strictly increases.
uses
Finset.card_lt_card,Finset.mem_filter,Finset.mem_univ,true_and,Nat.lt_or_ge,if_truehave hgrow : ∀ j, R j ≠ Finset.univ → (R j).card < (R (j + 1)).card := by intro j hj obtain ⟨z, hz⟩ : ∃ z, z ∉ R j := by by_contra h; push Not at h; exact hj (Finset.eq_univ_iff_forall.2 h) have hvj : v ∈ R j := by clear hz hj induction j with | zero => exact hv | succ j ih => exact hmono j ih obtain ⟨wk⟩ := (hG (t0 + j)).preconnected v z obtain ⟨d, -, hd1, hd2⟩ := wk.exists_boundary_dart (↑(R j) : Set (Fin n)) hvj hz refine Finset.card_lt_card ((hmono j).ssubset_of_not_subset fun hsub => hd2 ?_) have hy : d.snd ∈ R (j + 1) := by have h1 : d.fst ∈ R j := hd1 simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at h1 ⊢ obtain ⟨p, hp0, hp, hpj⟩ := h1 refine ⟨fun i => if i ≤ j then p i else d.snd, by simp [hp0], fun i hi => ?_, by simp⟩ rcases Nat.lt_or_ge i j with h | h · simp only [show i ≤ j from h.le, show i + 1 ≤ j from h, if_true] exact hp i h · obtain rfl : i = j := by omega right; simpa [hpj] using d.adj exact hsub hy
For every j, |R(j)| ≥ min(j + 1, n) automation
We proceed by induction on j. For j = 0, |R(0)| ≥ 1 since v ∈ R(0). In the inductive step, if R(j) is already univ then R(j + 1) = univ with cardinality n; otherwise |R(j + 1)| > |R(j)|, increasing the cardinality by at least 1. Linear arithmetic completes both branches.
uses
Finset.eq_univ_of_forall,Finset.mem_univ,Finset.card_univ,Fintype.card_finhave hcard : ∀ j, min (j + 1) n ≤ (R j).card := by intro j induction j with | zero => have := Finset.card_pos.2 ⟨v, hv⟩ omega | succ j ih => by_cases hj : R j = Finset.univ · have : R (j + 1) = Finset.univ := Finset.eq_univ_of_forall fun y => hmono j (by rw [hj]; exact Finset.mem_univ y) rw [this, Finset.card_univ, Fintype.card_fin]; omega · have := hgrow j hj; omega
R(n − 1) equals the full vertex set, so any target vertex u belongs to R(n − 1) automation
Since n ≥ 1 (as Fin n has an element v), the cardinality bound gives |R(n − 1)| ≥ min(n, n) = n. Since any subset of Fin n has cardinality at most n, |R(n − 1)| = n and R(n − 1) = univ. Thus u ∈ R(n − 1).
uses
Finset.eq_univ_of_card,Finset.card_le_univ,Fintype.card_fin,Finset.mem_univhave hn : 1 ≤ n := Nat.one_le_iff_ne_zero.2 fun h => by subst h; exact v.elim0 have hfull : R (n - 1) = Finset.univ := by apply Finset.eq_univ_of_card have := hcard (n - 1) have hle := Finset.card_le_univ (R (n - 1)) simp only [Fintype.card_fin] at hle ⊢ omega have hu : u ∈ R (n - 1) := by rw [hfull]; exact Finset.mem_univ u
There exists an infinite temporal walk from v reaching u within n − 1 steps automation
Extract the path p of length n − 1 reaching u, and extend it infinitely by staying at u at all times i ≥ n − 1. Linear arithmetic and rewriting simplify the conditional cases to verify that this is a valid temporal walk reaching u at step n − 1 ≤ n − 1.
uses
Finset.mem_filter,Finset.mem_univ,true_and,le_rfl,Nat.lt_or_ge,if_true,if_falsesimp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hu obtain ⟨p, hp0, hp, hpj⟩ := hu refine ⟨fun i => if i ≤ n - 1 then p i else u, by simp [hp0], fun i => ?_, ⟨n - 1, le_rfl, by simp [hpj]⟩⟩ rcases Nat.lt_or_ge i (n - 1) with h | h · simp only [show i ≤ n - 1 from h.le, show i + 1 ≤ n - 1 from h, if_true] exact hp i h · left have h1 : ¬ (i + 1 ≤ n - 1) := by omega simp only [h1, if_false] by_cases h2 : i ≤ n - 1 · obtain rfl : i = n - 1 := by omega simp [hpj] · simp [h2]
Base case: the empty list of vertices is visited by the constant walk in 0 steps
By induction on the list L. For L = [], the constant walk w(i) = v starts at v, stays at v at every time step, and vacuously visits every vertex in the empty list within 0 ≤ 0 * (n − 1) steps.
uses
Or.inl,List.not_mem_nilinduction L with | nil => intro t0 v exact ⟨fun _ => v, rfl, fun _ => Or.inl rfl, fun u hu => absurd hu List.not_mem_nil⟩
Inductive step: concatenate the walk reaching a with the walk visiting L to obtain a temporal walk starting at v automation
By temporal_connected_reach_within, some walk q reaches a at time j ≤ n − 1. By the induction hypothesis started at time t0 + j from a, a walk p visits L within |L| * (n − 1) steps. Splicing q before time j and p after time j yields a valid temporal walk starting at v, verified by case analysis on whether the step occurs before, at, or after the splice point j.
uses
temporal_connected_reach_within,Nat.lt_or_ge,if_true,if_false,le_refl| cons a L ih => intro t0 v obtain ⟨q, hq0, hq, j, hj, hqj⟩ := temporal_connected_reach_within G hG t0 v a obtain ⟨p, hp0, hp, hpL⟩ := ih (t0 + j) a refine ⟨fun i => if i ≤ j then q i else p (i - j), by simp [hq0], fun i => ?_, ?_⟩ · rcases Nat.lt_or_ge i j with h | h · simp only [show i ≤ j from h.le, show i + 1 ≤ j from h, if_true] exact hq i · have h1 : ¬ (i + 1 ≤ j) := by omega simp only [h1, if_false] have hpi := hp (i - j) have e1 : i - j + 1 = i + 1 - j := by omega have e2 : t0 + j + (i - j) = t0 + i := by omega rw [e1, e2] at hpi by_cases h2 : i ≤ j · obtain rfl : i = j := by omega simp only [le_refl, if_true, hqj] simpa [hp0] using hpi · simp only [h2, if_false] exact hpiThe spliced walk visits every vertex in a :: L within (|L| + 1) * (n − 1) steps automation
If u = a, it is reached at step j ≤ n − 1 ≤ (|L| + 1) * (n − 1). If u ∈ L, it is reached by p at step k ≤ |L| * (n − 1), so on the spliced walk it is reached at step j + k ≤ (n − 1) + |L| * (n − 1) = (|L| + 1) * (n − 1).
uses
List.length_cons,le_trans,Nat.le_mul_of_pos_left,Nat.succ_pos,add_mul,one_mul,Nat.add_zero,le_refl,if_true,if_false,Nat.add_sub_cancel_left· intro u hu rcases List.mem_cons.1 hu with rfl | hu · refine ⟨j, ?_, by simp [hqj]⟩ rw [List.length_cons] exact le_trans hj (Nat.le_mul_of_pos_left (n - 1) (Nat.succ_pos _)) · obtain ⟨k, hk, hpk⟩ := hpL u hu refine ⟨j + k, by rw [List.length_cons, add_mul, one_mul]; omega, ?_⟩ by_cases hk0 : k = 0 · subst hk0 simp only [Nat.add_zero, le_refl, if_true] rw [hqj, ← hpk, hp0] · have : ¬ (j + k ≤ j) := by omega simp only [this, if_false, Nat.add_sub_cancel_left, hpk]
Apply temporal_connected_visit_list to the list of all vertices other than s
We instantiate temporal_connected_visit_list with the list of vertices (Finset.univ.erase s).toList starting from s at time 0, obtaining a temporal walk w starting at s that visits every vertex in that list within length times n − 1 steps.
uses
temporal_connected_visit_listclassical intro n G hG s obtain ⟨w, hw0, hw, hL⟩ := temporal_connected_visit_list G hG (Finset.univ.erase s).toList 0 s refine ⟨w, hw0, fun t => by simpa using hw t, fun u => ?_⟩
The walk w explores all vertices of the graph within (n − 1)² steps
For any vertex u, if u = s then w visits u at time 0 ≤ (n − 1)². If u ≠ s, u belongs to the erased list, so w visits u at step j bounded by the list length times n − 1. Since the erased finset has cardinality n − 1, the bound is (n − 1) * (n − 1) = (n − 1)².
uses
Nat.zero_le,le_trans,Finset.length_toList,Finset.card_erase_of_mem,Finset.mem_univ,Finset.card_univ,Fintype.card_fin,sqby_cases hu : u = s · exact ⟨0, Nat.zero_le _, hu ▸ hw0⟩ · obtain ⟨j, hj, hwj⟩ := hL u (by simp [hu]) refine ⟨j, le_trans hj ?_, hwj⟩ simp only [Finset.length_toList, Finset.card_erase_of_mem (Finset.mem_univ s), Finset.card_univ, Fintype.card_fin] rw [sq]
Finset.mem_filter- Membership in a filtered finset means membership in the original finset and satisfying the filter predicate
Finset.mem_univ- Every element of a finite type belongs to the universal finset
true_and- True ∧ p simplifies to p
Nat.lt_or_ge- For any natural numbers n and m, either n < m or n ≥ m
if_true- An if-then-else whose condition is True evaluates to the then branch
Nat.not_lt_zero- No natural number is strictly less than zero
Finset.card_lt_card- A strict subset of a finite set has strictly smaller cardinality
Finset.eq_univ_of_forall- A finset containing every element of the type equals the universal finset
Finset.card_univ- The cardinality of Finset.univ equals the cardinality of the underlying finite type
Fintype.card_fin- The cardinality of Fin n is n
Finset.eq_univ_of_card- A finset whose cardinality equals the cardinality of the type is the universal finset
Finset.card_le_univ- The cardinality of any finset is at most the cardinality of the ambient finite type
le_rfl- The less-than-or-equal relation is reflexive
le_refl- The less-than-or-equal relation is reflexive
if_false- An if-then-else whose condition is False evaluates to the else branch
Or.inl- Disjunction introduction: p implies p ∨ q
List.not_mem_nil- No element is a member of the empty list
temporal_connected_reach_within- In a temporal graph with connected snapshots, every vertex is reachable from any start vertex within n − 1 steps
temporal_connected_visit_list- Given any list of vertices, a temporal walk can visit all of them in order within length times n − 1 steps
List.length_cons- The length of a cons list a :: as is as.length + 1
le_trans- Transitivity of less-than-or-equal: a ≤ b and b ≤ c imply a ≤ c
Nat.le_mul_of_pos_left- For positive n, m ≤ n * m
Nat.succ_pos- The successor of any natural number is strictly positive
add_mul- Right distributivity of multiplication over addition: (a + b) * c = a * c + b * c
one_mul- One is the left identity for multiplication: 1 * a = a
Nat.add_zero- Adding zero to a natural number leaves it unchanged: n + 0 = n
Nat.add_sub_cancel_left- Left cancellation of addition in subtraction: n + m − n = m
Nat.zero_le- Zero is less than or equal to any natural number
Finset.length_toList- The length of the list obtained from a finset equals the cardinality of the finset
Finset.card_erase_of_mem- Removing an element from a finset decreases its cardinality by 1
sq- Squaring an element equals multiplying it by itself: a ^ 2 = a * a
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.
theorem temporal_connected_reach_within {n : ℕ} (G : ℕ → SimpleGraph (Fin n)) (hG : ∀ t, (G t).Connected) (t0 : ℕ) (v u : Fin n) : ∃ w : ℕ → Fin n, w 0 = v ∧ (∀ i, w (i + 1) = w i ∨ (G (t0 + i)).Adj (w i) (w (i + 1))) ∧ ∃ j ≤ n - 1, w j = u := by classical let R : ℕ → Finset (Fin n) := fun j => Finset.univ.filter fun y => ∃ p : ℕ → Fin n, p 0 = v ∧ (∀ i < j, p (i + 1) = p i ∨ (G (t0 + i)).Adj (p i) (p (i + 1))) ∧ p j = y have hmono : ∀ j, R j ⊆ R (j + 1) := by intro j y hy simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hy ⊢ obtain ⟨p, hp0, hp, hpj⟩ := hy refine ⟨fun i => if i ≤ j then p i else y, by simp [hp0], fun i hi => ?_, by simp⟩ rcases Nat.lt_or_ge i j with h | h · have := hp i h simp only [show i ≤ j from h.le, show i + 1 ≤ j from h, if_true] exact this · obtain rfl : i = j := by omega left; simp [hpj] have hv : v ∈ R 0 := by simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨fun _ => v, rfl, fun i hi => absurd hi (Nat.not_lt_zero _), rfl⟩ have hgrow : ∀ j, R j ≠ Finset.univ → (R j).card < (R (j + 1)).card := by intro j hj obtain ⟨z, hz⟩ : ∃ z, z ∉ R j := by by_contra h; push Not at h; exact hj (Finset.eq_univ_iff_forall.2 h) have hvj : v ∈ R j := by clear hz hj induction j with | zero => exact hv | succ j ih => exact hmono j ih obtain ⟨wk⟩ := (hG (t0 + j)).preconnected v z obtain ⟨d, -, hd1, hd2⟩ := wk.exists_boundary_dart (↑(R j) : Set (Fin n)) hvj hz refine Finset.card_lt_card ((hmono j).ssubset_of_not_subset fun hsub => hd2 ?_) have hy : d.snd ∈ R (j + 1) := by have h1 : d.fst ∈ R j := hd1 simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at h1 ⊢ obtain ⟨p, hp0, hp, hpj⟩ := h1 refine ⟨fun i => if i ≤ j then p i else d.snd, by simp [hp0], fun i hi => ?_, by simp⟩ rcases Nat.lt_or_ge i j with h | h · simp only [show i ≤ j from h.le, show i + 1 ≤ j from h, if_true] exact hp i h · obtain rfl : i = j := by omega right; simpa [hpj] using d.adj exact hsub hy have hcard : ∀ j, min (j + 1) n ≤ (R j).card := by intro j induction j with | zero => have := Finset.card_pos.2 ⟨v, hv⟩ omega | succ j ih => by_cases hj : R j = Finset.univ · have : R (j + 1) = Finset.univ := Finset.eq_univ_of_forall fun y => hmono j (by rw [hj]; exact Finset.mem_univ y) rw [this, Finset.card_univ, Fintype.card_fin]; omega · have := hgrow j hj; omega have hn : 1 ≤ n := Nat.one_le_iff_ne_zero.2 fun h => by subst h; exact v.elim0 have hfull : R (n - 1) = Finset.univ := by apply Finset.eq_univ_of_card have := hcard (n - 1) have hle := Finset.card_le_univ (R (n - 1)) simp only [Fintype.card_fin] at hle ⊢ omega have hu : u ∈ R (n - 1) := by rw [hfull]; exact Finset.mem_univ u simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hu obtain ⟨p, hp0, hp, hpj⟩ := hu refine ⟨fun i => if i ≤ n - 1 then p i else u, by simp [hp0], fun i => ?_, ⟨n - 1, le_rfl, by simp [hpj]⟩⟩ rcases Nat.lt_or_ge i (n - 1) with h | h · simp only [show i ≤ n - 1 from h.le, show i + 1 ≤ n - 1 from h, if_true] exact hp i h · left have h1 : ¬ (i + 1 ≤ n - 1) := by omega simp only [h1, if_false] by_cases h2 : i ≤ n - 1 · obtain rfl : i = n - 1 := by omega simp [hpj] · simp [h2]theorem temporal_connected_visit_list {n : ℕ} (G : ℕ → SimpleGraph (Fin n)) (hG : ∀ t, (G t).Connected) (L : List (Fin n)) : ∀ (t0 : ℕ) (v : Fin n), ∃ w : ℕ → Fin n, w 0 = v ∧ (∀ i, w (i + 1) = w i ∨ (G (t0 + i)).Adj (w i) (w (i + 1))) ∧ ∀ u ∈ L, ∃ j ≤ L.length * (n - 1), w j = u := by induction L with | nil => intro t0 v exact ⟨fun _ => v, rfl, fun _ => Or.inl rfl, fun u hu => absurd hu List.not_mem_nil⟩ | cons a L ih => intro t0 v obtain ⟨q, hq0, hq, j, hj, hqj⟩ := temporal_connected_reach_within G hG t0 v a obtain ⟨p, hp0, hp, hpL⟩ := ih (t0 + j) a refine ⟨fun i => if i ≤ j then q i else p (i - j), by simp [hq0], fun i => ?_, ?_⟩ · rcases Nat.lt_or_ge i j with h | h · simp only [show i ≤ j from h.le, show i + 1 ≤ j from h, if_true] exact hq i · have h1 : ¬ (i + 1 ≤ j) := by omega simp only [h1, if_false] have hpi := hp (i - j) have e1 : i - j + 1 = i + 1 - j := by omega have e2 : t0 + j + (i - j) = t0 + i := by omega rw [e1, e2] at hpi by_cases h2 : i ≤ j · obtain rfl : i = j := by omega simp only [le_refl, if_true, hqj] simpa [hp0] using hpi · simp only [h2, if_false] exact hpi · intro u hu rcases List.mem_cons.1 hu with rfl | hu · refine ⟨j, ?_, by simp [hqj]⟩ rw [List.length_cons] exact le_trans hj (Nat.le_mul_of_pos_left (n - 1) (Nat.succ_pos _)) · obtain ⟨k, hk, hpk⟩ := hpL u hu refine ⟨j + k, by rw [List.length_cons, add_mul, one_mul]; omega, ?_⟩ by_cases hk0 : k = 0 · subst hk0 simp only [Nat.add_zero, le_refl, if_true] rw [hqj, ← hpk, hp0] · have : ¬ (j + k ≤ j) := by omega simp only [this, if_false, Nat.add_sub_cancel_left, hpk]theorem temporal_connected_explore_sq : ∀ (n : ℕ) (G : ℕ → SimpleGraph (Fin n)), (∀ t, (G t).Connected) → ∀ s : Fin n, ∃ w : ℕ → Fin n, w 0 = s ∧ is_temporal_walk G w ∧ temporal_walk_explores_by w ((n - 1) ^ 2) := by classical intro n G hG s obtain ⟨w, hw0, hw, hL⟩ := temporal_connected_visit_list G hG (Finset.univ.erase s).toList 0 s refine ⟨w, hw0, fun t => by simpa using hw t, fun u => ?_⟩ by_cases hu : u = s · exact ⟨0, Nat.zero_le _, hu ▸ hw0⟩ · obtain ⟨j, hj, hwj⟩ := hL u (by simp [hu]) refine ⟨j, le_trans hj ?_, hwj⟩ simp only [Finset.length_toList, Finset.card_erase_of_mem (Finset.mem_univ s), Finset.card_univ, Fintype.card_fin] rw [sq]