AFTD Auto-Formalizing Theoretical Domains

temporal_connected_explore_sq

theoremverifiedformalization

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.

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

    lines 5–8

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

    lines 9–19

    uses Finset.mem_filter, Finset.mem_univ, true_and, Nat.lt_or_ge, if_true

      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]
  3. 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).

    lines 20–22

    uses Finset.mem_filter, Finset.mem_univ, true_and, Nat.not_lt_zero

      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⟩
  4. 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.

    lines 23–45

    uses Finset.card_lt_card, Finset.mem_filter, Finset.mem_univ, true_and, Nat.lt_or_ge, if_true

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

    lines 46–57

    uses Finset.eq_univ_of_forall, Finset.mem_univ, Finset.card_univ, Fintype.card_fin

      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
  6. 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).

    lines 58–65

    uses Finset.eq_univ_of_card, Finset.card_le_univ, Fintype.card_fin, Finset.mem_univ

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

    lines 66–79

    uses Finset.mem_filter, Finset.mem_univ, true_and, le_rfl, Nat.lt_or_ge, if_true, if_false

      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]
  8. 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.

    lines 86–89

    uses Or.inl, List.not_mem_nil

      induction L with
      | nil =>
        intro t0 v
        exact ⟨fun _ => v, rfl, fun _ => Or.inl rfl, fun u hu => absurd hu List.not_mem_nil⟩
  9. 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.

    lines 90–109

    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 hpi
  10. The 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).

    lines 110–122

    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]
  11. 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.

    lines 128–131

    uses temporal_connected_visit_list

      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 => ?_⟩
  12. 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)².

    lines 132–138

    uses Nat.zero_le, le_trans, Finset.length_toList, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, Fintype.card_fin, sq

      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]
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

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