Max-flow min-cut theorem

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

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 — Use feasibility and net flow value.
• Optimization problem — Distinguish maximum and minimum claims.
• 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.