Proof of Theorem 2, p. 403 — for each arc α of a cut D, some chain from a to b meets D in α only
ProvedFordFulkerson56.Planar.exists_chain_meeting_cut_only_atgraph-theorynetwork-flowsp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a network with source and sink , let be a cut of (a disconnecting set no proper subset of which is disconnecting), and let . Then there is a chain joining and which meets in only:
This is the step of the proof of Theorem 2 that uses the minimality of a cut: in that proof it is applied to two arcs of a cut that lie on the same chain. It holds in every network; no planarity is needed.
Preamble
import Mathlib import Definitions.Def_FordFulkerson56_MinCut_Network import Definitions.Def_FordFulkerson56_MinCut_IsChain import Definitions.Def_FordFulkerson56_MinCut_IsDisconnecting
Formal statement
namespace FordFulkerson56.Planar
/-- Proof of Theorem 2, p. 403: since `D` is a cut, for each arc `α ∈ D` there is a chain joining the
source and the sink which meets `D` in `α` only. -/
theorem exists_chain_meeting_cut_only_at {V E : Type*} [Fintype V] [DecidableEq V] [Fintype E]
[DecidableEq E] (N : FordFulkerson56.MinCut.Network V E) (D : Finset E) (hD : FordFulkerson56.MinCut.IsCut N D) (α : E) (hα : α ∈ D) :
∃ C : Finset E, FordFulkerson56.MinCut.IsChain N N.source N.sink C ∧ C ∩ D = {α} := by sorry
end FordFulkerson56.Planar
Source
Ford & Fulkerson, Maximal Flow Through a Network, Canad. J. Math. 8 (1956), p. 403, proof of Theorem 2, sentences beginning "Since D is a cut"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.