AFTD Auto-Formalizing Theoretical Domains

digraph_apex_over_bidirected_complete_min_cut_le

theoremverified

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
Used by 1

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

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

    lines 5–9

    uses Nat.le_div_iff_mul_le, sq_nonneg

      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)]
  2. 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.

    lines 10–11

      have hA : A.card ≤ d + 2 := by simpa using A.card_le_univ
      by_cases hz : Fin.last (d + 1) ∈ A
  3. 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}).

    lines 12–21

    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⟩
  4. 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⌋.

    lines 22–28

    uses min_le_right, Finset.card_product, Finset.card_erase_of_mem, Finset.card_compl, Fintype.card_fin, Finset.card_pos.2

        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
  5. 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}).

    lines 29–38

    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⟩
  6. 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⌋.

    lines 39–47

    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_notMem

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

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