# Max-flow min-cut theorem

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

In a finite capacitated network the largest feasible flow value equals the least capacity among all source–sink cuts.

mko-max-flow-min-cut-theorem · theorem · v0.10.0



## Mathematical statement

Enumerate each vertex subset S containing the source and excluding the sink. Its capacity sums only directed edges from S to its complement; incoming edges are not counted. Every feasible flow value is at most every cut capacity. Complete cut enumeration determines the minimum cut. If a feasible flow and a cut have equal values, this bound immediately certifies both a maximum flow and a minimum cut. An arbitrary feasible flow or single cut is not automatically optimal. This slice does not claim integral flow, an augmenting-path algorithm proof or a general theorem proof from finitely many instances.





## Representative formula (exact TeX)

F(N)=C(N)





## Assumptions


- Use a complete finite directed network with nonnegative exact rational capacities and feasible flows.
- The vertex bound permits complete enumeration of all source–sink cuts.





## Symbol scope


- F — maximum flow value
- N — finite flow network
- C — minimum cut capacity





## Intuition, definition, and misconceptions

Enumerate the complete family of legal source–sink cuts.

Check flow≤cut using capacity and conservation for every cut.

An equal-valued feasible pair supplies both optimality certificates.

Do not add incoming-edge capacity to a cut or infer optimality from an arbitrary feasible flow or cut.





## Adopted derivation guide

[All four cuts and an equal-value two-sided certificate](https://ocme.evemisslab.com/en/derivations/derivation-mko-max-flow-min-cut-theorem-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Finite flow network](https://ocme.evemisslab.com/en/mko/mko-finite-flow-network/) — Use feasibility and net flow value.
- [Optimization problem](https://ocme.evemisslab.com/en/mko/mko-optimization-problem/) — Distinguish maximum and minimum claims.
- [Linear programming](https://ocme.evemisslab.com/en/mko/mko-linear-programming/) — Retain the general theorem background.





## Verification boundary

Finite enumeration certifies only the specified network, not integrality or the correctness of a particular algorithm.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add augmenting paths and Ford–Fulkerson boundaries.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/max-flow-min-cut-theorem.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-max-flow-min-cut-theorem/index.md)