AFTD Auto-Formalizing Theoretical Domains

graph_cost

def

For a finite vertex type V with [Fintype V], a pairwise distance function d : V → V → ℝ, and a simple graph T on V, graph_cost d T is defined as (1/2) * ∑ u : V, ∑ v : V, if T.Adj u v then d u v else 0.

Statement

noncomputable def graph_cost {V : Type*} [Fintype V] (d : V → V → ℝ) (T : SimpleGraph V) : ℝ
Defined in
arXiv:2610.23032 Section 4
Verified
20 Oct 2026
Axioms
none listed
Used by 1
  • is_mstA simple graph T on a finite type V is a minimum spanning tree under d : V → V → ℝ if T is a tree (T.IsTree) and graph_cost d T ≤…

Read back from the Lean

Given a finite type V, a cost/weight function d : V → V → ℝ, and a simple graph T : SimpleGraph V, graph_cost d T is defined as half the sum over all ordered pairs of vertices (u, v) : V × V of d u v if u and v are adjacent in T, and 0 otherwise: (1 / 2) * ∑ u : V, ∑ v : V, if T.Adj u v then d u v else 0.

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

/-- The total cost of a graph under distance function d. -/
noncomputable def graph_cost {V : Type*} [Fintype V] (d : V → V → ℝ) (T : SimpleGraph V) : ℝ :=
  letI : DecidableRel T.Adj := Classical.decRel _
  (1 / 2 : ℝ) * ∑ u : V, ∑ v : V, if T.Adj u v then d u v else 0
See it in the graphDiscuss this resultChallenge it