Lemma 4 — the triangle dichotomy for mincuts
ProvedMSTCuts2027.Parallel.triangle_cut_dichotomygraph-algorithmsminimum-cutp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1parallel-algorithms
Let be a symmetric real cut function, three vertices, and a -mincut that keeps on the side of . Then exactly one of the following holds:
- , and is an -mincut;
- , and any cut is an -mincut if and only if it is an -mincut.
This is the fact behind EliminateTriangle: one known cut decides which edge of a triangle of can be discarded.
Differences from the source:
- encoding: three vertices, C keeps x on the side of u → x ≠ u, x ≠ v, and (x ∈ C ↔ u ∈ C); reason: x ≠ v follows anyway, and x = u is not a triangle; the cut (C, V∖C) is unoriented, so "side" is membership agreement
Preamble
import Mathlib import Definitions.Def_FlowsNetworks_MultiTerminal_SpanningSubtree import Definitions.Def_MSTCuts2027_Parallel_CutModel
Formal statement
namespace MSTCuts2027.Parallel
/-- Lemma 4: exactly one of the two assertions holds. -/
theorem triangle_cut_dichotomy {V : Type} [Fintype V] [DecidableEq V]
(F : Finset V → ℝ) (hF : IsSymmetricCutFunction F)
(u v x : V) (hxu : x ≠ u) (hxv : x ≠ v) (C : Finset V) (hC : IsMincut F u v C)
(hside : x ∈ C ↔ u ∈ C) :
Xor (lam F x v = lam F u v ∧ IsMincut F x v C)
(lam F x v < lam F u v ∧ ∀ D : Finset V, IsMincut F x v D ↔ IsMincut F x u D) := by sorry
end MSTCuts2027.Parallel
Source
Baswana–Roy, Using MSTs to Compute All-Pairs Mincuts and Beyond ..., STOC 2027 submission #21, pinned preprint SHA-256 faa337be0f0f1bfbbcf924cb3591bd51ded2a6ef2c9e2154e00534a840156a11, Lemma 4, printed p. 6, PDF p. 8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.