Chapter 26 of 28 · Advanced

Advanced Graph Theory: Bipartite Matching, Maximum Flow and Min-Cut

Advanced Graph Theory and Network Flow

• 25 min read
• Advanced
• Updated 27 Oct 2026
• By Shivam Thakur

26.0 The Question This Chapter Answers

Chapters 11-14 built the foundational graph toolkit: traversal, shortest paths, spanning trees, connectivity. This chapter tackles a genuinely different, higher-level question: given a network with capacity limits on each edge (think: pipes with maximum flow rates, or roads with maximum traffic capacity), what is the maximum amount of "stuff" that can flow from a source to a destination? This is the Maximum Flow problem, and it comes with one of the most beautiful, surprising results in all of graph theory: it is exactly equal to the Minimum Cut — the smallest total capacity of edges that, if removed, would disconnect the source from the destination entirely.

26.1 Bipartite Graphs and Bipartite Matching

26.1.1 What Is a Bipartite Graph?

Definition: A bipartite graph is a graph whose vertices can be divided into two disjoint groups, such that every edge connects a vertex in one group to a vertex in the other — never connecting two vertices within the same group.

Real-Life Analogy: Job Applicants and Job Openings

Picture a graph with job applicants on one side and job openings on the other, with an edge connecting an applicant to every job they're qualified for. This is inherently bipartite — applicants never connect to other applicants, and jobs never connect to other jobs.

Detecting Bipartiteness (A Direct Callback to Chapter 11's BFS)

function isBipartite(graph) {
  const colors = new Map(); // vertex -> 0 or 1 (the two "sides")

  for (const startVertex of graph.getAllVertices()) {
    if (colors.has(startVertex)) continue; // already colored via an earlier component

    colors.set(startVertex, 0);
    const queue = [startVertex]; // Chapter 6/11's BFS queue

    while (queue.length > 0) {
      const current = queue.shift();

      for (const neighbor of graph.getNeighbors(current)) {
        if (!colors.has(neighbor)) {
          colors.set(neighbor, 1 - colors.get(current)); // opposite color from current
          queue.push(neighbor);
        } else if (colors.get(neighbor) === colors.get(current)) {
          return false; // two adjacent vertices have the SAME color -> NOT bipartite!
        }
      }
    }
  }

  return true;
}

26.1.2 Bipartite Matching: The Job-Assignment Problem

Definition: A matching in a bipartite graph is a set of edges with no shared endpoints — in the job-applicant analogy, each matched edge represents one applicant assigned to one job, with no applicant or job used twice. Maximum Bipartite Matching finds the largest such set.

The Augmenting Path Algorithm (A Direct Preview of This Chapter's Central Technique)

function maxBipartiteMatching(leftVertices, graph) {
  const matchRight = new Map(); // right-side vertex -> the left-side vertex it's matched to

  function tryMatch(leftVertex, visited) {
    for (const rightVertex of graph.getNeighbors(leftVertex)) {
      if (visited.has(rightVertex)) continue;
      visited.add(rightVertex);

      // If rightVertex is unmatched, OR we can find an ALTERNATIVE match for
      // whoever it's currently matched to (freeing it up for leftVertex) -- take it!
      if (!matchRight.has(rightVertex) || tryMatch(matchRight.get(rightVertex), visited)) {
        matchRight.set(rightVertex, leftVertex);
        return true;
      }
    }
    return false;
  }

  let matchCount = 0;
  for (const leftVertex of leftVertices) {
    if (tryMatch(leftVertex, new Set())) {
      matchCount++;
    }
  }

  return matchCount;
}

26.2 Maximum Flow: The Ford-Fulkerson Method

26.2.1 The Setup: Flow Networks

Definition: A flow network is a directed graph where each edge has a capacity (the maximum flow it can carry), with a designated source vertex (where flow originates) and sink vertex (where flow terminates). The Maximum Flow problem asks for the greatest total flow rate achievable from source to sink, without exceeding any edge's capacity.

ASCII Visualization

           10        5
      S -------> A -------> T
      |                     ^
      |          15         |
      +--------> B ---------+
                       10

S = source, T = sink (target)
Capacities shown on each edge. What's the MAXIMUM total flow from S to T?

26.2.2 The Core Idea: Augmenting Paths and Residual Graphs

Definition: The Ford-Fulkerson method repeatedly finds an augmenting path — any path from source to sink with available (unused) capacity along every edge — and pushes as much additional flow as that path's bottleneck (its minimum remaining capacity) allows, updating a residual graph that tracks remaining capacity (and, crucially, "undo" capacity in the reverse direction) after each push.

26.2.3 Full Implementation Using BFS (Edmonds-Karp Variant)

function maxFlow(graph, source, sink, numVertices) {
  // graph: adjacency matrix representation, graph[u][v] = capacity from u to v (0 if no edge)
  const residual = graph.map(row => [...row]); // deep copy — this WILL be mutated

  function bfsFindAugmentingPath() {
    const parent = new Array(numVertices).fill(-1);
    const visited = new Array(numVertices).fill(false);
    const queue = [source];
    visited[source] = true;

    while (queue.length > 0) {
      const current = queue.shift(); // Chapter 6/11's BFS, again!

      for (let next = 0; next < numVertices; next++) {
        if (!visited[next] && residual[current][next] > 0) {
          visited[next] = true;
          parent[next] = current;
          queue.push(next);

          if (next === sink) return parent; // found a path to the sink!
        }
      }
    }

    return null; // no augmenting path exists — we're DONE
  }

  let totalFlow = 0;

  while (true) {
    const parent = bfsFindAugmentingPath();
    if (parent === null) break;

    // Find the BOTTLENECK: the minimum residual capacity along the found path
    let pathFlow = Infinity;
    let node = sink;
    while (node !== source) {
      const prev = parent[node];
      pathFlow = Math.min(pathFlow, residual[prev][node]);
      node = prev;
    }

    // Update the residual graph: subtract forward, ADD backward (the "undo" mechanism!)
    node = sink;
    while (node !== source) {
      const prev = parent[node];
      residual[prev][node] -= pathFlow;
      residual[node][prev] += pathFlow; // THE CRUCIAL REVERSE EDGE UPDATE
      node = prev;
    }

    totalFlow += pathFlow;
  }

  return totalFlow;
}

Dry Run (Using the Network From Section 26.2.1)

S=0, A=1, B=2, T=3
Capacities: S->A=10, S->B=15, A->T=5, B->T=10

BFS finds path S->A->T (bottleneck = min(10,5) = 5)
  residual[S][A] -= 5 -> 5.  residual[A][S] += 5 -> 5.
  residual[A][T] -= 5 -> 0.  residual[T][A] += 5 -> 5.
  totalFlow = 5

BFS finds path S->B->T (bottleneck = min(15,10) = 10)
  residual[S][B] -= 10 -> 5.  residual[B][S] += 10 -> 10.
  residual[B][T] -= 10 -> 0.  residual[T][B] += 10 -> 10.
  totalFlow = 15

BFS looks for another path: S->A has 5 remaining, but A->T is now 0 (and A->B doesn't
exist in this simple example) -- no augmenting path found via A. S->B has 5 remaining,
but B->T is now 0. NO AUGMENTING PATH EXISTS.

Final totalFlow = 15 (matches the intuitive maximum: S can send at most 10+15=25 out,
but T can only receive at most 5+10=15 in, so 15 is indeed the true bottleneck-limited max)

26.3 The Max-Flow Min-Cut Theorem: A Genuinely Beautiful Result

Definition: A cut in a flow network is a partition of vertices into two groups, one containing the source and the other containing the sink. The capacity of a cut is the sum of capacities of edges crossing from the source's group to the sink's group. The Max-Flow Min-Cut Theorem states that the maximum possible flow from source to sink is exactly equal to the minimum possible cut capacity.

Real-World Applications Worth Naming Unprompted

• Bipartite matching (section 26.1.2) is directly solvable as a max flow problem: connect a super-source to every left vertex (capacity 1 each), every right vertex to a super-sink (capacity 1 each), and the original bipartite edges (capacity 1 each) — the max flow equals the maximum matching size, a genuinely elegant unification of two seemingly separate techniques into one.
• Network reliability/bottleneck analysis: identifying the min cut in a computer network or supply chain reveals exactly which connections, if disrupted, would most severely limit total throughput — directly actionable for infrastructure investment decisions.
• Image segmentation (a computer vision application): pixels as vertices, similarity as edge capacity, min cut separates an image into foreground/background regions.
• Project selection with dependencies ("maximum weight closure" problems): a genuinely clever reduction of certain optimization problems into a min-cut computation.

26.4 Edge Cases and Gotchas Checklist

1. Disconnected source and sink. Verify your max flow implementation correctly returns 0 if no path exists at all.
2. Self-loops or parallel edges in the flow network. Verify your adjacency matrix representation handles these correctly (self-loops typically contribute nothing useful and should be ignored or given zero effective capacity).
3. Forgetting the reverse residual edge update — this is, without exaggeration, the single most common and most severe bug in Ford-Fulkerson implementations, silently producing an incorrect (too-low) max flow value, since the algorithm loses its ability to "undo" suboptimal early choices.
4. Using DFS instead of BFS for augmenting path finding without realizing the complexity implications — always default to BFS (Edmonds-Karp) unless you have a specific reason and have verified the graph's structure won't trigger DFS's pathological slow case.
5. Integer vs. floating-point capacities — verify your bottleneck (Math.min) calculations behave correctly if capacities aren't guaranteed to be integers.
6. Directed vs. undirected flow networks — an undirected edge with capacity c is typically modeled as two directed edges (each direction, capacity c), not capacity c shared between both directions; verify this distinction matches your specific problem's intent.

26.5 Chapter Summary

This chapter extended Chapters 11-14's graph foundations into genuinely advanced territory, opening with bipartite graphs — detected via Chapter 11's BFS combined with a two-coloring test, and provably equivalent to the graph containing no odd-length cycles — and bipartite matching, whose augmenting-path algorithm ("displace the current match, recursively check if it can find an alternative, then take the freed slot") turned out to be the exact conceptual seed of this chapter's central technique, not a separate, unrelated idea.

We built Maximum Flow around the Ford-Fulkerson method: repeatedly find an augmenting path with available capacity, push flow equal to its bottleneck, and update a residual graph. We gave extended, careful attention to the single most commonly misunderstood detail in the entire algorithm: every forward flow push must be accompanied by an equal "undo" capacity added in the reverse direction, without which the algorithm would have no mechanism to reconsider an earlier suboptimal routing choice — directly echoing Chapter 20's lesson that naive, purely greedy, "never look back" strategies aren't automatically correct, and that a genuine correctness guarantee requires the specific mechanism (here, reverse residual edges) that allows revision. We distinguished the general Ford-Fulkerson method from its specific, standard Edmonds-Karp implementation (using BFS, directly reusing Chapter 6/11's queue-based traversal, to find augmenting paths), noting the provable O(VE²) bound this specific choice guarantees, versus the general method's potentially problematic dependence on the actual flow value's magnitude when a poorer path-finding strategy is used.

We closed with the Max-Flow Min-Cut Theorem — a genuinely beautiful, surprising result stating that the maximum achievable flow is always exactly equal to the network's narrowest bottleneck (the minimum cut separating source from sink), not merely bounded by it, and that this minimum cut can be recovered for free once max flow terminates, simply by checking residual reachability from the source. We closed with a survey of real-world applications worth naming unprompted in an interview: bipartite matching reduces directly to a max flow computation (a genuinely elegant unification of two techniques covered in the same chapter), alongside network reliability analysis, image segmentation, and project-selection-with-dependencies problems — demonstrating that this chapter's techniques, while among the most mathematically sophisticated in the book, have correspondingly wide, genuinely practical real-world reach.

26.6 Revision Notes

• Bipartite graphs are detected via Chapter 11's BFS combined with two-coloring; equivalent to containing no odd-length cycles.
• Bipartite matching's augmenting-path algorithm ("displace and recursively re-match") is the conceptual seed of this chapter's central max-flow technique, not a separate idea.
• Ford-Fulkerson repeatedly finds an augmenting path, pushes flow equal to its bottleneck, and updates a residual graph — the reverse residual edge update is non-negotiable, providing the "undo" mechanism that makes the algorithm correct rather than a potentially-wrong greedy heuristic.
• Edmonds-Karp is the specific, standard implementation using BFS for augmenting-path finding, guaranteeing O(VE²) — a critical refinement over the unspecified general Ford-Fulkerson method.
• The Max-Flow Min-Cut Theorem: maximum flow always exactly equals the minimum cut capacity — not just an upper bound, but always achievable, and recoverable for free via residual reachability once max flow terminates.
• Bipartite matching reduces directly to a max flow computation via a super-source/super-sink construction — a genuine unification of this chapter's two halves.

26.7 Mind Map (ASCII)

                  ADVANCED GRAPH THEORY & NETWORK FLOW
                                  |
      +------------------+-------+-------+------------------------+
      |                  |               |                        |
  BIPARTITE           MAXIMUM FLOW    RESIDUAL GRAPH          MAX-FLOW
  GRAPHS              (Ford-Fulkerson) & REVERSE EDGES        MIN-CUT THEOREM
      |                    |               |                       |
  Two-coloring test    Augmenting path: Every forward push    Max flow EXACTLY
  (Ch.11 BFS) =        find path with   needs a reverse       equals min cut
  equivalent to        available        "undo" edge -- THE    capacity (narrowest
  "no odd cycles"      capacity, push   #1 correctness         bottleneck)
      |                bottleneck       requirement (echoes         |
  Bipartite            flow                  Ch.20: naive      NOT just a bound
  MATCHING:                |             greedy isn't          -- ALWAYS
  augmenting-path      Edmonds-Karp =    automatically         ACHIEVABLE
  algorithm            SPECIFIC impl.    correct without a          |
  ("displace &         using BFS         revision mechanism)   Find min cut FREE:
  re-match")           (Ch.6/11 queue)        |                BFS/DFS from source
  = SEED of this        -> O(V*E^2)      Ford-Fulkerson =      using residual
  chapter's max-        guaranteed       the GENERAL method,   capacity; reachable
  flow technique        bound            unspecified path-      = source side
      |                                  finding strategy            |
  REDUCES TO MAX                                               Applications:
  FLOW via super-                                              bipartite matching,
  source/super-sink                                            network reliability,
  construction!                                                image segmentation,
  (unifies both                                                project selection
  halves of chapter)

26.8 Cheat Sheet

BIPARTITE GRAPH DETECTION
=============================
Two-color via BFS (Ch.11): if any edge connects two same-colored vertices -> NOT bipartite
Equivalent fact: bipartite <=> no odd-length cycles

BIPARTITE MATCHING (AUGMENTING PATH)
========================================
For each left vertex, try to match it to an unmatched right neighbor.
If all neighbors are taken, try to DISPLACE one (recursively re-match its
current partner to a DIFFERENT vertex) -- if successful, take the freed slot.

MAX FLOW (FORD-FULKERSON / EDMONDS-KARP)
============================================
while an augmenting path (source to sink, available capacity) exists:
    bottleneck = MIN residual capacity along the path
    for each edge (u,v) on the path:
        residual[u][v] -= bottleneck    <- forward: use up capacity
        residual[v][u] += bottleneck    <- REVERSE: add "undo" capacity (CRITICAL!)
    totalFlow += bottleneck
return totalFlow

Ford-Fulkerson (general method): path-finding strategy unspecified, can be O(E*maxFlow) worst case
Edmonds-Karp (BFS-specific):     O(V*E^2) GUARANTEED -- the standard, safe choice

MAX-FLOW MIN-CUT THEOREM
============================
max flow == min cut capacity (ALWAYS, exactly, not just an upper bound)
Find min cut for FREE after max flow completes:
  BFS/DFS from source using only edges with remaining residual capacity
  Reachable vertices = source side. Unreachable = sink side.
  Cut edges = original edges crossing from reachable to unreachable.

APPLICATIONS
===============
Bipartite matching = max flow (super-source -> left, capacity 1 each;
                                right -> super-sink, capacity 1 each;
                                original edges, capacity 1 each)
Network reliability, image segmentation, project selection (max weight closure)

26.9 Key Takeaways

1. Bipartite graphs are detected via two-coloring (Chapter 11's BFS) and are equivalent to having no odd-length cycles.
2. Bipartite matching's "displace and recursively re-match" augmenting-path technique is the direct conceptual seed of maximum flow, not a separate idea.
3. The residual graph's reverse "undo" edges are non-negotiable for Ford-Fulkerson's correctness — without them, the algorithm can't revise an earlier suboptimal choice.
4. Edmonds-Karp (BFS-based augmenting paths) guarantees O(VE²), a critical, specific refinement over the unspecified general Ford-Fulkerson method.
5. The Max-Flow Min-Cut Theorem states these two quantities are always exactly equal, not just bounded — and the min cut is recoverable for free via residual reachability.

26.10 20 Multiple Choice Questions

26.11 20 Coding Problems

Easy

1. Implement isBipartite from memory (section 26.1.1), and test it on both a bipartite and a non-bipartite (odd-cycle-containing) graph.
2. Write a function to construct a simple flow network (adjacency matrix) from a list of edges with capacities.
3. Implement a function to find the bottleneck (minimum capacity) along a given path in a flow network.
4. Given a flow network, write a function to verify that a claimed flow assignment respects every edge's capacity constraint.
5. Implement a simple BFS-based path existence checker for a residual graph (a helper for the full max flow algorithm).

Medium

6. Implement maxBipartiteMatching from memory (section 26.1.2), and verify it against a small hand-constructed job-assignment example.
7. Implement the full maxFlow (Edmonds-Karp) function from memory (section 26.2.3), and verify against the book's dry run.
8. Given a completed max flow computation, implement a function to find the min cut (the specific edges) using residual-graph reachability.
9. Given a bipartite graph representing students and elective courses (each student can take one course, each course has one slot), use max flow to determine the maximum number of students that can be assigned.
10. Implement a function to verify the Max-Flow Min-Cut theorem empirically: compute max flow and min cut independently on the same network, and confirm they're equal.

Hard

11. Given a network with multiple sources and multiple sinks, adapt the max flow algorithm using a "super-source" and "super-sink" construction (connecting all sources/sinks with infinite-capacity edges) to find the maximum total flow.
12. Implement "Minimum Vertex Cover" for a bipartite graph using König's theorem (a genuinely elegant result stating that in bipartite graphs, the minimum vertex cover size equals the maximum matching size), building on your bipartite matching implementation.
13. Given a flow network where edges also have MINIMUM required flow (not just maximum capacity), describe (with a simplified implementation) how the max flow algorithm would need to be adapted to handle this "lower bound" constraint.
14. Implement a project-selection ("maximum weight closure") solver: given projects with profits/costs and dependencies, use a min-cut reduction to determine the optimal subset of projects to undertake.
15. Given a large bipartite graph (e.g., thousands of applicants and jobs), benchmark your max-flow-based matching solution against the direct augmenting-path bipartite matching algorithm (section 26.1.2), discussing when each approach is preferable.

Interview Level

16. (Google-level) Given a data center network with bandwidth capacities between servers, use max flow to determine the maximum sustainable data transfer rate between two specific servers, and use min cut to identify the specific network links that would need upgrading to increase capacity.
17. (Amazon-level) Given a warehouse-to-customer delivery network with capacity constraints on each route segment, use max flow to determine the maximum number of packages deliverable per day, and discuss how this informs logistics infrastructure investment decisions.
18. (Microsoft-level) Given a task-assignment system where employees have varying skill sets (bipartite: employees to tasks) and each task can be assigned to exactly one employee, use max flow to find the maximum number of tasks that can be staffed, and discuss handling employees who can do multiple tasks.
19. (Meta-level) Given a content moderation queue distribution problem (moderators to content types, bipartite, each moderator can handle multiple content types up to a capacity limit), extend the standard bipartite matching to a capacitated flow problem and solve it with max flow.
20. (Netflix-level) Design a content delivery network (CDN) capacity planning tool: given server-to-region bandwidth capacities, use max flow to determine the maximum total content delivery rate to a specific region, and use the min-cut result to identify and report the exact bottleneck links limiting further scaling.

26.12 5 Interview Questions

1. "How would you determine if a graph is bipartite?" (Tests the two-coloring BFS technique and the odd-cycle equivalence.)
2. "Implement maximum bipartite matching, and explain the core idea behind your algorithm." (Tests the augmenting-path/displacement technique specifically.)
3. "Implement the Ford-Fulkerson algorithm for maximum flow, and explain why the residual graph needs reverse edges." (Tests both implementation and the critical correctness detail.)
4. "What is the Max-Flow Min-Cut theorem, and how would you find the actual min cut once you've computed max flow?" (Tests the theorem itself and the free min-cut-recovery technique.)
5. "How does bipartite matching relate to maximum flow?" (Tests the unifying reduction connecting both halves of this chapter.)

26.13 3 Real Projects

1. Complete Flow Algorithm Library: Implement bipartite graph detection, bipartite matching, and Edmonds-Karp maximum flow (with min-cut recovery) in a single library, with a self-check script verifying the Max-Flow Min-Cut theorem holds across randomized test networks.
2. Job Assignment Optimizer: Build a tool that takes a list of job applicants with their qualifications and a list of job openings with requirements, models it as a bipartite graph, and uses max flow to find the maximum number of successful assignments, reporting the specific matches made.
3. Network Bottleneck Analyzer: Build a tool that takes a network topology with bandwidth capacities, computes the maximum flow between any two specified nodes, and reports the specific min-cut edges — directly useful for identifying which network links would most improve throughput if upgraded.

26.14 Further Reading

• L.R. Ford Jr. and D.R. Fulkerson's original 1956 paper introducing the max flow method bearing their names.
• Jack Edmonds and Richard Karp's 1972 paper establishing the BFS-based polynomial-time bound for the algorithm bearing their names.
• Search "König's theorem bipartite graphs" for the elegant minimum-vertex-cover result mentioned in coding problem #12.
• Jon Kleinberg and Éva Tardos, Algorithm Design, chapter on network flow, for the definitive, rigorous treatment of max flow applications, including project selection and image segmentation.
• LeetCode's and competitive programming resources' "Network Flow" and "Bipartite Matching" problem sets, for extensive additional practice.