Theorem 1, 6° ⇒ 5° — minimum-cost chains to force nonnegative circuit slopes
ProvedSendSplit.Existence.six_implies_fiveLet be a graph with arc cost functions and limiting right-derivatives (slopeAtInfty). Suppose condition 6° of Theorem 1 holds: for every set containing exactly one node of each sink strong component of and no other node, and every choice of the arc costs of the augmented graph ( inside strong components, arbitrary reals on arcs joining distinct strong components and on the appended arcs ), there is a minimum-cost chain (of real cost) to from each node of . Then condition 5° holds:
This is the implication 6° ⇒ 5° of Theorem 1, closing the equivalence of the circuit condition 5° and the shortest-chain test 6°.
Formalization Note. Chains are walks (lists of nodes of , none standing for ) and may repeat nodes; costs live in (EReal); "minimum-cost" means attained, with real cost.
import Mathlib import Definitions.Def_SendSplit_Existence_Network import Definitions.Def_SendSplit_Existence_AugmentedGraph
namespace SendSplit.Existence
theorem six_implies_five {n : ℕ} (G : ArcGraph n) (c : Fin n → Fin n → ℝ → ℝ)
(h6 : ∀ S, IsSinkSelection G S → ∀ (b : Fin n → Fin n → ℝ) (bν : Fin n → ℝ),
∀ u, HasMinCostChain G S (augCost G c b bν) u) :
∀ C, IsSimpleCircuit G C → 0 ≤ ∑ p ∈ C, slopeAtInfty (c p.1 p.2) := by sorry
end SendSplit.Existence