AFTD Auto-Formalizing Theoretical Domains

fundamental_cut_load

def

The 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 separated by deleting e from T.

Statement

noncomputable def fundamental_cut_load {α : Type*} [Fintype α] [DecidableEq α]
    (H : SimpleGraph α) [DecidableRel H.Adj] (w : Sym2 α → ℕ)
    (T : SimpleGraph α) (e : Sym2 α) : ℕ
Source
step towards weighted_spanning_tree_congestion_hardness_gap
Verified
05 Nov 2026
Axioms
none listed
Used by 1
  • spanning_tree_congestionThe weighted spanning tree congestion of a graph H with edge weights w is the infimum, over all spanning trees T of H, of the…

Lean source view module on GitHub

/-- Weighted load of the fundamental cut of `e` in `T`: the sum of the weights of the `H`-edges crossing the cut induced by deleting `e` from `T`. -/
noncomputable def fundamental_cut_load {α : Type*} [Fintype α] [DecidableEq α]
    (H : SimpleGraph α) [DecidableRel H.Adj] (w : Sym2 α → ℕ)
    (T : SimpleGraph α) (e : Sym2 α) : ℕ := by
  classical
  exact ∑ uv ∈ H.edgeFinset,
    if Sym2.lift ⟨fun u v => ¬ (T.deleteEdges {e}).Reachable u v,
      fun _ _ => propext ⟨fun h hr => h hr.symm, fun h hr => h hr.symm⟩⟩ uv
    then w uv else 0
See it in the graphDiscuss this resultChallenge it