Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Integrality and finite termination of the Ford–Fulkerson algorithm

Proved
LinearOptimization.max_flow_ford_fulkerson_integer_termination

by Shuze Chen · Aug 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

ford-fulkersonintegralitymax-flownetwork-flows

(Bertsimas & Tsitsiklis, Theorem 7.8, p. 305) Suppose that all arc capacities uiju_{ij}uij​ are integer or infinite, and that the Ford–Fulkerson algorithm is initialized with an integer flow vector.

Then, the arc flow variables remain integer throughout the algorithm and, if the optimal value is finite, the algorithm terminates after a finite number of steps.

Encoding: (Formalized over the run predicate: every flow in every admissible Ford–Fulkerson run started at an integer feasible flow is integer, and if the maximum flow value is finite, there is no infinite admissible run — for every augmenting-path selection rule.)

Preamble
import Definitions.Def_LinearOptimization_AugmentingPath


open Matrix
open scoped ENNReal

/-- **Bertsimas & Tsitsiklis, Theorem 7.8 (p. 305).** For integer-or-infinite capacities and
an integer initial feasible flow: every flow produced by the
Ford–Fulkerson algorithm is integer, and if the maximum flow value is
finite there is no infinite admissible run — under every
augmenting-path selection rule. -/
Formal statement
theorem LinearOptimization.max_flow_ford_fulkerson_integer_termination {n m : ℕ}
    (arcs : Fin m → Fin n × Fin n) (u : Fin m → ℝ≥0∞) (s t : Fin n)
    (hst : s ≠ t) (hloop : HasNoSelfLoops arcs) (hupos : ∀ k, 0 < u k)
    (huint : ∀ k, u k = ⊤ ∨ ∃ z : ℕ, u k = (z : ℝ≥0∞))
    (f₀ : Fin m → ℝ) (hf₀ : IsFeasibleMaxFlow arcs u s t f₀)
    (hint₀ : ∀ k, ∃ z : ℤ, f₀ k = (z : ℝ)) :
    (∀ f, Relation.ReflTransGen (IsFordFulkersonStep arcs u s t) f₀ f →
      ∀ k, ∃ z : ℤ, f k = (z : ℝ)) ∧
    (maxFlowValue arcs u s t ≠ ⊤ →
      ¬∃ g : ℕ → Fin m → ℝ, g 0 = f₀ ∧
        ∀ i, IsFordFulkersonStep arcs u s t (g i) (g (i + 1))) := by
  sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 7.8, p. 305

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