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.

Read the Lean proof on GitHub

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 maxFlowmaxFlow; the boundedness lemma makes that value at most the supremum. The admissible cut bounds the infimum defining sparsestCutsparsestCut, yielding the classical inequality with the algorithm's same universal approximation constant.