AFTD Auto-Formalizing Theoretical Domains

digraph_both_cuts_ge_ceil_div_six_of_high_indegree

theoremverified

Case 1 of the proof of Theorem 1.4: in a loopless digraph with m arcs, if a vertex z has in-degree at least m/3 + 1 and some set A₀ ∋ z has e(A₀, V∖A₀) ≥ m/6, then some set A has e(A, V∖A) ≥ ⌈m/6⌉ and e(V∖A, A) ≥ ⌈m/6⌉ (keep z and the tails of ⌈m/6⌉ arcs leaving A₀).

Statement

theorem digraph_both_cuts_ge_ceil_div_six_of_high_indegree {V : Type*} [Fintype V]
    [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hloop : ∀ v, ¬ G.Adj v v)
    (z : V) (A₀ : Finset V) (hz : z ∈ A₀)
    (hcut : (digraph_edge_count G : ℚ) / 6 ≤ digraph_cut_count G A₀ A₀ᶜ)
    (hin : (digraph_edge_count G : ℚ) / 3 + 1 ≤
      (Finset.univ.filter fun u => G.Adj u z).card) :
    ∃ 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
arXiv:2610.21381, proof of Theorem 1.4 (Section 5), the case d⁻(z) ≥ m/3 + 1
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The proof chooses a subset C of k = ⌈m/6⌉ edges leaving A₀ and defines A to be {z} ∪ T, where T is the set of tails of C. Since T ⊆ A₀ and z ∈ A₀, all edges of C leave A, guaranteeing that e(A, V \ A) ≥ k. For the reverse cut, the in-degree hypothesis implies that z has at least 2k in-neighbors. Because the digraph has no self-loops, z itself is not an in-neighbor, so at most |T| ≤ k in-neighbors lie in A; the remaining at least k in-neighbors lie in V \ A and each sends an edge to z ∈ A, ensuring e(V \ A, A) ≥ k.

  1. Let m = |E(G)| and k = ⌈m/6⌉; choose a subset C of k edges leaving A₀, and let T be the set of tails of C.

    We define m to be the edge count of G, k to be ⌈m/6⌉, and S to be the set of directed edges leaving A₀. Since |S| ≥ m/6 by assumption, the ceiling property gives k ≤ |S|. Hence there exists a subset C ⊆ S with exactly k edges, and we define T to be the projection of C onto the first component (the set of tails of C).

    lines 9–14

    uses Nat.ceil_le.2, Finset.exists_subset_card_eq

      set m := digraph_edge_count G
      set k := ⌈(m : ℚ) / 6⌉₊
      set S := (A₀ ×ˢ A₀ᶜ).filter fun p => G.Adj p.1 p.2 with hS
      have hkS : k ≤ S.card := Nat.ceil_le.2 hcut
      obtain ⟨C, hCS, hCk⟩ := Finset.exists_subset_card_eq hkS
      set T := C.image Prod.fst
  2. T is a subset of A₀.

    Every vertex u ∈ T is the tail of some edge p ∈ C. Since C ⊆ S and every edge in S originates in A₀, its tail must belong to A₀.

    lines 15–20

    uses Finset.mem_image.1, Finset.mem_filter, Finset.mem_product

      have hTA₀ : T ⊆ A₀ := by
        intro u hu
        obtain ⟨p, hp, rfl⟩ := Finset.mem_image.1 hu
        have := hCS hp
        simp only [hS, Finset.mem_filter, Finset.mem_product] at this
        exact this.1.1
  3. It suffices to show that the candidate set A = {z} ∪ T satisfies e(A, V \ A) ≥ k and e(V \ A, A) ≥ k.

    We instantiate the existential quantifier with A = {z} ∪ T (written insert z T). This produces two subgoals: bounding the forward cut e(A, V \ A) from below by k, and bounding the backward cut e(V \ A, A) from below by k.

    line 21

      refine ⟨insert z T, ?_, ?_⟩
  4. The cut leaving A has at least k edges: e(A, V \ A) ≥ k.

    Since |C| = k, it suffices to show that C is contained in the cut edges from A to V \ A. For any edge p = (u, v) ∈ C, its tail u is in T ⊆ A. Its head v is not in A₀ because p leaves A₀. Since A = {z} ∪ T ⊆ A₀ (as z ∈ A₀ and T ⊆ A₀), v cannot belong to A. Therefore every edge in C crosses from A to V \ A, which implies e(A, V \ A) ≥ |C| = k.

    lines 22–32

    uses Finset.card_le_card, Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_insert, Or.inr, Finset.mem_image_of_mem

      · rw [← hCk]
        unfold digraph_cut_count
        apply Finset.card_le_card
        intro p hp
        have hp' := hCS hp
        simp only [hS, Finset.mem_filter, Finset.mem_product, Finset.mem_compl] at hp'
        simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_insert]
        refine ⟨⟨Or.inr (Finset.mem_image_of_mem _ hp), ?_⟩, hp'.2⟩
        rintro (h | h)
        · exact hp'.1.2 (h ▸ hz)
        · exact hp'.1.2 (hTA₀ h)
  5. The in-neighborhood I of z has cardinality at least 2k.

    Let I be the in-neighborhood of z. The ceiling inequality k < m/6 + 1 implies 2k < m/3 + 2. Combining this with the in-degree hypothesis m/3 + 1 ≤ |I| yields 2k < |I| + 1 over the rationals. For natural numbers, this strict inequality is equivalent to 2k ≤ |I|.

    lines 33–37

    uses Nat.ceil_lt_add_one, Nat.lt_add_one_iff.1

      · set I := Finset.univ.filter fun u => G.Adj u z
        have hk : (k : ℚ) < m / 6 + 1 := Nat.ceil_lt_add_one (by positivity)
        have h2k : 2 * k ≤ I.card := by
          have : ((2 * k : ℕ) : ℚ) < (I.card : ℚ) + 1 := by push_cast; linarith
          exact Nat.lt_add_one_iff.1 (by exact_mod_cast this)
  6. At most k in-neighbors of z lie in A, so |I| ≤ |I \ A| + k.

    We show I ⊆ (I \ A) ∪ T. For any u ∈ I, if u ∉ T, then u cannot equal z because G has no self-loops, so u ∉ {z} ∪ T = A, meaning u ∈ I \ A. Hence |I| ≤ |(I \ A) ∪ T| ≤ |I \ A| + |T|. Since T is the image of C under first projection, |T| ≤ |C| = k, which gives |I| ≤ |I \ A| + k.

    lines 38–52

    uses Finset.mem_union_right, Finset.mem_union_left, Finset.mem_sdiff.2, Finset.mem_insert, Finset.mem_filter.1, Finset.card_le_card, Finset.card_union_le, Finset.card_image_le

        have hIT : I.card ≤ (I \ insert z T).card + k := by
          have h1 : I ⊆ (I \ insert z T) ∪ T := by
            intro u hu
            by_cases huT : u ∈ T
            · exact Finset.mem_union_right _ huT
            · refine Finset.mem_union_left _ (Finset.mem_sdiff.2 ⟨hu, ?_⟩)
              rw [Finset.mem_insert]
              rintro (rfl | h)
              · exact hloop u (Finset.mem_filter.1 hu).2
              · exact huT h
          calc I.card ≤ ((I \ insert z T) ∪ T).card := Finset.card_le_card h1
            _ ≤ (I \ insert z T).card + T.card := Finset.card_union_le _ _
            _ ≤ (I \ insert z T).card + k := by
              have : T.card ≤ C.card := Finset.card_image_le
              omega
  7. The vertices in I \ A provide at least |I \ A| edges from V \ A to A: |I \ A| ≤ e(V \ A, A).

    The map u ↦ (u, z) is injective. For any u ∈ I \ A, u lies in V \ A, z lies in A, and (u, z) is an edge of G because u ∈ I. Thus the image of I \ A under this map is a subset of the cut edges from V \ A to A, proving that |I \ A| ≤ e(V \ A, A).

    lines 53–63

    uses Finset.card_image_of_injective, Prod.mk.inj, Finset.card_le_card, Finset.mem_image.1, Finset.mem_sdiff, Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_insert_self, and_true, Finset.mem_filter.1

        have hD : (I \ insert z T).card ≤ digraph_cut_count G (insert z T)ᶜ (insert z T) := by
          unfold digraph_cut_count
          rw [← Finset.card_image_of_injective _ (fun a b h => (Prod.mk.inj h).1 :
            Function.Injective fun u : V => (u, z))]
          apply Finset.card_le_card
          intro p hp
          obtain ⟨u, hu, rfl⟩ := Finset.mem_image.1 hp
          rw [Finset.mem_sdiff] at hu
          simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl,
            Finset.mem_insert_self, and_true]
          exact ⟨hu.2, (Finset.mem_filter.1 hu.1).2⟩
  8. The cut entering A has at least k edges: e(V \ A, A) ≥ k.

    Combining 2k ≤ |I|, |I| ≤ |I \ A| + k, and |I \ A| ≤ e(V \ A, A) yields e(V \ A, A) ≥ |I| - k ≥ 2k - k = k by linear integer arithmetic, concluding the proof.

    line 64

        omega
Nat.ceil_le.2
If a rational number x is at most a natural number n, then ⌈x⌉ ≤ n.
Finset.exists_subset_card_eq
A finite set with cardinality at least n contains a subset of cardinality exactly n.
Finset.mem_image.1
If an element is in the image f(S), then it equals f(a) for some a ∈ S.
Finset.mem_filter
An element belongs to the filtered set {x ∈ S | P x} if and only if it belongs to S and satisfies P.
Finset.mem_product
A pair (a, b) belongs to the Cartesian product S ×ˢ T if and only if a ∈ S and b ∈ T.
Finset.card_le_card
If S ⊆ T, then |S| ≤ |T|.
Finset.mem_compl
An element belongs to the complement Sᶜ if and only if it does not belong to S.
Finset.mem_insert
An element belongs to {b} ∪ S if and only if it equals b or belongs to S.
Or.inr
If B holds, then A ∨ B holds.
Finset.mem_image_of_mem
If a ∈ S, then f(a) belongs to the image f(S).
Nat.ceil_lt_add_one
For any nonnegative number a, ⌈a⌉ < a + 1.
Nat.lt_add_one_iff.1
For natural numbers, a < b + 1 implies a ≤ b.
Finset.mem_union_right
If a ∈ T, then a ∈ S ∪ T.
Finset.mem_union_left
If a ∈ S, then a ∈ S ∪ T.
Finset.mem_sdiff.2
If a ∈ S and a ∉ T, then a ∈ S \ T.
Finset.mem_filter.1
If an element belongs to {x ∈ S | P x}, then it belongs to S and satisfies P.
Finset.card_union_le
For finite sets S and T, |S ∪ T| ≤ |S| + |T|.
Finset.card_image_le
The image of a finite set under any function has size at most that of the domain: |f(S)| ≤ |S|.
Finset.card_image_of_injective
An injective function on a finite set preserves cardinality: |f(S)| = |S|.
Prod.mk.inj
If two pairs (a, b) and (c, d) are equal, then their first components are equal: a = c.
Finset.mem_sdiff
An element belongs to S \ T if and only if it belongs to S and not to T.
Finset.mem_insert_self
An element a always belongs to {a} ∪ S.
and_true
For any proposition P, the conjunction P ∧ True is equivalent to P.

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_high_indegree {V : Type*} [Fintype V]    [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hloop : ∀ v, ¬ G.Adj v v)    (z : V) (A₀ : Finset V) (hz : z ∈ A₀)    (hcut : (digraph_edge_count G : ℚ) / 6 ≤ digraph_cut_count G A₀ A₀ᶜ)    (hin : (digraph_edge_count G : ℚ) / 3 + 1 ≤      (Finset.univ.filter fun u => G.Adj u z).card) :    ∃ 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  set m := digraph_edge_count G  set k := ⌈(m : ℚ) / 6⌉₊  set S := (A₀ ×ˢ A₀ᶜ).filter fun p => G.Adj p.1 p.2 with hS  have hkS : k ≤ S.card := Nat.ceil_le.2 hcut  obtain ⟨C, hCS, hCk⟩ := Finset.exists_subset_card_eq hkS  set T := C.image Prod.fst  have hTA₀ : T ⊆ A₀ := by    intro u hu    obtain ⟨p, hp, rfl⟩ := Finset.mem_image.1 hu    have := hCS hp    simp only [hS, Finset.mem_filter, Finset.mem_product] at this    exact this.1.1  refine ⟨insert z T, ?_, ?_⟩  · rw [← hCk]    unfold digraph_cut_count    apply Finset.card_le_card    intro p hp    have hp' := hCS hp    simp only [hS, Finset.mem_filter, Finset.mem_product, Finset.mem_compl] at hp'    simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_insert]    refine ⟨⟨Or.inr (Finset.mem_image_of_mem _ hp), ?_⟩, hp'.2⟩    rintro (h | h)    · exact hp'.1.2 (h ▸ hz)    · exact hp'.1.2 (hTA₀ h)  · set I := Finset.univ.filter fun u => G.Adj u z    have hk : (k : ℚ) < m / 6 + 1 := Nat.ceil_lt_add_one (by positivity)    have h2k : 2 * k ≤ I.card := by      have : ((2 * k : ℕ) : ℚ) < (I.card : ℚ) + 1 := by push_cast; linarith      exact Nat.lt_add_one_iff.1 (by exact_mod_cast this)    have hIT : I.card ≤ (I \ insert z T).card + k := by      have h1 : I ⊆ (I \ insert z T) ∪ T := by        intro u hu        by_cases huT : u ∈ T        · exact Finset.mem_union_right _ huT        · refine Finset.mem_union_left _ (Finset.mem_sdiff.2 ⟨hu, ?_⟩)          rw [Finset.mem_insert]          rintro (rfl | h)          · exact hloop u (Finset.mem_filter.1 hu).2          · exact huT h      calc I.card ≤ ((I \ insert z T) ∪ T).card := Finset.card_le_card h1        _ ≤ (I \ insert z T).card + T.card := Finset.card_union_le _ _        _ ≤ (I \ insert z T).card + k := by          have : T.card ≤ C.card := Finset.card_image_le          omega    have hD : (I \ insert z T).card ≤ digraph_cut_count G (insert z T)ᶜ (insert z T) := by      unfold digraph_cut_count      rw [← Finset.card_image_of_injective _ (fun a b h => (Prod.mk.inj h).1 :        Function.Injective fun u : V => (u, z))]      apply Finset.card_le_card      intro p hp      obtain ⟨u, hu, rfl⟩ := Finset.mem_image.1 hp      rw [Finset.mem_sdiff] at hu      simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl,        Finset.mem_insert_self, and_true]      exact ⟨hu.2, (Finset.mem_filter.1 hu.1).2⟩    omega
See it in the graphDiscuss this resultChallenge it