graph_interval_index
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
- graph_interval_index_eq_choose_two_add_colFor every connected finite graph G on n vertices, the interval index Int(G) equals (n choose 2) + col(G).
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)