Proof of `Vertex splitting for the directed flow–cut algorithm` (1st statement)
groundedproofs/Lax263307Proofs/VertexSplitting.lean · lax-263307
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
Compare the certificate's flow value with . A smaller value bounds the cut capacity by , below the chosen large capacity. The cut therefore projects to a nontrivial separation. Its ratio is at most , and the shore and capacity identities give the desired original separator cost. The other branch retains the certificate's feasible high-value split flow.
Attribution
Bonnet–Chang, the two alternatives in the vertex-splitting reduction of Lemma 7.