Proof of Theorem 1, p. 639 — the null circulation is the unique extreme circulation
ProvedSendSplit.Existence.extreme_circulation_iff_eq_zerograph-theorynetwork-flowsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a graph (arcs join distinct nodes) and a circulation in . Then is extreme, i.e. its induced subgraph is a forest, if and only if
This is used in Theorem 1 to pass from 3° to 2°: an extreme minimum-cost circulation must be the null circulation.
Formalization Note Forests are over arcs: a nonzero circulation on a pair of antiparallel arcs induces a 2-cycle and is not extreme.
Preamble
import Mathlib import Definitions.Def_SendSplit_Existence_Network
Formal statement
namespace SendSplit.Existence
theorem extreme_circulation_iff_eq_zero {n : ℕ} (G : ArcGraph n) (x : Fin n → Fin n → ℝ)
(hx : IsCirculation G x) :
IsExtremeFlow G (fun _ => 0) x ↔ x = 0 := by sorry
end SendSplit.Existence
Source
Erickson, Monma, Veinott, Send-and-Split Method for Minimum-Concave-Cost Network Flows, Math. Oper. Res. 12 (1987), p. 639, proof of Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.