A Cut Bounds the Flow - Max-Flow, Min-Cut

A cut turns the network into a bottleneck statement: if the source is on one side and the sink is on the other, all source-to-sink flow must cross the boundary. The capacity of that boundary is therefore an upper bound on every feasible flow, regardless of the routing details. This lesson reads that bound on the flagship network.

highlighted = computed this step

Cut partition

A cut places s on one side and t on the other. Think of it as a boundary that any source-to-sink shipment must cross. Why: once the source and sink are separated, every feasible route has to use at least one arc that goes from the source side to the sink side.

S\mid T

Cut capacity

This cut has capacities 2, 1, and 1, summing to 4. Only edges directed from S to T count in the cut capacity. Why: those are the arcs that must carry net flow out of the source side toward the sink side.

c(S,T)=2+{}1+{}1=4

Upper bound

Any feasible flow is at most this cut value, so the flow value 4 cannot exceed it. This is the bottleneck logic in certificate form. Why: no matter how the flow is routed inside the two sides, it cannot cross the boundary through more capacity than the boundary has.

|f|\le c(S,T)

Diagram note

The source-side nodes show the residual-reachable side; the emphasized arcs are the recomputed cut edges. This diagram states an upper bound on every possible flow, not just on the flow currently drawn. Pixel positions are rounded for layout; every number shown is exact.

\text{every cut gives an upper bound}