digraph_apex_over_bidirected_complete_min_cut_le
For every vertex set A of D_d, min(e(A, Aᶜ), e(Aᶜ, A)) ≤ ⌊(d + 1)²/4⌋.
Statement
theorem digraph_apex_over_bidirected_complete_min_cut_le (d : ℕ)
[DecidableRel (digraph_apex_over_bidirected_complete d).Adj] (A : Finset (Fin (d + 2))) :
min (digraph_cut_count (digraph_apex_over_bidirected_complete d) A Aᶜ)
(digraph_cut_count (digraph_apex_over_bidirected_complete d) Aᶜ A) ≤ (d + 1) ^ 2 / 4- Source
- Lemma for digraph_min_cut_additive_bound_fails_for_every_d; arXiv:2610.21381 (Optimally large cuts in both directions), Sec. 6.
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- digraph_min_cut_additive_bound_fails_for_every_dFor 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 ⊔…
The proof, explained
The theorem bounds the minimum cut between any vertex set A and its complement in the digraph D_d by ⌊(d + 1)²/4⌋. The graph consists of a complete bidirected graph on d + 1 vertices together with an apex vertex z = last(d + 1) that has outgoing edges to all other vertices but no incoming edges. Depending on whether z ∈ A or z ∉ A, all edges crossing the cut in one direction form a full Cartesian product between the two sides with z excluded from the target. The cardinalities of the two factors sum to d + 1, so the discrete AM-GM inequality bounds their product by ⌊(d + 1)²/4⌋.
For any natural numbers a and b with a + b = d + 1, the product satisfies a * b ≤ ⌊(d + 1)² / 4⌋
Dividing in ℕ by 4, this is equivalent to 4ab ≤ (a + b)². Casting to integers, this inequality follows directly from the identity (a + b)² - 4ab = (a - b)² ≥ 0.
uses
Nat.le_div_iff_mul_le,sq_nonneghave hab : ∀ a b : ℕ, a + b = d + 1 → a * b ≤ (d + 1) ^ 2 / 4 := by intro a b hab rw [Nat.le_div_iff_mul_le (by norm_num), ← hab] zify nlinarith [sq_nonneg ((a : ℤ) - b)]
The cardinality of A is at most d + 2, and it suffices to consider the cases whether the apex vertex z = last(d + 1) belongs to A or not
The set A is a subset of Fin (d + 2), which has d + 2 elements, so |A| ≤ d + 2. We then split into two cases based on whether the apex vertex z = Fin.last (d + 1) is in A.
have hA : A.card ≤ d + 2 := by simpa using A.card_le_univ by_cases hz : Fin.last (d + 1) ∈ A
If the apex z belongs to A, the directed edges from Aᶜ to A are precisely Aᶜ × (A \ {z})
In the digraph, an edge from u to v exists if and only if u ≠ v and v ≠ z. For any u ∈ Aᶜ and v ∈ A, the condition u ≠ v is automatically satisfied because A and Aᶜ are disjoint. Therefore, an edge exists from u to v if and only if v ≠ z, so the edge set is exactly the Cartesian product Aᶜ × (A \ {z}).
uses
Finset.mem_filter,Finset.mem_product,Finset.mem_compl,Finset.mem_erase· have h1 : (Aᶜ ×ˢ A).filter (fun p => (digraph_apex_over_bidirected_complete d).Adj p.1 p.2) = Aᶜ ×ˢ A.erase (Fin.last (d + 1)) := by ext ⟨u, v⟩ simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_erase] change ((_ ∧ _) ∧ (u ≠ v ∧ v ≠ Fin.last (d + 1))) ↔ _ constructor · rintro ⟨⟨hu, hv⟩, -, hvz⟩ exact ⟨hu, hvz, hv⟩ · rintro ⟨hu, hvz, hv⟩ exact ⟨⟨hu, hv⟩, fun h => hu (h ▸ hv), hvz⟩
If the apex z belongs to A, min(e(A, Aᶜ), e(Aᶜ, A)) ≤ ⌊(d + 1)² / 4⌋
The minimum cut size is at most e(Aᶜ, A), which equals |Aᶜ| · |A \ {z}|. Since z ∈ A, we have |A \ {z}| = |A| - 1 and |A| > 0. The complement has size |Aᶜ| = (d + 2) - |A|. Their sum is ((d + 2) - |A|) + (|A| - 1) = d + 1. By the arithmetic lemma established in the first step, their product is at most ⌊(d + 1)² / 4⌋.
uses
min_le_right,Finset.card_product,Finset.card_erase_of_mem,Finset.card_compl,Fintype.card_fin,Finset.card_pos.2refine (min_le_right _ _).trans ?_ unfold digraph_cut_count rw [h1, Finset.card_product] apply hab rw [Finset.card_erase_of_mem hz, Finset.card_compl, Fintype.card_fin] have := Finset.card_pos.2 ⟨_, hz⟩ omega
If the apex z does not belong to A, the directed edges from A to Aᶜ are precisely A × (Aᶜ \ {z})
For any u ∈ A and v ∈ Aᶜ, disjointness ensures u ≠ v. Thus an edge u → v exists if and only if v ≠ z, meaning v ∈ Aᶜ \ {z}. Consequently, the cut edges from A to Aᶜ form the full Cartesian product A × (Aᶜ \ {z}).
uses
Finset.mem_filter,Finset.mem_product,Finset.mem_compl,Finset.mem_erase· have h1 : (A ×ˢ Aᶜ).filter (fun p => (digraph_apex_over_bidirected_complete d).Adj p.1 p.2) = A ×ˢ Aᶜ.erase (Fin.last (d + 1)) := by ext ⟨u, v⟩ simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_erase] change ((_ ∧ _) ∧ (u ≠ v ∧ v ≠ Fin.last (d + 1))) ↔ _ constructor · rintro ⟨⟨hu, hv⟩, -, hvz⟩ exact ⟨hu, hvz, hv⟩ · rintro ⟨hu, hvz, hv⟩ exact ⟨⟨hu, hv⟩, fun h => hv (h ▸ hu), hvz⟩
If the apex z does not belong to A, min(e(A, Aᶜ), e(Aᶜ, A)) ≤ ⌊(d + 1)² / 4⌋, completing the proof
The minimum is bounded above by e(A, Aᶜ) = |A| · |Aᶜ \ {z}|. Since z ∉ A, we have z ∈ Aᶜ, so |Aᶜ \ {z}| = |Aᶜ| - 1 = (d + 2 - |A|) - 1 = d + 1 - |A|, and |A| ≤ d + 1. The sum of the two factors is |A| + (d + 1 - |A|) = d + 1. Applying the arithmetic lemma, their product is at most ⌊(d + 1)² / 4⌋.
uses
min_le_left,Finset.card_product,Finset.mem_compl.2,Finset.card_erase_of_mem,Finset.card_compl,Fintype.card_fin,Finset.card_lt_univ_of_notMemrefine (min_le_left _ _).trans ?_ unfold digraph_cut_count rw [h1, Finset.card_product] apply hab have hz' : Fin.last (d + 1) ∈ Aᶜ := Finset.mem_compl.2 hz rw [Finset.card_erase_of_mem hz', Finset.card_compl, Fintype.card_fin] have : A.card ≤ d + 1 := by simpa using Finset.card_lt_univ_of_notMem hz omega
Nat.le_div_iff_mul_le- For natural numbers and k > 0, x ≤ y / k is equivalent to x * k ≤ y
sq_nonneg- The square of any element in an ordered ring is non-negative
Finset.mem_filter- An element is in a filtered set if and only if it belongs to the base set and satisfies the predicate
Finset.mem_product- A pair is in the Cartesian product s × t if and only if the first component is in s and the second is in t
Finset.mem_compl- An element belongs to the complement sᶜ if and only if it does not belong to s
Finset.mem_erase- An element belongs to s.erase b if and only if it is in s and distinct from b
min_le_right- The minimum of two elements is at most the second element: min a b ≤ b
min_le_left- The minimum of two elements is at most the first element: min a b ≤ a
Finset.card_product- The cardinality of the Cartesian product of two finite sets is the product of their cardinalities
Finset.card_erase_of_mem- Removing an element that belongs to a finite set decreases its cardinality by 1
Finset.card_compl- The cardinality of the complement of a finite set s in α is the cardinality of α minus the cardinality of s
Fintype.card_fin- The cardinality of the finite type Fin n is n
Finset.card_pos.2- If a finite set contains an element, its cardinality is strictly positive
Finset.mem_compl.2- If an element is not in s, then it is in the complement sᶜ
Finset.card_lt_univ_of_notMem- If an element does not belong to a subset s of a finite type α, then |s| < |α|
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_apex_over_bidirected_complete_min_cut_le (d : ℕ) [DecidableRel (digraph_apex_over_bidirected_complete d).Adj] (A : Finset (Fin (d + 2))) : min (digraph_cut_count (digraph_apex_over_bidirected_complete d) A Aᶜ) (digraph_cut_count (digraph_apex_over_bidirected_complete d) Aᶜ A) ≤ (d + 1) ^ 2 / 4 := by have hab : ∀ a b : ℕ, a + b = d + 1 → a * b ≤ (d + 1) ^ 2 / 4 := by intro a b hab rw [Nat.le_div_iff_mul_le (by norm_num), ← hab] zify nlinarith [sq_nonneg ((a : ℤ) - b)] have hA : A.card ≤ d + 2 := by simpa using A.card_le_univ by_cases hz : Fin.last (d + 1) ∈ A · have h1 : (Aᶜ ×ˢ A).filter (fun p => (digraph_apex_over_bidirected_complete d).Adj p.1 p.2) = Aᶜ ×ˢ A.erase (Fin.last (d + 1)) := by ext ⟨u, v⟩ simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_erase] change ((_ ∧ _) ∧ (u ≠ v ∧ v ≠ Fin.last (d + 1))) ↔ _ constructor · rintro ⟨⟨hu, hv⟩, -, hvz⟩ exact ⟨hu, hvz, hv⟩ · rintro ⟨hu, hvz, hv⟩ exact ⟨⟨hu, hv⟩, fun h => hu (h ▸ hv), hvz⟩ refine (min_le_right _ _).trans ?_ unfold digraph_cut_count rw [h1, Finset.card_product] apply hab rw [Finset.card_erase_of_mem hz, Finset.card_compl, Fintype.card_fin] have := Finset.card_pos.2 ⟨_, hz⟩ omega · have h1 : (A ×ˢ Aᶜ).filter (fun p => (digraph_apex_over_bidirected_complete d).Adj p.1 p.2) = A ×ˢ Aᶜ.erase (Fin.last (d + 1)) := by ext ⟨u, v⟩ simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_erase] change ((_ ∧ _) ∧ (u ≠ v ∧ v ≠ Fin.last (d + 1))) ↔ _ constructor · rintro ⟨⟨hu, hv⟩, -, hvz⟩ exact ⟨hu, hvz, hv⟩ · rintro ⟨hu, hvz, hv⟩ exact ⟨⟨hu, hv⟩, fun h => hv (h ▸ hu), hvz⟩ refine (min_le_left _ _).trans ?_ unfold digraph_cut_count rw [h1, Finset.card_product] apply hab have hz' : Fin.last (d + 1) ∈ Aᶜ := Finset.mem_compl.2 hz rw [Finset.card_erase_of_mem hz', Finset.card_compl, Fintype.card_fin] have : A.card ≤ d + 1 := by simpa using Finset.card_lt_univ_of_notMem hz omega