AFTD Auto-Formalizing Theoretical Domains

spanning_tree_congestion

def

The weighted spanning tree congestion of a graph H with edge weights w is the infimum, over all spanning trees T of H, of the maximum load of a fundamental cut of T.

Statement

noncomputable def spanning_tree_congestion {α : Type*} [Fintype α] [DecidableEq α]
    (H : SimpleGraph α) [DecidableRel H.Adj] (w : Sym2 α → ℕ) : ℕ
Source
step towards weighted_spanning_tree_congestion_hardness_gap
Verified
05 Nov 2026
Axioms
none listed
Built on 1
  • fundamental_cut_loadThe load of the fundamental cut of an edge e in a spanning tree T of H: the total w-weight of the edges of H whose endpoints are…

Lean source view module on GitHub

/-- Weighted spanning tree congestion `STC_w(H)`: the infimum of the maximum fundamental-cut load over all spanning trees of `H`, as a natural number. -/
noncomputable def spanning_tree_congestion {α : Type*} [Fintype α] [DecidableEq α]
    (H : SimpleGraph α) [DecidableRel H.Adj] (w : Sym2 α → ℕ) : ℕ := by
  classical
  exact sInf {c : ℕ | ∃ T : SimpleGraph α,
    T ≤ H ∧ T.IsTree ∧ T.edgeFinset.sup (fundamental_cut_load H w T) = c}
See it in the graphDiscuss this resultChallenge it