digraph_min_cut_additive_bound_fails_for_every_d
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
- digraph_apex_over_bidirected_completeThe digraph D_d on d + 2 vertices: a bidirected complete graph on the vertices 0, …, d, together with an apex d + 1 that sends an arc to…
- digraph_cut_counte_G(A, B): the number of edges of the digraph G from a vertex of A to a vertex of B.
- digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
- digraph_apex_over_bidirected_complete_edge_countD_d has (d + 1)² arcs.
- digraph_apex_over_bidirected_complete_out_degreeEvery vertex of D_d has outdegree at least d.
- digraph_apex_over_bidirected_complete_min_cut_leFor every vertex set A of D_d, min(e(A, Aᶜ), e(Aᶜ, A)) ≤ ⌊(d + 1)²/4⌋.
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.
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.
uses
digraph_apex_over_bidirected_complete_out_degree,digraph_apex_over_bidirected_complete_edge_countletI 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 => ?_⟩
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.
uses
lt_of_le_of_lt,digraph_apex_over_bidirected_complete_min_cut_lerefine lt_of_le_of_lt (digraph_apex_over_bidirected_complete_min_cut_le d A) ?_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.
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)]
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).
uses
Nat.eq_or_lt_of_lercases Nat.eq_or_lt_of_le hd with h2 | h3 · subst h2; norm_num
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).
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
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.
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