Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§1.1 — a flow in the Hitchcock network is maximum iff there is no augmenting path

Proved
EdmondsKarp.Scaling.isMaxFlow_iff_no_augPath

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

maximum-flownetwork-flowsp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider a problem on the network of Figure 1 with capacities aia_iai​, bjb_jbj​. A flow fff is a maximum flow if and only if there is no augmenting path relative to fff.

In the scaling method each phase stops when no augmenting path exists; this theorem says that it then holds a maximum flow of that phase's problem.

Preamble
import Mathlib
import Definitions.Def_EdmondsKarp_Scaling_Transport
import Definitions.Def_EdmondsKarp_Scaling_Augmentation
Formal statement
namespace EdmondsKarp.Scaling

/-- §1.1, pp. 249–250, in the network of Figure 1: a flow is maximum if and only if there is no
augmenting path relative to it. -/
theorem isMaxFlow_iff_no_augPath {m n : ℕ} (T : Transport m n) (x : Flow m n) (hx : IsFlow T x) :
    IsMaxFlow T x ↔ ¬ ∃ L : List (Node m n), IsAugPath T x L := by sorry

end EdmondsKarp.Scaling
Source
Edmonds, Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, J. ACM 19(2), 1972, pp. 249–250, §1.1 (unnumbered: 'the flow f is not maximum. It can be shown that, conversely, a flow f in N is not maximum only if there is an augmenting path with respect to f')
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Let m,nm, nm,n be natural numbers, T=(a,b,d)T=(a,b,d)T=(a,b,d) an arbitrary real transport problem with no sign conditions, and xxx an arc function.

Hypothesis. xxx is a flow for TTT, as defined above: nonnegativity, the capacity bounds f0i≤aif_{0i}\le a_if0i​≤ai​ and fj0≤bjf_{j0}\le b_jfj0​≤bj​, and conservation at sss, at each sis_isi​, at each tjt_jtj​, and at ttt.

Conclusion. The following are equivalent:

  • xxx is a maximum flow, i.e. r(y)≤r(x)r(y)\le r(x)r(y)≤r(x) for every flow yyy for TTT;
  • there is no list of nodes that is an augmenting path relative to xxx in TTT.

Here an augmenting path is a list of distinct nodes from sss to ttt whose consecutive pairs all have positive residual capacity. Residual capacity is ai−f0ia_i-f_{0i}ai​−f0i​ on (s,si)(s,s_i)(s,si​), +∞+\infty+∞ on (si,tj)(s_i,t_j)(si​,tj​), bj−fj0b_j-f_{j0}bj​−fj0​ on (tj,t)(t_j,t)(tj​,t), f0if_{0i}f0i​ on (si,s)(s_i,s)(si​,s), fijf_{ij}fij​ on (tj,si)(t_j,s_i)(tj​,si​), fj0f_{j0}fj0​ on (t,tj)(t,t_j)(t,tj​), and 000 for every other pair.

Degenerate cases.

  • If m=0m=0m=0 or n=0n=0n=0, the only flow is zero. It is maximum, no augmenting path exists, and both sides are true.
  • If some ai<0a_i<0ai​<0 or bj<0b_j<0bj​<0, no flow exists and the statement is vacuous.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me