Proof of `Vertex splitting for the directed flow–cut algorithm` (3rd statement)
groundedproofs/Lax263307Proofs/VertexSplitting.lean · lax-263307
What this proof establishes
no assumptions
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
Sum the cut contributions separately for input and output ports. Every output port contributes zero, since no large-capacity arc leaves the cut. An input port contributes exactly its vertex cost when it lies inside and its paired output port lies outside. These are precisely the separator's vertices.
Attribution
Bonnet–Chang, capacity identity in the vertex-splitting reduction of Lemma 7.