---
title: "Short note: Max-flow min-cut theorem"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:max-flow-min-cut-theorem"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/max-flow-min-cut-theorem
site: BCT Engineering
---

# Short note: Max-flow min-cut theorem

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2075 Bhadra, 4 marks; 2074 Bhadra, 4 marks; 2073 Magh, 4 marks; 2072 Asoj, 4 marks; 2070 Bhadra, 4 marks; 2069 Bhadra, 3 marks (asked 6 times)
- Video: [DM 01 Max Flow and Min Cut Theorem Transport Network Flow Example Solution](https://www.youtube.com/watch?v=a0XlX0NwRhM) — Guru Vidya
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/max-flow-min-cut-theorem
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on Max Flow and Min Cut Theorem.

## Short answer

In any flow network, the maximum flow value from source to sink equals the minimum capacity of an s-t cut. The Ford-Fulkerson method finds it by repeatedly augmenting flow along paths in the residual graph, and when none exist, the reachable vertices form a minimum cut.

## Answer

**Flow network:** a directed graph with a source s, a sink t, and a capacity c(u,v) ≥ 0 on each edge. A **flow** f assigns f(u,v) ≤ c(u,v) to each edge so that, at every vertex other than s and t, flow in = flow out (conservation). Its **value** is the net flow leaving s.

A **cut** (S, T) splits the vertices into S containing s and T containing t. Its **capacity** is the sum of capacities of the edges going from S to T.

**Max-flow min-cut theorem (Ford–Fulkerson):** in any flow network, the maximum value of a flow equals the minimum capacity of a cut.

Why: the flow across any cut is at most its capacity, so max flow ≤ min cut. When no augmenting path exists in the residual graph, the vertices reachable from s form S, every edge S→T is full and every edge T→S is empty, so the flow equals that cut's capacity.

**Ford–Fulkerson method:** start with zero flow; repeatedly find an augmenting path from s to t in the residual graph, push the bottleneck amount along it, and stop when none exists.

**Example:** edges s→a 3, s→b 2, a→b 1, a→t 2, b→t 3.

| Augmenting path | Added flow | Total |
|---|---|---|
| s → a → t | 2 | 2 |
| s → b → t | 2 | 4 |
| s → a → b → t | 1 | 5 |

Now no path remains. Max flow = 5. The cut S = {s}, T = {a, b, t} has capacity 3 + 2 = 5, equal to the flow, so it is a minimum cut.

Uses: network routing, bipartite matching, project scheduling.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does the max-flow min-cut theorem state?
   A. The maximum flow value equals the minimum cut capacity
   B. Max flow is greater than min cut
   C. Max flow equals the sum of all capacities
   D. Min cut equals the number of edges
   Answer: A. Ford and Fulkerson. (Key point: Theorem)

2. How is a cut's capacity computed?
   A. Sum of edges from T to S
   B. Sum of capacities of edges from S to T
   C. Sum of all edges
   D. Number of edges crossing
   Answer: B. Only forward edges count. (Key point: Cut capacity)

3. When does Ford-Fulkerson stop?
   A. After n iterations
   B. When all edges are saturated
   C. When no augmenting path exists in the residual graph
   D. When a path of capacity 0 appears
   Answer: C. Then the reachable set defines a minimum cut. (Key point: Stopping condition)

4. What is the maximum flow in the example?
   A. 5
   B. 3
   C. 8
   D. 6
   Answer: A. The cut {s} vs others has capacity 3 + 2 = 5. (Key point: Example)

## Related in other subjects

- [Define αmax, αmin, insertion loss and gain](https://www.bctengineer.com/question.md?key=semester_5%2Ffilter_design%3Adefine-amax-amin-insertion-loss) — Filter Design, chapter 1, asked 2×
- [Max and min word occurrence with MapReduce](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Amapreduce-max-min-word-occurrence) — Big Data Technologies, chapter 3
- [Informed vs uninformed; min-max; alpha-beta](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ainformed-uninformed-minmax-alphabeta) — Artificial Intelligence, chapter 3
- [Define passband, stopband, αmax, αmin, ωp, ωs](https://www.bctengineer.com/question.md?key=semester_5%2Ffilter_design%3Adefine-passband-stopband-terms) — Filter Design, chapter 1