---
title: "Network Flow and the Max-Flow Min-Cut Theorem"
description: "Flow pushes as much as possible from a source to a sink without exceeding any edge's capacity. Augmenting paths in a residual graph find the maximum, and the theorem says that maximum equals the cheap"
canonical: https://lightmysky.com/learn/computing/network-flow-and-the-max-flow-min-cut-theorem-mt_momRV9lK1n
source: https://lightmysky.com/learn/computing/network-flow-and-the-max-flow-min-cut-theorem-mt_momRV9lK1n.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Network Flow and the Max-Flow Min-Cut Theorem

Flow pushes as much as possible from a source to a sink without exceeding any edge's capacity. Augmenting paths in a residual graph find the maximum, and the theorem says that maximum equals the cheapest set of edges whose removal disconnects the two.

Subject: Computing · Area: Algorithms & Data Structures · Ages 21 to 22
Page: https://lightmysky.com/learn/computing/network-flow-and-the-max-flow-min-cut-theorem-mt_momRV9lK1n

## Ready when they can

- Find a maximum flow by repeatedly augmenting along paths in the residual graph
- Identify the minimum cut and check its capacity equals the flow
- Model bipartite matching as a flow problem and read the matching off the answer

## Lesson: Push water, find the bottleneck

After cheapest routes, the next puzzle is how much can travel at once. A flow network pushes as much as possible from a source to a sink without exceeding any edge's capacity. You keep pushing along paths with leftover room until no such path remains.

**Example.** Edges from the source hold 4 and 3, and edges into the sink hold 3 and 5. Pushing carefully moves 7 units in total. The cheapest edge set whose removal disconnects source from sink also costs 7. Maximum flow equals minimum cut, every time.

The residual graph is your working map: it shows remaining room forward and undo room backward. Each augmenting path adds its bottleneck amount. When no path is left, the flow is maximum and the reached nodes mark the minimum cut.

To match workers to jobs, build a flow network: source to each worker, edges for who can do what, each job to the sink, every capacity 1. Run the flow and read the matching off the used middle edges.

**Recap.** Augment along leftover room until none remains, and the flow you pushed equals the cheapest cut.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Shortest Paths with Negative Weights and Between All Pairs](https://lightmysky.com/learn/computing/shortest-paths-with-negative-weights-and-between-all-pairs-mt_e8szFezaxO)
- [Breadth-First and Depth-First Search](https://lightmysky.com/learn/computing/breadth-first-and-depth-first-search-mt_q8IEzoBhzy)

## Opens up

- [Matchings and Hall's Theorem](https://lightmysky.com/learn/mathematics/matchings-and-halls-theorem-mt_hkWslW5b5U)
- [Reductions: Solving One Problem by Turning It into Another](https://lightmysky.com/learn/computing/reductions-solving-one-problem-by-turning-it-into-another-mt_PAwby3ZyAr)
- [Linear Programming, Duality and Rounding](https://lightmysky.com/learn/computing/linear-programming-duality-and-rounding-mt_rsj6G8iydV)