graph_col
def
The collinear count col(G) of a finite graph G is the number of 3-element subsets {x, y, z} of vertices such that one of the three vertices lies between the other two, i.e., satisfies d(x, y) + d(y, z) = d(x, z).
Statement
open scoped Classical in noncomputable def graph_col {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ
- Defined in
- arXiv:2610.39966 Section 2
- 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
For any finite type V and any simple graph G on V, graph_col G is defined as the number of 3-element subsets s of V for which there exist three pairwise distinct vertices x, y, z ∈ s such that G.dist x y + G.dist y z = G.dist x z (i.e., y lies on a shortest path between x and z with respect to the graph distance G.dist).
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 number of collinear triples col(G) in a finite graph G. -/ noncomputable def graph_col {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ := ((Finset.univ : Finset (Finset V)).filter (fun s => s.card = 3 ∧ ∃ y ∈ s, ∃ x ∈ s, ∃ z ∈ s, x ≠ y ∧ y ≠ z ∧ x ≠ z ∧ G.dist x y + G.dist y z = G.dist x z)).card