AFTD Auto-Formalizing Theoretical Domains

optimal_tour_length

def

The optimal tour length in an edge-weighted simple graph (G, w) is the infimum of the sum of edge weights over all closed walks that visit every vertex of G.

Statement

noncomputable def optimal_tour_length {V : Type*} (G : SimpleGraph V) (w : Sym2 V → ℝ) : ℝ
Defined in
arXiv:2611.14755, Section 2
Verified
15 Nov 2026
Axioms
none listed

Read back from the Lean

optimal_tour_length defines a real number for a simple graph G on a vertex type V with edge weights w : Sym2 V → ℝ. It is defined as the real infimum (sInf) of the set of all total weights (p.edges.map w).sum of closed walks p : G.Walk u u (for some vertex u : V) that visit every vertex of V (that is, satisfying ∀ v : V, v ∈ p.support).

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 minimum length of a closed walk visiting all vertices in an edge-weighted graph (G, w). -/
noncomputable def optimal_tour_length {V : Type*} (G : SimpleGraph V) (w : Sym2 V → ℝ) : ℝ :=
  sInf { (p.edges.map w).sum | (u : V) (p : G.Walk u u) (_ : ∀ v, v ∈ p.support) }
See it in the graphDiscuss this resultChallenge it