Exercises: Network Flow and Matching

These build from mechanical flow-checking to full proofs, code, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; do them before you peek.

Throughout, the primary network $M$ is the one from the chapter: vertices $\{s,a,b,t\}$ with $c(s,a)=10,\ c(s,b)=3,\ c(a,b)=4,\ c(a,t)=3,\ c(b,t)=10$. The greedy-trap network $N$ has all five capacities equal to 3: $c(s,a)=c(s,b)=c(a,t)=c(b,t)=c(a,b)=3$.

Part A — Warm-ups (⭐)

34.1 † On network $M$, decide whether each assignment is a valid flow. If not, name the first constraint it breaks. (a) $f(s,a)=4,\ f(s,b)=3,\ f(a,b)=4,\ f(a,t)=0,\ f(b,t)=7$. (b) $f(s,a)=5,\ f(s,b)=2,\ f(a,b)=2,\ f(a,t)=3,\ f(b,t)=4$. (c) $f(s,a)=11,\ f(s,b)=0,\ f(a,b)=4,\ f(a,t)=3,\ f(b,t)=4$.

34.2 For the flow $f(s,a)=7,\ f(s,b)=3,\ f(a,b)=4,\ f(a,t)=3,\ f(b,t)=7$ on $M$, list every saturated edge and compute $\lvert f\rvert$ two ways: as the net flow out of $s$ and as the net flow into $t$. Do they agree?

34.3 † Consider the s–t cut $(S,T)$ of $M$ with $S=\{s,b\}$, $T=\{a,t\}$. List exactly which edges cross from $S$ to $T$, and compute the cut capacity $c(S,T)$. Is this cut a minimum cut? (You may use the chapter's max-flow value of 10.)

34.4 A flow on some network has value 9, and you find an s–t cut of capacity 9. What two facts does this single observation prove at once?

Part B — Compute it (⭐⭐)

34.5 † Run the Ford–Fulkerson method by hand on network $N$, but this time choose your first augmenting path to be $s\to a\to t$ (not the diagonal). Write each iteration: the augmenting path, its bottleneck, and the cumulative value. How many augmenting paths do you need, and do you ever use a back edge? Compare with the chapter's diagonal-first trace.

34.6 Build this network $P$: vertices $\{s,a,b,c,t\}$ with $c(s,a)=4,\ c(s,b)=2,\ c(a,b)=3,\ c(a,c)=1,\ c(b,c)=3,\ c(c,t)=4,\ c(b,t)=1$. Find a maximum flow by hand using shortest augmenting paths (BFS), filling in an iteration table like the one in §34.3. State the final value.

34.7 † For your max flow on $P$ (Exercise 34.6), construct the minimum cut by taking $S$ = the set of vertices reachable from $s$ in the final residual network. List $S$, list the saturated $S\to T$ edges, and verify $c(S,T)$ equals your max-flow value.

34.8 On network $M$, suppose you are allowed to increase the capacity of exactly one edge by 5 units. Which edge should you upgrade to raise the max flow the most, and what is the new max flow? Justify using the min cut, not by re-running the whole algorithm. (Hint: point 3 after the max-flow min-cut proof.)

34.9 † A bipartite graph has parts $X=\{1,2,3,4\}$ and $Y=\{w,x,y,z\}$ with edges $1{-}w,\ 1{-}x,\ 2{-}w,\ 3{-}x,\ 3{-}y,\ 4{-}y,\ 4{-}z$. Find a maximum matching by inspection, then draw the flow network from the §34.5 reduction and state the corresponding max-flow value.

Part C — Prove it (⭐⭐, scaffolded)

34.10 † (Scaffolded — fill in the missing step.) Prove the value-across-a-cut identity used in weak duality: for any flow $f$ and any s–t cut $(S,T)$, $$\lvert f\rvert \;=\; \sum_{u\in S}\sum_{v\in T} f(u,v) \;-\; \sum_{u\in S}\sum_{v\in T} f(v,u).$$ Fill in the blanks. - Start from the definition: $\lvert f\rvert = \sum_{w} f(s,w) - \sum_{u} f(u,s)$, which is the net flow out of $s$. For every other vertex $v\in S$ with $v\neq s$, flow conservation says the net flow out of $v$ is $\underline{\hphantom{xxxx}}$. - Therefore $\lvert f\rvert$ equals the sum, over all $v\in S$, of (flow out of $v$) minus (flow into $v$): $\ \lvert f\rvert = \sum_{v\in S}\Big(\sum_{w} f(v,w) - \sum_{u} f(u,v)\Big)$. - In that double sum, any edge with both endpoints in $S$ contributes $\underline{\hphantom{xxxx}}$ (it is counted once with a $+$ and once with a $-$), so it cancels. The only surviving terms are edges with one endpoint in $S$ and one in $\underline{\hphantom{xx}}$, which gives exactly the claimed difference of cross-cut sums. $\blacksquare$

34.11 Prove that for any flow $f$ on any network, $\lvert f\rvert \le c(s,V\setminus\{s\})$ — i.e., the value never exceeds the total capacity leaving the source. (This is the one-line "source cut" bound from §34.2. Use the value-across-a-cut identity with $S=\{s\}$.)

34.12 † (Scaffolded.) Prove the integrality claim: if every capacity is an integer and Ford–Fulkerson starts from the zero flow, then the flow is integer-valued after every iteration. Fill the blanks for an induction on the number of iterations. - Base case: the zero flow assigns $\underline{\hphantom{xx}}$ to every edge, which is an integer. - Inductive step: assume every $f(u,v)$ is an integer before an iteration. The residual capacities $c_f(u,v) = (c(u,v)-f(u,v)) + f(v,u)$ are then differences and sums of integers, hence $\underline{\hphantom{xxxxx}}$. So the bottleneck $\Delta$ (a minimum of residual capacities) is an integer. Pushing $\Delta$ adds or subtracts an integer on each edge of the path, so every $f(u,v)$ remains $\underline{\hphantom{xxxxx}}$ afterward. $\blacksquare$ - In one sentence, explain why this is exactly what the bipartite-matching reduction (§34.5) relies on.

Part D — Find the error (⭐⭐)

Each argument below is wrong. State precisely which part fails and why.

34.13 † Claim: "I ran the naive greedy method (push on any spare forward path until none remains) on network $N$ and got a flow of value 3 with no augmenting forward path left. By the max-flow min-cut theorem, since no augmenting path remains, 3 is the maximum flow." — Find the flaw. (The true max is 6.)

34.14 Claim: "On network $M$, the cut $S=\{s\}$, $T=\{a,b,t\}$ has capacity $c(s,a)+c(s,b)=10+3=13$. The cut $S=\{s,a,b\}$, $T=\{t\}$ has capacity $c(a,t)+c(b,t)=3+10=13$ as well. Both cuts equal 13, so the max flow is 13." — Find the flaw. (The true max is 10.)

34.15 † Claim: "In the bipartite reduction, give each middle edge $x\to y$ capacity $\infty$ instead of 1 (the source and sink edges stay at capacity 1). The max-flow value still equals the maximum matching size, because the capacity-1 edges at the source already limit each worker to one job." A classmate says this breaks the reduction. Who is right, and why? (Hint: think carefully about whether the recovered flow-carrying middle edges still form a matching.)

34.16 Claim: "Every edge of network $M$ that is saturated by the max flow lies on the minimum cut." The max flow saturates $s\to b$, $a\to b$, $a\to t$, and... let's check $b\to t$ carries 7 of 10, so it is not saturated. So the saturated edges are $s\to b,\ a\to b,\ a\to t$, and these are exactly the min-cut edges, confirming the claim. — Is the claim (saturated $\Rightarrow$ on the min cut) actually true in general? Give a tiny counterexample or argue it holds. (Hint: think about an edge saturated inside $S$.)

Part E — Model it (⭐⭐⭐)

34.17 † (Model it.) A hospital must staff 4 night shifts (Mon–Thu). Five nurses are available; each nurse has listed the shifts they are willing to work: Ana {Mon, Tue}, Ben {Mon}, Cara {Tue, Wed}, Dev {Wed, Thu}, Eli {Thu}. Each shift needs exactly one nurse and each nurse works at most one shift. Model "can every shift be covered?" as a bipartite-matching/max-flow problem: state the two sides, the edges, the source/sink edges and their capacities, and what flow value would mean "all shifts covered." You do not need to solve it numerically.

34.18 (Model it — capacitated.) Reframe Exercise 34.17 so that each nurse may work up to 2 shifts (still one nurse per shift). Exactly which capacities in your flow network change, and to what? Explain in one sentence why this is not a plain matching anymore but is still a max-flow problem.

34.19 † (Model it — segmentation.) You are separating a 4-pixel image (pixels $p_1,p_2,p_3,p_4$ in a row) into foreground and background. Foreground-likelihood gives source capacities $c(s,p_1)=5,\ c(s,p_2)=1,\ c(s,p_3)=1,\ c(s,p_4)=4$; background-likelihood gives sink capacities $c(p_1,t)=1,\ c(p_2,t)=4,\ c(p_3,t)=4,\ c(p_4,t)=1$; each adjacent pair has a smoothness penalty of 2 in both directions. Describe what computing the minimum cut would produce, and which side ($S$ or $T$) is the foreground. (Conceptual — no need to compute the cut.)

Part F — Conjecture and test (⭐⭐⭐)

34.20 † (Conjecture and test, then prove.) Using the chapter's max_flow_value, build the unit-capacity reduction for several small complete bipartite graphs $K_{m,n}$ (every left vertex joined to every right vertex). Compute the maximum matching size for $K_{1,3}, K_{2,3}, K_{3,3}, K_{2,5}$. Conjecture a closed form for the maximum matching size of $K_{m,n}$ in terms of $m$ and $n$, then prove it (one direction is an upper bound from the source/sink edges; the other is an explicit matching).

34.21 (Conjecture and test.) For an integer $k\ge 1$, build the network with vertices $\{s,a,b,t\}$ and capacities $c(s,a)=c(a,t)=c(s,b)=c(b,t)=k$ and a "cross" edge $c(a,b)=k$. Compute the max flow for $k=1,2,3,4$ using the code. Conjecture the max flow as a function of $k$, and prove your formula by exhibiting both a flow of that value and a cut of equal capacity.

34.22 † (Conjecture and test.) It is tempting to believe "doubling every capacity doubles the max flow." Test it: take network $M$, double all five capacities, and compute the new max flow with the code; repeat by tripling. Conjecture the relationship between scaling all capacities by a positive integer $k$ and the max flow, then prove it. (Hint: show $k\cdot f$ is a valid flow and $k\cdot(S,T)$ is the matching cut.)

Part G — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. You may reuse is_valid_flow and max_flow_value from the chapter.

34.23 † Write a function cut_capacity(cap, S) that, given the capacity dictionary and a set S of vertices on the source side, returns the capacity of the cut $(S, V\setminus S)$ — summing $c(u,v)$ only for edges with $u\in S$ and $v\notin S$. Test it on network $M$ with $S=\{$"s","a"$\}$ and confirm it returns 10.

34.24 Write is_saturated(cap, flow) returning the set of edges $(u,v)$ with $f(u,v)=c(u,v)$. Test it on the chapter's max flow for $M$ and report the saturated set.

34.25 † Write min_cut_side(cap, s, t) that returns the set $S$ of vertices reachable from s in the final residual network of Edmonds–Karp (i.e., the source side of a minimum cut). Reuse the residual-graph machinery of max_flow_value, but instead of returning the total, run one final BFS after the loop ends and return the reached set. Test on $M$ and confirm $S=\{$"s","a"$\}$.

34.26 Write matching_edges(left, edges) that, like max_bipartite_matching, builds the reduction but returns the actual list of matched pairs (x, y) — the middle edges carrying one unit of flow — rather than just the count. (Hint: run a flow algorithm that tracks residuals, then a middle edge $x\to y$ is used exactly when its residual dropped to 0, i.e. the reverse residual is 1.) Test on the chapter's worker–task example and report a maximum matching.

Part H — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

34.27 † (Ch. 32 + 34.) Both Kruskal's MST algorithm and Ford–Fulkerson are greedy methods with a correctness theorem. In two or three sentences, state the cut property that certifies Kruskal's choices and the max-flow min-cut certificate for Ford–Fulkerson, and explain the structural analogy: what plays the role of "a cut" in each, and what is being optimized.

34.28 (Ch. 29 + 34.) The BFS inside Edmonds–Karp and Dijkstra's algorithm both grow outward from a source. Explain (a) what each one computes, (b) why Edmonds–Karp uses unweighted BFS rather than Dijkstra even though the network has capacities, and (c) one condition Dijkstra requires of edge weights that BFS does not.

34.29 † (Ch. 27 + 34.) Recall from Chapter 27 that a graph is bipartite iff it has no odd cycle. Suppose someone hands you a graph and asks for a maximum matching via the §34.5 flow reduction, but the graph is not bipartite. Explain why the reduction's correctness argument breaks, and identify the exact step in the "Why it works" proof that fails when the two sides are not well-defined.

34.30 (Ch. 28 + 34.) In Chapter 28 you used BFS to compute "degrees of separation" in a social graph. Now you want the maximum number of edge-disjoint $s$–$t$ paths (a measure of how many independent communication routes survive failures). Argue that this number equals the max flow when every edge is given capacity 1, citing the integrality property. (This is the Chapter 39 Track B "resilience" question previewed in the Project Checkpoint.)

34.31 † (Deep Dive — prove Hall from max-flow min-cut.) Complete the proof of Hall's Marriage Theorem sketched in §34.5. Assume the bipartite graph with parts $X,Y$ has no matching saturating $X$. Build the unit-capacity reduction and let $(S,T)$ be a minimum cut, so $c(S,T) = \lvert f_{\max}\rvert < \lvert X\rvert$. Let $W = X\cap S$ (the left vertices on the source side). Show carefully that $N(W)\subseteq Y\cap S$ and then that $\lvert N(W)\rvert < \lvert W\rvert$, exhibiting a violator of Hall's condition. (Hint: a middle edge from $W$ to $Y\cap T$ would have to be cut, but middle edges have capacity 1 — count what the cut must contain.)

34.32 (Deep Dive.) König's theorem states that in a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover (a smallest set of vertices touching every edge). Using max-flow min-cut on the §34.5 reduction, argue informally why the minimum s–t cut corresponds to a vertex cover of the same size. (You may state, without re-deriving, that the min-cut edges can be replaced by their endpoints in $X$ or $Y$.)

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: a precise statement of what is being proved, correct handling of back edges and cut direction, and a clearly exhibited certificate (a flow and a matching cut) when claiming optimality.