1 / 2 Max Flow, Min Cut & Matching

A Cut As Receipt

Flow network, capacities on the arcs:

s to a capacity 10, s to b capacity 5, a to b capacity 4, a to t capacity 6, b to t capacity 8 sa bt 105 468

An engineer hands you three things: a concrete flow of value 14, the cut S={s,a,b}S = {s, a, b} whose capacity is 14, and a second cut S′={s}S' = {s} whose capacity is 15. What is actually proved?

A

Nothing is proved until all 2V−22^{V-2} cuts have been enumerated and the smallest identified.

B

14 is the maximum. Every cut is an upper bound on every flow, so the capacity-14 cut caps the answer at 14, and the exhibited flow reaches it. The capacity-15 cut only says the answer is at most 15, which the tighter cut already implies.

C

The capacity-14 cut proves the max flow is 14 on its own. Max flow equals min cut, so producing a flow is unnecessary.

D

The two cuts contradict each other, so one of the two capacities was computed wrong.