AFTD Auto-Formalizing Theoretical Domains

is_mst

def

A 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 ≤ graph_cost d T' for every tree T' on V.

Statement

def is_mst {V : Type*} [Fintype V] (d : V → V → ℝ) (T : SimpleGraph V) : Prop
Defined in
arXiv:2610.23032 Section 4
Verified
20 Oct 2026
Axioms
none listed
Built on 1
  • graph_costFor 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…

Read back from the Lean

Given a finite type $V$, a function $d : V \to V \to \mathbb{R}$, and a simple graph $T$ with vertices in $V$, is_mst d T asserts that: 1. $T$ is a tree (T.IsTree), and 2. For every simple graph $T'$ on $V$, if $T'$ is a tree (T'.IsTree), then the cost of $T$ under $d$ (graph_cost d T) is less than or equal to the cost of $T'$ under $d$ (graph_cost d T').

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

/-- A simple graph is a minimum spanning tree if it is a tree and minimizes graph_cost. -/
def is_mst {V : Type*} [Fintype V] (d : V → V → ℝ) (T : SimpleGraph V) : Prop :=
  T.IsTree ∧ ∀ T' : SimpleGraph V, T'.IsTree → graph_cost d T ≤ graph_cost d T'
See it in the graphDiscuss this resultChallenge it