AFTD Auto-Formalizing Theoretical Domains

digraph_min_cut_eq_half_sum_sub_half_abs_diff

theoremverified

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.

  1. 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.

    line 8

    uses le_total

      rcases le_total (digraph_cut_count G A B : ℚ) (digraph_cut_count G B A : ℚ) with h | h
  2. 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.

    lines 9–10

    uses min_eq_left, abs_of_nonpos, sub_nonpos.mpr

      · rw [min_eq_left h, abs_of_nonpos (sub_nonpos.mpr h)]
        ring
  3. 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.

    lines 11–12

    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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it