Questions: Network Flows: Maximum Flow and Minimum Cut

Question 1

You find a flow in a network with value 12. You also identify a cut of capacity 12. What can you conclude?

• A. The flow might be improvable; you need to keep running Ford-Fulkerson
• B. The flow is maximum and the cut is minimum — each is a certificate proving the other
• C. The cut capacity gives a lower bound, so the maximum flow could be higher than 12
• D. You have confirmed the flow is feasible, but optimality requires checking all cuts

Answer: (B)

By the max-flow min-cut theorem, maximum flow = minimum cut capacity. Finding a flow of value 12 and a cut of capacity 12 simultaneously certifies both: the flow cannot be improved (every cut gives an upper bound, and this cut equals 12), and no cut smaller than 12 exists (a flow of 12 was achieved, so every cut must be at least 12). The two together constitute a proof of optimality requiring no further computation.

Question 2

What is the purpose of backward edges in the residual graph during Ford-Fulkerson?

• A. They represent unused capacity in the original forward direction
• B. They allow the algorithm to undo and reroute earlier flow assignments that turned out to be suboptimal
• C. They indicate edges where the original graph allows bidirectional flow
• D. They are only generated when the source and sink are disconnected

Answer: (B)

A backward edge with capacity f(e) on an edge where f(e) units of flow have been sent allows the algorithm to 'cancel' up to f(e) units of that earlier flow — effectively rerouting it along a different path. Without backward edges, Ford-Fulkerson could get stuck with suboptimal local routing and fail to reach the true maximum. Backward edges are what allow the algorithm to correct greedy decisions made in earlier iterations.

Question 3

In a flow network, a cut of small capacity provides a lower bound on the maximum possible flow.

• T. True
• F. False

Answer: False

Cuts provide upper bounds, not lower bounds. Every cut separates source from sink, so every unit of flow must cross the cut — meaning the flow value cannot exceed the cut capacity. A minimum cut gives the tightest upper bound, which by the max-flow min-cut theorem equals the maximum flow. A valid flow of known value provides a lower bound.

Question 4

When Ford-Fulkerson terminates — finding no augmenting path in the residual graph — the current flow value is guaranteed to equal the capacity of some cut in the network.

• T. True
• F. False

Answer: True

When no augmenting path exists, the set of nodes reachable from the source in the residual graph forms set S of a cut (S, T). The edges from S to T in the original graph are all fully saturated (no residual capacity forward), and this cut's capacity equals the current flow value. This is the constructive proof of the max-flow min-cut theorem: termination of Ford-Fulkerson and the min-cut condition are the same event.

Question 5

Why is the max-flow min-cut theorem described as providing a 'certificate of optimality'? What two things does it simultaneously produce, and why does that matter?

Model answer: It simultaneously produces (1) a flow achieving the maximum value and (2) a cut proving that no larger flow is possible. The flow is the constructive witness; the cut is the impossibility proof. Together they certify optimality without requiring exhaustive search — you don't need to check all possible flows, because the cut proves that the achieved value is an upper bound, and the flow proves that upper bound is attained.

This duality is computationally valuable: you can verify a maximum flow in polynomial time just by exhibiting a cut of equal capacity. It also unifies matching and flow problems — a maximum bipartite matching and its certificate of optimality (Hall's condition violation) correspond exactly to a max flow and its min cut.