AFTD Auto-Formalizing Theoretical Domains

graph_interval_index

def

The interval index of a finite graph G is the sum over all 2-element subsets {u, v} of vertices of |I(u, v)| - 1, where I(u, v) is the interval between u and v consisting of all vertices w with d(u, w) + d(w, v) = d(u, v).

Statement

open scoped Classical in
noncomputable def graph_interval_index {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ
Defined in
arXiv:2610.39966 Section 1
Verified
30 Oct 2026
Axioms
none listed
Used by 1

Read back from the Lean

Definition of graph_interval_index: for a finite type V and a simple graph G : SimpleGraph V, graph_interval_index G is the natural number given by the sum over all 2-element subsets uv of V (i.e., unordered pairs {u, v} of distinct vertices in V) of: (the number of vertices w : V such that for all u, v ∈ uv with u ≠ v, G.dist u w + G.dist w v = G.dist u v) - 1 where subtraction is truncated subtraction on ℕ, and G.dist is the shortest-path distance in G.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

open scoped Classical in
/-- The interval index Int(G) of a finite graph G. -/
noncomputable def graph_interval_index {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ := ∑ uv ∈ (Finset.univ : Finset (Finset V)).filter (·.card = 2),
    ((Finset.univ.filter (fun w => ∀ u ∈ uv, ∀ v ∈ uv, u ≠ v → G.dist u w + G.dist w v = G.dist u v)).card - 1)
See it in the graphDiscuss this resultChallenge it