Questions: Network Flows and the Max-Flow Min-Cut Theorem

Question 1

Ford-Fulkerson finds an augmenting path and pushes maximum flow along it. A student says: 'Since we push greedily along each path, the first augmenting path we find largely determines the final flow value.' What is wrong with this claim?

• A. Nothing — the first augmenting path always determines the maximum flow
• B. The algorithm only pushes one unit of flow per path, so the first path is irrelevant
• C. The final max-flow value is unique, but backward edges in the residual graph let later augmenting paths reroute flow from suboptimal early choices
• D. Ford-Fulkerson does not use augmenting paths — it finds minimum cuts directly

Answer: (C)

The maximum flow value is unique, but the set of augmenting paths used to reach it is not. Backward edges in the residual graph allow the algorithm to 'undo' flow committed along an earlier suboptimal path by routing flow backward along a previous edge. This rerouting capacity is what guarantees correctness regardless of path-selection order — without backward edges, greedy path selection could get stuck.

Question 2

The capacity of a cut (S, T) in a flow network is defined as:

• A. The sum of capacities of all edges with both endpoints in S or both in T
• B. The sum of capacities of all edges crossing between S and T in either direction
• C. The sum of capacities of edges directed from S to T only — backward edges from T to S are excluded
• D. The minimum capacity among all edges incident to the source s

Answer: (C)

Cut capacity counts only forward edges (S → T), not backward edges (T → S). This asymmetry is essential: flow can only travel from s to t by crossing the cut in the forward direction. Edges going T → S don't constrain the flow — in fact, flow on such edges reduces the net flow across the cut, so they're irrelevant to the upper bound. Forgetting this asymmetry is a common error when computing cut capacities by hand.

Question 3

When Ford-Fulkerson terminates with no remaining augmenting paths, the flow value achieved exactly equals the minimum cut capacity — this is a tight equality, not merely an upper bound.

• T. True
• F. False

Answer: True

True. This is the Max-Flow Min-Cut Theorem. Any cut gives an upper bound on the flow; the minimum cut gives the tightest such bound; and when Ford-Fulkerson terminates, it achieves exactly that value. The vertices reachable from s in the final residual graph form one side of a minimum cut, and the flow through the corresponding forward edges equals their full capacity. The equality is tight — there is no gap between the maximum flow and the minimum cut.

Question 4

Flow conservation requires that total flow in equals total flow out at most vertex in the network, including the source and the sink.

• T. True
• F. False

Answer: False

False. Flow conservation applies at every vertex EXCEPT the source (s) and sink (t). The source has net outflow — flow originates there without arriving — and the sink has net inflow — flow terminates there without leaving. These net amounts are equal and define the value of the flow. Applying conservation to s and t would make any non-zero flow impossible, which is exactly the opposite of the point.

Question 5

Explain why backward edges in the residual graph are necessary, and what would go wrong if Ford-Fulkerson only allowed augmenting paths along forward edges.

Model answer: Backward edges allow the algorithm to reroute previously committed flow. If only forward edges were used, an early suboptimal path choice — for example, routing through an edge that blocks a higher-capacity alternative path — could not be corrected. The algorithm would terminate with a suboptimal flow, unable to reach the true maximum. Backward edges represent residual capacity to 'cancel' flow on an edge, effectively allowing flow to be rerouted through alternative paths, which guarantees the algorithm always converges to the true maximum regardless of path selection order.

The key insight is that backward edges encode the freedom to change your mind. A backward edge of capacity f on edge (u,v) means you can reduce the flow on (u,v) by up to f units — the algorithmic equivalent of rerouting. Without this, Ford-Fulkerson would be a greedy algorithm with no backtracking, and greedy algorithms on network flow problems are provably suboptimal in general. The backward edges are what elevate it from a heuristic to an exact algorithm.