AFTD Auto-Formalizing Theoretical Domains

digraph_min_cut_additive_bound_fails_for_every_d

theoremverifiedoriginal

For every d ≥ 2 there is a loopless digraph with minimum outdegree at least d and m = (d + 1)² arcs in which every vertex bipartition A ⊔ B has min(e(A, B), e(B, A)) < ⌈((d − 1)m + d²)/(2(2d − 1))⌉. So the bound of Theorem 1.1 of arXiv:2610.21381 does not hold for all m, for any d (the paper notes this only for d = 2, m = 9).

Statement

theorem digraph_min_cut_additive_bound_fails_for_every_d (d : ℕ) (hd : 2 ≤ d) :
    ∃ (V : Type) (_ : Fintype V) (_ : DecidableEq V) (G : Digraph V) (_ : DecidableRel G.Adj),
      (∀ v, ¬ G.Adj v v) ∧ (∀ v, d ≤ (Finset.univ.filter (G.Adj v)).card) ∧
      digraph_edge_count G = (d + 1) ^ 2 ∧
      ∀ A : Finset V, min (digraph_cut_count G A Aᶜ) (digraph_cut_count G Aᶜ A) <
        ⌈((d - 1 : ℚ) * digraph_edge_count G + d ^ 2) / (2 * (2 * d - 1))⌉₊
Related work
arXiv:2610.21381 (Optimally large cuts in both directions), Theorem 1.1 (the bound ⌈((d − 1)m + d²)/(2(2d − 1))⌉ for all sufficiently large m) and the remark in Sec. 6 that it fails for d = 2, m = 9.
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6

The proof, explained

For any d ≥ 2, the counterexample digraph is formed by adding an apex vertex with in-degree 0 and out-degree d + 1 to a bidirected complete graph on d + 1 vertices, yielding m = (d + 1)² edges and minimum outdegree d. Because the apex receives no edges, the minimum directed cut of any partition is at most ⌊(d + 1)² / 4⌋. This upper bound is strictly smaller than the proposed bound ⌈((d - 1)m + d²)/(2(2d - 1))⌉: for d = 2 this is 2 < ⌈13/6⌉ = 3, and for d ≥ 3 clearing denominators leaves a positive quadratic margin of d² - 2d - 1 > 0.

  1. The graph digraph_apex_over_bidirected_complete d on d + 2 vertices is loopless, has minimum outdegree at least d, and has (d + 1)² edges

    We provide the witness graph on the vertex set Fin (d + 2), which has a directed edge u → v whenever u ≠ v and v is not the last vertex (the apex). The graph is loopless because u ≠ v is required. By digraph_apex_over_bidirected_complete_out_degree, every vertex has outdegree at least d, and by digraph_apex_over_bidirected_complete_edge_count, it has exactly (d + 1)² edges. It remains to show that every cut size is strictly smaller than the bound.

    lines 7–11

    uses digraph_apex_over_bidirected_complete_out_degree, digraph_apex_over_bidirected_complete_edge_count

      letI inst : DecidableRel (digraph_apex_over_bidirected_complete d).Adj := fun u v => by
        unfold digraph_apex_over_bidirected_complete; infer_instance
      refine ⟨Fin (d + 2), inferInstance, inferInstance, digraph_apex_over_bidirected_complete d, inst,
        fun v h => h.1 rfl, digraph_apex_over_bidirected_complete_out_degree d,
        digraph_apex_over_bidirected_complete_edge_count d, fun A => ?_⟩
  2. It suffices to show that ⌊(d + 1)² / 4⌋ < ⌈((d - 1)m + d²) / (2(2d - 1))⌉

    By digraph_apex_over_bidirected_complete_min_cut_le, every vertex partition A ⊔ Aᶜ satisfies min(e(A, Aᶜ), e(Aᶜ, A)) ≤ ⌊(d + 1)² / 4⌋. By transitivity of inequality (lt_of_le_of_lt), it suffices to prove that this upper bound is strictly less than the target ceiling expression.

    line 12

    uses lt_of_le_of_lt, digraph_apex_over_bidirected_complete_min_cut_le

      refine lt_of_le_of_lt (digraph_apex_over_bidirected_complete_min_cut_le d A) ?_
  3. The inequality reduces to ⌊(d + 1)² / 4⌋ * 2(2d - 1) < (d - 1)(d + 1)² + d² in ℚ

    We substitute m = (d + 1)² via digraph_apex_over_bidirected_complete_edge_count and apply Nat.lt_ceil, which equates k < ⌈x⌉ for integers to k < x in ℚ. Since d ≥ 2, the denominator 2(2d - 1) is strictly positive (at least 6), so clearing the denominator via lt_div_iff₀ yields the equivalent rational inequality. We also note the integer division inequality 4 * ⌊(d + 1)² / 4⌋ ≤ (d + 1)² via Nat.mul_div_le.

    lines 13–18

    uses digraph_apex_over_bidirected_complete_edge_count, Nat.lt_ceil, Nat.mul_div_le, lt_div_iff₀

      rw [digraph_apex_over_bidirected_complete_edge_count d, Nat.lt_ceil]
      have hk : 4 * ((d + 1) ^ 2 / 4) ≤ (d + 1) ^ 2 := Nat.mul_div_le _ _
      have hd' : (3 : ℚ) ≤ 2 * d - 1 := by
        have : (2 : ℚ) ≤ d := by exact_mod_cast hd
        linarith
      rw [lt_div_iff₀ (by linarith)]
  4. The inequality holds when d = 2

    We split into cases d = 2 and d > 2 using Nat.eq_or_lt_of_le. For d = 2, the inequality specializes to ⌊9/4⌋ * 2(3) = 2 * 6 = 12 < (1)(9) + 4 = 13, which is verified by direct calculation (norm_num).

    lines 19–20

    uses Nat.eq_or_lt_of_le

      rcases Nat.eq_or_lt_of_le hd with h2 | h3
      · subst h2; norm_num
  5. The inequality holds for all d ≥ 3

    For d ≥ 3, multiplying 4 * ⌊(d + 1)² / 4⌋ ≤ (d + 1)² by 2d - 1 ≥ 0 (via mul_le_mul_of_nonneg_right) gives 4 * ⌊(d + 1)² / 4⌋ * (2d - 1) ≤ (d + 1)² * (2d - 1). Doubling the desired inequality gives 4 * ⌊(d + 1)² / 4⌋ * (2d - 1) < 2(d - 1)(d + 1)² + 2d². The gap between the right-hand side and (d + 1)²(2d - 1) is exactly d² - 2d - 1 = d(d - 2) - 1 ≥ 3(1) - 1 = 2 > 0, which is closed by nonlinear arithmetic (nlinarith).

    lines 21–25

    uses mul_le_mul_of_nonneg_right

      · have hk' : (4 : ℚ) * (((d + 1) ^ 2 / 4 : ℕ) : ℚ) ≤ ((d : ℚ) + 1) ^ 2 := by exact_mod_cast hk
        have h3' : (3 : ℚ) ≤ d := by exact_mod_cast h3
        have hm := mul_le_mul_of_nonneg_right hk' (by linarith : (0 : ℚ) ≤ 2 * d - 1)
        push_cast
        nlinarith
digraph_apex_over_bidirected_complete_edge_count
The number of directed edges in digraph_apex_over_bidirected_complete d is (d + 1)²
digraph_apex_over_bidirected_complete_min_cut_le
For any vertex subset A in digraph_apex_over_bidirected_complete d, min(e(A, Aᶜ), e(Aᶜ, A)) ≤ ⌊(d + 1)² / 4⌋
digraph_apex_over_bidirected_complete_out_degree
In the graph digraph_apex_over_bidirected_complete d, every vertex has outdegree at least d
lt_of_le_of_lt
If a ≤ b and b < c, then a < c
lt_div_iff₀
For a positive divisor c, a < b / c if and only if a * c < b
mul_le_mul_of_nonneg_right
If b ≤ c and 0 ≤ a, then b * a ≤ c * a
Nat.eq_or_lt_of_le
If n ≤ m, then n = m or n < m
Nat.lt_ceil
For a natural number n and a real (or rational) number a, n < ⌈a⌉ if and only if n < a
Nat.mul_div_le
For natural numbers m and n, n * (m / n) ≤ m (integer division)

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_min_cut_additive_bound_fails_for_every_d (d : ℕ) (hd : 2 ≤ d) :    ∃ (V : Type) (_ : Fintype V) (_ : DecidableEq V) (G : Digraph V) (_ : DecidableRel G.Adj),      (∀ v, ¬ G.Adj v v) ∧ (∀ v, d ≤ (Finset.univ.filter (G.Adj v)).card) ∧      digraph_edge_count G = (d + 1) ^ 2 ∧      ∀ A : Finset V, min (digraph_cut_count G A Aᶜ) (digraph_cut_count G Aᶜ A) <        ⌈((d - 1 : ℚ) * digraph_edge_count G + d ^ 2) / (2 * (2 * d - 1))⌉₊ := by  letI inst : DecidableRel (digraph_apex_over_bidirected_complete d).Adj := fun u v => by    unfold digraph_apex_over_bidirected_complete; infer_instance  refine ⟨Fin (d + 2), inferInstance, inferInstance, digraph_apex_over_bidirected_complete d, inst,    fun v h => h.1 rfl, digraph_apex_over_bidirected_complete_out_degree d,    digraph_apex_over_bidirected_complete_edge_count d, fun A => ?_⟩  refine lt_of_le_of_lt (digraph_apex_over_bidirected_complete_min_cut_le d A) ?_  rw [digraph_apex_over_bidirected_complete_edge_count d, Nat.lt_ceil]  have hk : 4 * ((d + 1) ^ 2 / 4) ≤ (d + 1) ^ 2 := Nat.mul_div_le _ _  have hd' : (3 : ℚ) ≤ 2 * d - 1 := by    have : (2 : ℚ) ≤ d := by exact_mod_cast hd    linarith  rw [lt_div_iff₀ (by linarith)]  rcases Nat.eq_or_lt_of_le hd with h2 | h3  · subst h2; norm_num  · have hk' : (4 : ℚ) * (((d + 1) ^ 2 / 4 : ℕ) : ℚ) ≤ ((d : ℚ) + 1) ^ 2 := by exact_mod_cast hk    have h3' : (3 : ℚ) ≤ d := by exact_mod_cast h3    have hm := mul_le_mul_of_nonneg_right hk' (by linarith : (0 : ℚ) ≤ 2 * d - 1)    push_cast    nlinarith
See it in the graphDiscuss this resultChallenge it