Further Reading: Network Flow and Matching

Annotated pointers for going deeper. Start with the textbook treatments to firm up the definitions and the max-flow min-cut proof, then branch toward the algorithmics (faster max-flow algorithms), the matching theory (Hall, König, augmenting paths), or the applications (segmentation, scheduling) as your interest pulls you.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), the graph chapters on connectivity and matching. The market-standard discrete-math presentation, with Hall's marriage theorem and bipartite matching at the level of this chapter, plus a large exercise bank. The closest companion to our §34.5 if you want more matching drill.

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), the Maximum Flow chapter. The canonical algorithms reference for everything in §§34.1–34.5: flow networks, the Ford–Fulkerson method, the max-flow min-cut theorem with full proof, the Edmonds–Karp $O(VE^2)$ analysis, and the bipartite-matching reduction. If you read one outside source, read this one — it matches our notation and goes one level deeper on running times.

West, Introduction to Graph Theory (2nd ed.), the chapters on matchings and on network flow. A graph-theorist's treatment: Hall's theorem, König's theorem, and the augmenting-path view of matching (Berge's theorem) developed carefully, then connected to flows. Read this if you want the matching side—rather than the flow side—as the primary lens.

On the duality idea

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the matching/flow material. Freely available. The most CS-flavored development, with the same "model it, then let the algorithm work" spirit as this chapter. Good for re-seeing max-flow min-cut as a first taste of strong duality without the full machinery of linear programming.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the matching section. Freely available. A gentle, example-driven treatment of bipartite matching and Hall's condition. Useful as a slower second pass if §34.5 moved quickly, especially the "deficiency" intuition behind Hall's theorem.

Deeper dives (algorithms and theory)

CLRS (4th ed.), the relabel-to-front / push-relabel material on maximum flow. For readers who want max-flow algorithms faster than Edmonds–Karp: the push-relabel family abandons augmenting paths for a local "preflow" approach and achieves better worst-case bounds. A natural next step after you are comfortable with Ford–Fulkerson.

West, Introduction to Graph Theory (2nd ed.), the section deriving König's and Hall's theorems from flow / from each other. The cleanest place to see the web of equivalences (max-flow min-cut $\Rightarrow$ König $\Rightarrow$ Hall, and back) that Exercises 34.31–34.32 ask you to trace. Worth it if those exercises whetted your appetite for how these classical theorems interlock.

Applications

Graph-cut image segmentation — the "interactive foreground extraction" literature (commonly associated with Boykov–Jolly and with the GrabCut system). (Tier 2 — attributed.) The min-cut segmentation sketched in §34.6 was a workhorse of computer vision. These are the standard references for how per-pixel and smoothness capacities are chosen so that the minimum cut is a good object boundary. Read for the engineering of capacities, not new flow theory.

CLRS (4th ed.), the maximum-bipartite-matching application section. Develops exactly the §34.5 reduction and several application framings (task assignment and scheduling), reinforcing the modeling skill of recognizing flow inside a problem that does not look like plumbing.

Suggested order

  1. Re-read §§34.1–34.4 here, then read the CLRS Maximum Flow chapter for the same material one level deeper (especially the running-time analysis of Edmonds–Karp).
  2. Read the matching sections of West (or Levin, for a gentler pass) alongside §34.5; do Exercises 34.31–34.32 to derive Hall and König from the theorem.
  3. For the duality "aha," read the MIT 6.042 flow/matching notes — they frame max-flow min-cut as your gateway to strong duality.
  4. If algorithms are your draw, finish with the push-relabel material in CLRS; if applications are, read the graph-cut segmentation references.