digraph_min_cut_eq_half_sum_sub_half_abs_diff
For any two vertex subsets A and B in a finite digraph G, the minimum of the directed cut counts e(A, B) and e(B, A) in ℚ equals half their sum minus half the absolute value of their difference.
Statement
theorem digraph_min_cut_eq_half_sum_sub_half_abs_diff {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (A B : Finset V) : (min (digraph_cut_count G A B : ℚ) (digraph_cut_count G B A : ℚ)) = ((digraph_cut_count G A B : ℚ) + (digraph_cut_count G B A : ℚ)) / 2 - |(digraph_cut_count G A B : ℚ) - (digraph_cut_count G B A : ℚ)| / 2
- Source
- arXiv:2610.21381 Section 5 line 1572
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_cut_counte_G(A, B): the number of edges of the digraph G from a vertex of A to a vertex of B.
Read back from the Lean
For every finite type $V$ with decidable equality, every directed graph $G$ on $V$ with decidable adjacency, and every pair of finite sets $A, B \subseteq V$, the minimum of the cut count from $A$ to $B$ and the cut count from $B$ to $A$ (as rational numbers) is equal to half their sum minus half the absolute value of their difference in $\mathbb{Q}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes the identity min(x, y) = (x + y)/2 - |x - y|/2 for the cut counts x = e(A, B) and y = e(B, A) in ℚ. Because ℚ is totally ordered, either x ≤ y or y ≤ x. In each case, rewriting the minimum and the absolute value reduces the goal to an elementary ring identity verified by polynomial arithmetic.
It suffices to consider the cases e(A, B) ≤ e(B, A) and e(B, A) ≤ e(A, B).
Since the order on ℚ is total (by `le_total`), either e(A, B) ≤ e(B, A) or e(B, A) ≤ e(A, B). The proof splits into these two cases.
uses
le_totalrcases le_total (digraph_cut_count G A B : ℚ) (digraph_cut_count G B A : ℚ) with h | h
The identity holds when e(A, B) ≤ e(B, A).
Under the hypothesis e(A, B) ≤ e(B, A), the minimum min(e(A, B), e(B, A)) simplifies to e(A, B) via `min_eq_left`. By `sub_nonpos.mpr`, the difference e(A, B) - e(B, A) is nonpositive, so `abs_of_nonpos` rewrites its absolute value to -(e(A, B) - e(B, A)). The equation then reduces to e(A, B) = (e(A, B) + e(B, A)) / 2 - -(e(A, B) - e(B, A)) / 2, which holds by elementary ring arithmetic.
uses
min_eq_left,abs_of_nonpos,sub_nonpos.mpr· rw [min_eq_left h, abs_of_nonpos (sub_nonpos.mpr h)] ring
The identity holds when e(B, A) ≤ e(A, B).
Under the hypothesis e(B, A) ≤ e(A, B), the minimum simplifies to e(B, A) via `min_eq_right`. By `sub_nonneg.mpr`, the difference e(A, B) - e(B, A) is nonnegative, so `abs_of_nonneg` rewrites its absolute value to e(A, B) - e(B, A). The equation then reduces to e(B, A) = (e(A, B) + e(B, A)) / 2 - (e(A, B) - e(B, A)) / 2, which again holds by elementary ring arithmetic.
uses
min_eq_right,abs_of_nonneg,sub_nonneg.mpr· rw [min_eq_right h, abs_of_nonneg (sub_nonneg.mpr h)] ring
le_total- In any linear order, for any two elements a and b, either a ≤ b or b ≤ a.
min_eq_left- If a ≤ b, then min(a, b) = a.
abs_of_nonpos- If a ≤ 0, then |a| = -a.
sub_nonpos.mpr- If a ≤ b, then a - b ≤ 0.
min_eq_right- If b ≤ a, then min(a, b) = b.
abs_of_nonneg- If 0 ≤ a, then |a| = a.
sub_nonneg.mpr- If b ≤ a, then 0 ≤ a - b.
- The identity is purely algebraic: it holds for any two elements in a linearly ordered field such as ℚ, and does not rely on any graph-theoretic properties of directed cuts.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- For any vertex subsets A and B in a digraph, min(e(A, B), e(B, A)) = (e(A, B) + e(B, A))/2 - |e(A, B) - e(B, A)|/2. -/theorem digraph_min_cut_eq_half_sum_sub_half_abs_diff {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (A B : Finset V) : (min (digraph_cut_count G A B : ℚ) (digraph_cut_count G B A : ℚ)) = ((digraph_cut_count G A B : ℚ) + (digraph_cut_count G B A : ℚ)) / 2 - |(digraph_cut_count G A B : ℚ) - (digraph_cut_count G B A : ℚ)| / 2 := by rcases le_total (digraph_cut_count G A B : ℚ) (digraph_cut_count G B A : ℚ) with h | h · rw [min_eq_left h, abs_of_nonpos (sub_nonpos.mpr h)] ring · rw [min_eq_right h, abs_of_nonneg (sub_nonneg.mpr h)] ring