AFTD Auto-Formalizing Theoretical Domains

tree_routing_cost

def

For any finite type V, type W, simple graph T on V, simple graph H on W, and function f : V → W, tree_routing_cost T H f is the sum over all undirected edges uv of T of the graph distance in H between f(u) and f(v).

Statement

noncomputable def tree_routing_cost {V W : Type*} [Fintype V]
    (T : SimpleGraph V) (H : SimpleGraph W) (f : V → W) : ℕ
Defined in
arXiv:2610.39863, Section 3
Verified
02 Nov 2026
Axioms
none listed
Used by 3
  • tbt_optFor a finite type V and a simple graph T on V, tbt_opt T is the infimum in ℕ of the routing costs tree_routing_cost T H id over all…
  • tbt_opt_eq_sn_opt_of_is_subcubicFor every finite type V with at least two elements and every subcubic tree T on V, tbt_opt T equals tbt_sn_opt T.
  • tbt_sn_optFor a finite type V and a simple graph T on V, tbt_sn_opt T is the infimum in ℕ of the routing costs tree_routing_cost T H f over all…

Read back from the Lean

tree_routing_cost defines a natural number for any types V and W with V finite ([Fintype V]), simple graphs T on V and H on W, and a function f : V → W. It is defined as the sum over all edges e = {u, v} in T.edgeFinset of the graph distance H.dist (f u) (f v) in H between the images of the endpoints under f, lifted to unordered pairs via Sym2.lift.

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 routing cost of a simple graph T on a finite type V in a host graph H under a function f : V → W. -/
noncomputable def tree_routing_cost {V W : Type*} [Fintype V]
    (T : SimpleGraph V) (H : SimpleGraph W) (f : V → W) : ℕ := open Classical in
  ∑ e ∈ T.edgeFinset,
    Sym2.lift ⟨fun u v ↦ H.dist (f u) (f v), fun _ _ ↦ H.dist_comm⟩ e
See it in the graphDiscuss this resultChallenge it