AFTD Auto-Formalizing Theoretical Domains

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

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