Chapter I, Corollary 5.4 — unions and intersections of minimal cuts are minimal cuts
ProvedFlowsNetworks.MaxFlow.minimal_cuts_union_interLet be a network with nonnegative capacities and let . If and are minimal cuts separating and , then
are also minimal cuts.
So the source sides of minimal cuts form a lattice under union and intersection; in particular there is a smallest and a largest one, which Theorem 5.5 identifies.
Formalization Note The book's "two distinguished nodes" are assumed distinct (). Cuts are given by their node sets.
import Mathlib import Definitions.Def_FlowsNetworks_MaxFlow_Network
namespace FlowsNetworks.MaxFlow
/-- Ford–Fulkerson, *Flows in Networks*, Chapter I, Corollary 5.4 (p. 23): if `(X, X̄)` and
`(Y, Ȳ)` are minimal cuts, then `(X ∪ Y, (X ∪ Y)‾)` and `(X ∩ Y, (X ∩ Y)‾)` are also minimal
cuts. -/
theorem minimal_cuts_union_inter {N : Type} [Fintype N] [DecidableEq N]
(G : Network N) (s t : N) (hst : s ≠ t) (X Y : Finset N)
(hX : IsMinCut G s t X) (hY : IsMinCut G s t Y) :
IsMinCut G s t (X ∪ Y) ∧ IsMinCut G s t (X ∩ Y) := by sorry
end FlowsNetworks.MaxFlow
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let be a finite node type with decidable equality, and let be a network on :
- arc set of ordered pairs with no loops;
- capacity with on arcs.
Let with . For a node set , the cut capacity is
is a minimal cut if , , and for every with and .
Conclusion. If and are both minimal cuts, then and are both minimal cuts.
Degenerate cases.
- If , the statement is immediate.
- If is empty, every set containing and not has capacity and is a minimal cut. The union and intersection again contain and not .
- has at least two elements.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.