Proof of `Vertex splitting for the directed flow–cut algorithm` (2nd 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
Uniform weights make the cut demand the product of its shore cardinalities. Clear this positive denominator, substitute the cut-capacity identity, and bound each split shore by twice its projected shore. The two factors of two give the separator bound.
Attribution
Bonnet–Chang, cut ratio estimate in Lemma 7.