In a network, the S-side of a cut sends three forward edges to the T-side with capacities 5, 3, and 7. Two backward edges run from T-side to S-side with capacities 4 and 2. What is the capacity of this cut?
A21 — the sum of all crossing edges in both directions
B15 — the sum of forward edges only (5 + 3 + 7)
C9 — the sum of backward edges, since they limit how much can return
D6 — the minimum capacity among the forward edges
The capacity of a cut is the total capacity of edges directed from S to T — forward edges only. Backward edges (T to S) do not count toward the cut capacity; they can carry flow back from T to S, which would reduce the net flow but does not add to the bottleneck. This is one of the most common errors: including backward edges makes cuts appear larger than they are and breaks the max-flow min-cut equality.
Question 2 Multiple Choice
The Max-Flow Min-Cut Theorem guarantees that for any network with a source and sink:
AThe maximum flow is at most the minimum cut capacity (a one-sided bound)
BThe maximum flow value equals the minimum cut capacity exactly — these two quantities are always the same
CEvery cut has the same capacity as the maximum flow
DThe minimum cut always contains the fewest edges of any cut separating source from sink
The theorem proves exact equality — not just that max flow ≤ min cut (which is easy, the 'weak duality'), but that max flow = min cut. This is the strong result. Option A (one-sided bound) is true but weaker. Option C confuses minimum cut with all cuts. Option D is the classic misconception: minimum cut means minimum total capacity, not fewest edges — a cut with two edges of capacity 100 each has more capacity than one with ten edges of capacity 1 each.
Question 3 True / False
When the Ford-Fulkerson algorithm terminates with no augmenting path remaining, every forward edge from the source-reachable vertex set S to the non-reachable set T in the residual graph must be fully saturated.
TTrue
FFalse
Answer: True
This is the key step in the proof. If any forward edge from S to T were not fully saturated, its residual capacity would be positive, meaning the endpoint in T would be reachable from the source — contradicting the definition of T as the non-reachable set. Full saturation of all S-to-T forward edges (and zero flow on all T-to-S backward edges) is precisely what makes the current flow equal to the capacity of this cut, proving max flow = min cut.
Question 4 True / False
The minimum cut in a network is the cut that separates source from sink using the fewest edges.
TTrue
FFalse
Answer: False
This is the most common misconception about min-cut. The minimum cut minimizes total capacity — the sum of capacities of forward edges crossing the cut — not the number of edges. A single edge with capacity 1000 has more cut capacity than a thousand edges of capacity 1 each. Confusing 'minimum capacity' with 'fewest edges' leads to incorrect identification of bottlenecks and wrong max-flow values.
Question 5 Short Answer
Explain why the Max-Flow Min-Cut Theorem proves that augmenting-path algorithms like Ford-Fulkerson find the true maximum flow when they terminate.
Think about your answer, then reveal below.
Model answer: When no augmenting path remains, define S as all vertices reachable from the source in the residual graph. The sink must be in T = V\S. Every forward edge from S to T is fully saturated (otherwise its endpoint would be reachable), and every backward edge from T to S carries zero flow (otherwise its tail would be reachable). The current flow therefore equals the capacity of this S-T cut exactly. Since any flow ≤ any cut capacity (weak duality), and this flow equals a specific cut capacity, the flow is maximum and this cut is minimum.
The proof is constructive: when Ford-Fulkerson stops, it simultaneously certifies optimality and exhibits a minimum cut. You don't need to check all cuts — the algorithm's termination state defines the min cut for you. This is the power of the theorem: it converts a 'no more augmenting paths' stopping condition into a proof of global optimality.