AFTD Auto-Formalizing Theoretical Domains

digraph_both_cuts_ge_ceil_div_six_of_two_partitions

theoremverified

If two vertex partitions have combined crossing count at least m and combined absolute directed-cut imbalance at most m/3, one partition has both directed cut counts at least the natural ceiling of m/6.

Statement

theorem digraph_both_cuts_ge_ceil_div_six_of_two_partitions {V : Type*} [Fintype V]
    [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (A₀ A₁ : Finset V)
    (htotal : (digraph_edge_count G : ℚ) ≤
      (digraph_cut_count G A₀ A₀ᶜ : ℚ) + digraph_cut_count G A₀ᶜ A₀ +
      digraph_cut_count G A₁ A₁ᶜ + digraph_cut_count G A₁ᶜ A₁)
    (hbalance : |(digraph_cut_count G A₀ A₀ᶜ : ℚ) - digraph_cut_count G A₀ᶜ A₀| +
      |(digraph_cut_count G A₁ A₁ᶜ : ℚ) - digraph_cut_count G A₁ᶜ A₁| ≤
        (digraph_edge_count G : ℚ) / 3) :
    ∃ A : Finset V, ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G A Aᶜ ∧
      ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G Aᶜ A
Source
Helper for digraph_both_cuts_ge_ceil_div_six_of_indegree_lt, arXiv:2610.21381, proof of Theorem 1.4, Case 2. The two-partition certificate and paired-outcome inequality are a deterministic formulation of the paper's averaging argument; no research advance is claimed.
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The proof establishes the algebraic identity 2 * min(a, b) = a + b - |a - b| to express the smaller directed cut of a partition in terms of its total cut size and imbalance. Summing this identity over both partitions gives 2 * min(x, y) + 2 * min(u, v) = (x + y + u + v) - (|x - y| + |u - v|) ≥ m - m/3 = 2m/3. Consequently, at least one of the two partitions must satisfy min(cut₁, cut₂) ≥ m/6, which immediately implies that both directed cuts for that partition are at least ⌈m/6⌉₊.

  1. Introduce shorthand notation for the four directed cut counts.

    Define the rational numbers x and y as the directed cut counts between A₀ and its complement in each direction, and u and v as the corresponding directed cut counts for A₁.

    lines 11–14

      let x : ℚ := digraph_cut_count G A₀ A₀ᶜ
      let y : ℚ := digraph_cut_count G A₀ᶜ A₀
      let u : ℚ := digraph_cut_count G A₁ A₁ᶜ
      let v : ℚ := digraph_cut_count G A₁ᶜ A₁
  2. For any two rational numbers a and b, 2 * min(a, b) = a + b - |a - b|.

    By totality of the order (le_total), either a ≤ b or b ≤ a. If a ≤ b, the minimum is a (min_eq_left), and because a - b ≤ 0 (sub_nonpos.mpr), its absolute value is -(a - b) (abs_of_nonpos); ring arithmetic then simplifies a + b - -(a - b) to 2 * a. The symmetric case b ≤ a follows identically using min_eq_right, sub_nonneg.mpr, and abs_of_nonneg.

    lines 15–20

    uses le_total, min_eq_left, abs_of_nonpos, sub_nonpos.mpr, min_eq_right, abs_of_nonneg, sub_nonneg.mpr

      have hmin (a b : ℚ) : 2 * min a b = a + b - |a-b| := by
        rcases le_total a b 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
  3. At least one of the two partitions satisfies m/6 ≤ min(cut₁, cut₂), where m is the edge count of G.

    Assume for contradiction that both min(x, y) < m/6 and min(u, v) < m/6. Then 2 * min(x, y) + 2 * min(u, v) < 2 * (m/3). Using the identity from the previous step, this sum equals (x + y + u + v) - (|x - y| + |u - v|). Since the total crossing edges satisfy x + y + u + v ≥ m and the total imbalance satisfies |x - y| + |u - v| ≤ m/3, the sum must be at least m - m/3 = 2m/3, producing a contradiction via linear arithmetic (linarith).

    lines 21–29

      have hgood : (digraph_edge_count G : ℚ) / 6 ≤ min x y ∨
          (digraph_edge_count G : ℚ) / 6 ≤ min u v := by
        by_contra h
        push_neg at h
        have h₀ := hmin x y
        have h₁ := hmin u v
        change (digraph_edge_count G : ℚ) ≤ x+y+u+v at htotal
        change |x-y| + |u-v| ≤ (digraph_edge_count G : ℚ)/3 at hbalance
        linarith
  4. There exists a vertex partition with both directed cut counts at least ⌈m/6⌉₊.

    Case split on which partition achieves the lower bound. If m/6 ≤ min(x, y), choose A₀; since the minimum is bounded above by each component (min_le_left, min_le_right), m/6 ≤ x and m/6 ≤ y, so by the ceiling property (Nat.ceil_le.mpr), ⌈m/6⌉₊ ≤ x and ⌈m/6⌉₊ ≤ y. If instead m/6 ≤ min(u, v), the identical argument applied to A₁ shows both u and v are at least ⌈m/6⌉₊.

    lines 30–36

    uses Nat.ceil_le.mpr, min_le_left, min_le_right

      rcases hgood with h | h
      · refine ⟨A₀, Nat.ceil_le.mpr ?_, Nat.ceil_le.mpr ?_⟩
        · exact h.trans (min_le_left x y)
        · exact h.trans (min_le_right x y)
      · refine ⟨A₁, Nat.ceil_le.mpr ?_, Nat.ceil_le.mpr ?_⟩
        · exact h.trans (min_le_left u v)
        · exact h.trans (min_le_right u v)
le_total
In a linear order, any two elements are comparable: 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.
Nat.ceil_le.mpr
For a rational q and a natural number n, if q ≤ n then ⌈q⌉₊ ≤ n.
min_le_left
For any elements a and b, min(a, b) ≤ a.
min_le_right
For any elements a and b, min(a, b) ≤ 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

theorem digraph_both_cuts_ge_ceil_div_six_of_two_partitions {V : Type*} [Fintype V]    [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (A₀ A₁ : Finset V)    (htotal : (digraph_edge_count G : ℚ) ≤      (digraph_cut_count G A₀ A₀ᶜ : ℚ) + digraph_cut_count G A₀ᶜ A₀ +      digraph_cut_count G A₁ A₁ᶜ + digraph_cut_count G A₁ᶜ A₁)    (hbalance : |(digraph_cut_count G A₀ A₀ᶜ : ℚ) - digraph_cut_count G A₀ᶜ A₀| +      |(digraph_cut_count G A₁ A₁ᶜ : ℚ) - digraph_cut_count G A₁ᶜ A₁| ≤        (digraph_edge_count G : ℚ) / 3) :    ∃ A : Finset V, ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G A Aᶜ ∧      ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G Aᶜ A := by  let x : ℚ := digraph_cut_count G A₀ A₀ᶜ  let y : ℚ := digraph_cut_count G A₀ᶜ A₀  let u : ℚ := digraph_cut_count G A₁ A₁ᶜ  let v : ℚ := digraph_cut_count G A₁ᶜ A₁  have hmin (a b : ℚ) : 2 * min a b = a + b - |a-b| := by    rcases le_total a b 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  have hgood : (digraph_edge_count G : ℚ) / 6 ≤ min x y ∨      (digraph_edge_count G : ℚ) / 6 ≤ min u v := by    by_contra h    push_neg at h    have h₀ := hmin x y    have h₁ := hmin u v    change (digraph_edge_count G : ℚ) ≤ x+y+u+v at htotal    change |x-y| + |u-v| ≤ (digraph_edge_count G : ℚ)/3 at hbalance    linarith  rcases hgood with h | h  · refine ⟨A₀, Nat.ceil_le.mpr ?_, Nat.ceil_le.mpr ?_⟩    · exact h.trans (min_le_left x y)    · exact h.trans (min_le_right x y)  · refine ⟨A₁, Nat.ceil_le.mpr ?_, Nat.ceil_le.mpr ?_⟩    · exact h.trans (min_le_left u v)    · exact h.trans (min_le_right u v)
See it in the graphDiscuss this resultChallenge it