Proof of `Classical product multicommodity flow–cut bound`
groundedproofs/Lax455465Proofs/ProductFlowCut.lean · lax-455465
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The deterministic algorithm supplies an admissible cut and a feasible arc flow. Public arc-to-path conversion puts its value in the feasible set defining ; the boundedness lemma makes that value at most the supremum. The admissible cut bounds the infimum defining , yielding the classical inequality with the algorithm's same universal approximation constant.