AFTD Auto-Formalizing Theoretical Domains

digraph_packing_free_cut_peeling_bound

theoremverified

If a set of at least r−m+1 vertices contains no q disjoint directed cycles, while every nonempty induced digraph of minimum outdegree m contains q cycles and all vertices of the set have global outdegree at least r, at least (r−m+1)(r−m+2)/2 arcs leave the set.

Statement

theorem digraph_packing_free_cut_peeling_bound
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (r m q : ℕ) (hm : m ≤ r) (B : Finset α) (hB : r - m + 1 ≤ B.card)
    (hdeg : ∀ v ∈ B, r ≤ (Finset.univ.filter fun w => D.Adj v w).card)
    (hcriterion : ∀ T : Finset α, T.Nonempty →
      (∀ v ∈ T, m ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ c : Fin q → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j)))
    (hno : ¬ ∃ c : Fin q → Finset α,
      (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j))) :
    (r - m + 1) * (r - m + 2) / 2 ≤
      ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card
Source
Peeling reduction for the minimum-counterexample campaign route to OP-110; experiments 12598 and 12602 check the resulting degree and partition arithmetic.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
Used by 3

The proof, explained

Because B contains no q disjoint directed cycles, the given cycle-packing criterion guarantees that every nonempty subset T ⊆ B contains a vertex with induced out-degree strictly less than m. By an inductive peeling argument (in516_peel), we can select an ordered sequence of n = r - m + 1 distinct vertices s₀, ..., s_{n-1} ∈ B such that each s_j has at most m + j - 1 out-neighbors in B. Since every vertex in B has total out-degree at least r, vertex s_j must send at least r - (m + j - 1) = n - j arcs outside of B. Summing these cut bounds over all j using the triangular sum identity (in516_triangular_sum) proves that at least n(n + 1)/2 = (r - m + 1)(r - m + 2)/2 arcs leave B.

  1. The sum ∑_{j=0}^{r-1} (r - j) indexed over Fin r equals the finset sum ∑_{k ∈ [0, r)} (r - k).

    We rewrite the sum indexed over Fin r into a sum over the range {0, ..., r-1} using Finset.sum_fin_eq_sum_range, and simplify the conditional summand since every index k in the range satisfies k < r.

    lines 3–9

    uses Finset.sum_fin_eq_sum_range, Finset.sum_congr, Finset.mem_range

      have h1 : (∑ j : Fin r, (r - (j:ℕ))) = ∑ k ∈ Finset.range r, (r - k) := by
        rw [Finset.sum_fin_eq_sum_range]
        refine Finset.sum_congr rfl ?_
        intro k hk
        simp only [Finset.mem_range] at hk
        simp [hk]
      rw [h1]
  2. Reversing the summation indices shows ∑_{k=0}^{r-1} (r - k) = ∑_{k=0}^{r-1} (k + 1).

    Using Finset.sum_range_reflect, the terms k + 1 are reflected to (r - 1 - k) + 1. Linear arithmetic confirms that r - k = r - 1 - k + 1 for all k < r.

    lines 10–17

    uses Finset.sum_range_reflect, Finset.sum_congr, Finset.mem_range

      have h2 : ∑ k ∈ Finset.range r, (r - k) = ∑ k ∈ Finset.range r, (k + 1) := by
        have := Finset.sum_range_reflect (fun k => k + 1) r
        rw [← this]
        refine Finset.sum_congr rfl ?_
        intro k hk
        simp only [Finset.mem_range] at hk
        omega
      rw [h2]
  3. The triangular sum evaluates to r(r + 1)/2, establishing in516_triangular_sum.

    We split the sum ∑_{k=0}^{r-1} (k + 1) into ∑ k + ∑ 1. The sum of ones is r, and the sum of indices is r(r-1)/2. Multiplying the identity by 2 gives r(r-1) + 2r = r(r+1), which holds algebraically since r(r-1) is always even.

    lines 18–32

    uses Finset.sum_add_distrib, Finset.sum_const_nat, Finset.card_range, mul_one, Finset.sum_range_id, Nat.eq_div_of_mul_eq_right, Nat.mul_comm, Nat.div_two_mul_two_of_even, Nat.even_mul_pred_self, Nat.mul_add

      rw [Finset.sum_add_distrib]
      simp only [Finset.sum_const_nat (m := 1) (fun x _ => rfl), Finset.card_range, mul_one]
      rw [Finset.sum_range_id]
      apply Nat.eq_div_of_mul_eq_right (c := 2) (by norm_num)
      have h2even : r * (r - 1) = 2 * (r * (r - 1) / 2) := by
        rw [Nat.mul_comm 2, Nat.div_two_mul_two_of_even (Nat.even_mul_pred_self r)]
      have key : r * (r - 1) + 2 * r = r * (r + 1) := by
        cases r with
        | zero => simp
        | succ n =>
            have hsub : n + 1 - 1 = n := by omega
            rw [hsub]
            ring
      rw [Nat.mul_add, ← h2even]
      exact key
  4. For n = 0, the empty sequence vacuously satisfies the peeling conditions.

    We proceed by induction on n. When n = 0, the domain Fin 0 is empty, so Fin.elim0 provides an injective function whose image and degree bounds hold vacuously.

    lines 41–45

    uses Fin.elim0

      intro n
      induction n with
      | zero =>
          intro X h hr
          exact ⟨Fin.elim0, fun i => i.elim0, fun i => i.elim0, fun i => i.elim0⟩
  5. In the inductive step n + 1, we pick a low-degree vertex s₀ ∈ X and apply the induction hypothesis to X \ {s₀}.

    Since |X| ≥ n + 1 > 0, X is nonempty. By the peeling hypothesis, X contains a vertex s₀ with fewer than m neighbors in X. Every nonempty subset of X \ {s₀} is also a subset of X and thus still contains a vertex of out-degree < m. Since |X \ {s₀}| = |X| - 1 ≥ n, the induction hypothesis yields an injection s' : Fin n → X \ {s₀} with internal out-degrees bounded by m + i.

    lines 46–54

    uses Finset.card_pos.mp, Finset.Subset.refl, Finset.erase_subset, Finset.card_erase_of_mem

      | succ n ih =>
          intro X h hr
          have hne : X.Nonempty := Finset.card_pos.mp (by omega)
          obtain ⟨s0, hs0X, hsink⟩ := h X (Finset.Subset.refl X) hne
          have h' : ∀ T ⊆ X.erase s0, T.Nonempty → ∃ v ∈ T, (T.filter fun w => D.Adj v w).card < m :=
            fun T hT hne => h T (hT.trans (Finset.erase_subset s0 X)) hne
          have hr' : n ≤ (X.erase s0).card := by
            rw [Finset.card_erase_of_mem hs0X]; omega
          obtain ⟨s', hinj', hmem', hbound'⟩ := ih (X.erase s0) h' hr'
  6. Prepending s₀ to s' produces an injective map s : Fin (n + 1) → X.

    We define s by setting s(0) = s₀ and s(i+1) = s'(i). Because s' takes values in X \ {s₀}, s₀ is not in the image of s'. Since s' is injective, Fin.cons_injective_of_injective implies s is injective, and all values lie in X.

    lines 55–65

    uses Fin.cons_injective_of_injective, Fin.cases, Fin.cons_zero, Fin.cons_succ

          let s : Fin (n+1) → α := Fin.cons s0 s'
          refine ⟨s, ?_, ?_, ?_⟩
          · show Function.Injective (Fin.cons s0 s')
            apply Fin.cons_injective_of_injective
            · rintro ⟨i, hi⟩
              exact (Finset.mem_erase.mp (hmem' i)).1 hi
            · exact hinj'
          · intro j
            induction j using Fin.cases with
            | zero => simpa only [s, Fin.cons_zero] using hs0X
            | succ i => simpa only [s, Fin.cons_succ] using (Finset.mem_erase.mp (hmem' i)).2
  7. Each vertex s(j) has strictly fewer than m + j out-neighbors in X, completing the proof of in516_peel.

    For j = 0, s(0) = s₀ has out-degree in X strictly less than m = m + 0. For j = i + 1, the out-neighbors of s'(i) in X are contained in its out-neighbors in X \ {s₀} together with at most {s₀}. Adding at most 1 to the inductive bound < m + i gives < m + i + 1 = m + j.

    lines 66–86

    uses Fin.cases, Fin.cons_zero, Fin.cons_succ, Finset.mem_filter, Finset.mem_union, Finset.mem_erase, Finset.card_le_card, Finset.card_union_le, Finset.card_singleton

          · intro j
            induction j using Fin.cases with
            | zero => simpa only [s, Fin.cons_zero, Fin.val_zero, Nat.add_zero] using hsink
            | succ i =>
                simp only [s, Fin.cons_succ]
                have hsub : X.filter (fun w => D.Adj (s' i) w)
                    ⊆ (X.erase s0).filter (fun w => D.Adj (s' i) w) ∪ ({s0} : Finset α) := by
                  intro w hw
                  simp only [Finset.mem_filter] at hw
                  rw [Finset.mem_union]
                  by_cases hw0 : w = s0
                  · right; simp [hw0]
                  · left
                    simp only [Finset.mem_filter, Finset.mem_erase]
                    exact ⟨⟨hw0, hw.1⟩, hw.2⟩
                have h1 := Finset.card_le_card hsub
                have h2 := Finset.card_union_le ((X.erase s0).filter (fun w => D.Adj (s' i) w)) ({s0} : Finset α)
                have h3 := hbound' i
                rw [Finset.card_singleton] at h2
                simp only [Fin.val_succ]
                omega
  8. Every nonempty subset T ⊆ B contains a vertex whose out-degree into T is strictly less than m.

    Suppose, for contradiction, that some nonempty T ⊆ B has every vertex with induced out-degree at least m. By the cycle-packing criterion hcriterion, T would contain q pairwise disjoint directed cycles. Since T ⊆ B, these cycles would lie in B, contradicting the hypothesis hno that B contains no such packing.

    lines 101–110

      classical
      have hsmall : ∀ T ⊆ B, T.Nonempty → ∃ v ∈ T, (T.filter fun w => D.Adj v w).card < m := by
        intro T hTB hT
        by_contra hn
        have hd : ∀ v ∈ T, m ≤ (T.filter fun w => D.Adj v w).card := by
          intro v hv
          by_contra hh
          exact hn ⟨v, hv, by omega⟩
        obtain ⟨c, hc, hp⟩ := hcriterion T hT hd
        exact hno ⟨c, fun i => ⟨(hc i).1.trans hTB, (hc i).2⟩, hp⟩
  9. There exists an injective sequence s of n = r - m + 1 vertices in B whose internal out-degrees are sequentially bounded.

    Setting n = r - m + 1, the assumption |B| ≥ n and the minimum out-degree property allow us to invoke the peeling lemma in516_peel, obtaining an injection s : Fin n → B where each s(j) has fewer than m + j neighbors in B.

    lines 111–112

    uses in516_peel

      let n := r - m + 1
      obtain ⟨s, hinj, hmem, hbound⟩ := in516_peel α D m n B hsmall hB
  10. Each peeled vertex s(j) sends at least n - j directed edges outside of B.

    The set of all out-neighbors of s(j) partitions disjointly into neighbors inside B and neighbors in Bᶜ. The global out-degree is at least r, while the number of neighbors in B is strictly less than m + j. Subtracting gives at least r - (m + j - 1) = (r - m + 1) - j = n - j edges leaving B.

    lines 113–129

    uses Finset.disjoint_left, Finset.filter_union, Finset.union_compl, Finset.card_union_of_disjoint

      have hterm : ∀ j : Fin n, n - (j:ℕ) ≤ (Bᶜ.filter fun w => D.Adj (s j) w).card := by
        intro j
        have hout := hdeg (s j) (hmem j)
        have hint := hbound j
        have hdisj : Disjoint (B.filter (fun w => D.Adj (s j) w)) (Bᶜ.filter (fun w => D.Adj (s j) w)) := by
          rw [Finset.disjoint_left]
          intro x hx hx'
          simp only [Finset.mem_filter] at hx hx'
          exact (Finset.mem_compl.mp hx'.1) hx.1
        have hunion : B.filter (fun w => D.Adj (s j) w) ∪ Bᶜ.filter (fun w => D.Adj (s j) w)
            = Finset.univ.filter (fun w => D.Adj (s j) w) := by
          rw [← Finset.filter_union, Finset.union_compl]
        have hpart : (Finset.univ.filter (fun w => D.Adj (s j) w)).card
            = (B.filter (fun w => D.Adj (s j) w)).card + (Bᶜ.filter (fun w => D.Adj (s j) w)).card := by
          rw [← hunion, Finset.card_union_of_disjoint hdisj]
        dsimp [n] at *
        omega
  11. The sum of outgoing edges from the n peeled vertices is at least n(n+1)/2.

    Summing the lower bound n - j over all j ∈ {0, ..., n - 1} by Finset.sum_le_sum, and evaluating the triangular sum via in516_triangular_sum, gives n(n+1)/2 ≤ ∑_{j ∈ Fin n} |{w ∈ Bᶜ : s(j) → w}|.

    lines 130–133

    uses Finset.sum_le_sum, in516_triangular_sum

      have hsum_ge : n * (n + 1) / 2 ≤ ∑ j : Fin n, (Bᶜ.filter fun w => D.Adj (s j) w).card := by
        have h1 : ∑ j : Fin n, (n - (j:ℕ)) ≤ ∑ j : Fin n, (Bᶜ.filter fun w => D.Adj (s j) w).card :=
          Finset.sum_le_sum (fun j _ => hterm j)
        rwa [in516_triangular_sum n] at h1
  12. The sum of cut edges from the image of s is bounded above by the total number of edges leaving B.

    Since s is injective, reindexing replaces the sum over Fin n with the sum over the image s(Fin n) ⊆ B. Because each vertex has a non-negative number of cut edges, the sum over this subset is at most the total sum over all v ∈ B.

    lines 134–143

    uses Finset.sum_image, Finset.sum_le_sum_of_subset_of_nonneg, Nat.zero_le

      have hsum_le : ∑ j : Fin n, (Bᶜ.filter fun w => D.Adj (s j) w).card
          ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card := by
        have himg : ∑ j : Fin n, (Bᶜ.filter fun w => D.Adj (s j) w).card
            = ∑ v ∈ (Finset.univ.image s), (Bᶜ.filter fun w => D.Adj v w).card := by
          rw [Finset.sum_image (f := fun v => (Bᶜ.filter fun w => D.Adj v w).card)
                (g := s) (s := Finset.univ) (fun i _ j _ h => hinj h)]
        rw [himg]
        exact Finset.sum_le_sum_of_subset_of_nonneg
          (Finset.image_subset_iff.mpr (fun j _ => hmem j))
          (fun v _ _ => Nat.zero_le _)
  13. At least (r - m + 1)(r - m + 2)/2 edges leave B.

    Combining the lower bound on the subset sum with the upper bound via transitivity (le_trans), and substituting n = r - m + 1, concludes that (r - m + 1)(r - m + 2)/2 ≤ ∑_{v ∈ B} |{w ∈ Bᶜ : v → w}|.

    lines 144–146

    uses le_trans

      have hfinal := le_trans hsum_ge hsum_le
      dsimp [n] at hfinal
      convert hfinal using 1
Finset.sum_fin_eq_sum_range
A sum indexed over Fin n equals the sum over Finset.range n of the same function evaluated on indices strictly less than n.
Finset.sum_congr
Two sums over equal finite sets are equal if their summands agree on every element.
Finset.mem_range
A natural number m belongs to Finset.range n if and only if m < n.
Finset.sum_range_reflect
Reversing the order of summation over Finset.range n preserves the sum.
Finset.sum_add_distrib
The sum of a pointwise sum of functions over a finite set equals the sum of the individual sums.
Finset.sum_const_nat
Summing a constant natural value m over a finite set s yields |s| * m.
Finset.card_range
The cardinality of Finset.range n is n.
mul_one
Multiplying any number by 1 leaves it unchanged.
Finset.sum_range_id
The sum of the first n natural numbers 0, 1, ..., n-1 is n(n - 1)/2.
Nat.eq_div_of_mul_eq_right
If c ≠ 0 and c * a = b, then a = b / c in the natural numbers.
Nat.mul_comm
Multiplication of natural numbers is commutative.
Nat.div_two_mul_two_of_even
Dividing an even natural number by 2 and multiplying by 2 yields the original number.
Nat.even_mul_pred_self
The product of any natural number with its predecessor is even.
Nat.mul_add
Multiplication distributes over addition for natural numbers.
Fin.elim0
Elimination principle for the empty type Fin 0: any function from Fin 0 can be vacuously defined.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.Subset.refl
Every finite set is a subset of itself.
Finset.erase_subset
Erasing an element from a finite set yields a subset of the original set.
Finset.card_erase_of_mem
Erasing an element that belongs to a finite set decreases its cardinality by 1.
Fin.cons_injective_of_injective
Prepending an element not in the range of an injective map from Fin n produces an injective map from Fin (n + 1).
Fin.cases
Case analysis on Fin (n + 1): either the index is 0 or the successor of an index in Fin n.
Fin.cons_zero
Evaluating a prepended sequence Fin.cons x p at 0 yields the head element x.
Fin.cons_succ
Evaluating a prepended sequence Fin.cons x p at the successor of i yields p(i).
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the predicate.
Finset.mem_union
An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_erase
An element belongs to s with b erased if and only if it is distinct from b and belongs to s.
Finset.card_le_card
If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.card_singleton
A singleton finite set has cardinality 1.
in516_peel
If every nonempty subset of X contains a vertex with induced out-degree < m, any n ≤ |X| vertices can be ordered so that the j-th vertex has < m + j neighbors in X.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.filter_union
Filtering a union by a predicate distributes over the union.
Finset.union_compl
The union of a finite set and its complement is the universal set.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i in a finite set, then the sum of f is at most the sum of g.
in516_triangular_sum
The sum ∑_{j=0}^{r-1} (r - j) of the first r positive integers in reverse order equals r(r + 1)/2.
Finset.sum_image
A sum over the image of a finite set under an injective map equals the sum over the domain evaluated at the mapped elements.
Finset.sum_le_sum_of_subset_of_nonneg
Summing a non-negative function over a subset yields at most the sum over the entire superset.
Nat.zero_le
Zero is less than or equal to any natural number.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.

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

private theorem in516_triangular_sum (r : ℕ) :    (∑ j : Fin r, (r - (j:ℕ))) = r * (r + 1) / 2 := by  have h1 : (∑ j : Fin r, (r - (j:ℕ))) = ∑ k ∈ Finset.range r, (r - k) := by    rw [Finset.sum_fin_eq_sum_range]    refine Finset.sum_congr rfl ?_    intro k hk    simp only [Finset.mem_range] at hk    simp [hk]  rw [h1]  have h2 : ∑ k ∈ Finset.range r, (r - k) = ∑ k ∈ Finset.range r, (k + 1) := by    have := Finset.sum_range_reflect (fun k => k + 1) r    rw [← this]    refine Finset.sum_congr rfl ?_    intro k hk    simp only [Finset.mem_range] at hk    omega  rw [h2]  rw [Finset.sum_add_distrib]  simp only [Finset.sum_const_nat (m := 1) (fun x _ => rfl), Finset.card_range, mul_one]  rw [Finset.sum_range_id]  apply Nat.eq_div_of_mul_eq_right (c := 2) (by norm_num)  have h2even : r * (r - 1) = 2 * (r * (r - 1) / 2) := by    rw [Nat.mul_comm 2, Nat.div_two_mul_two_of_even (Nat.even_mul_pred_self r)]  have key : r * (r - 1) + 2 * r = r * (r + 1) := by    cases r with    | zero => simp    | succ n =>        have hsub : n + 1 - 1 = n := by omega        rw [hsub]        ring  rw [Nat.mul_add, ← h2even]  exact keyprivate theorem in516_peel (α : Type) [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj] (m : ℕ) :    ∀ (n : ℕ) (X : Finset α),      (∀ T ⊆ X, T.Nonempty → ∃ v ∈ T, (T.filter fun w => D.Adj v w).card < m) →      n ≤ X.card →      ∃ s : Fin n → α, Function.Injective s ∧ (∀ j, s j ∈ X) ∧        ∀ j, (X.filter fun w => D.Adj (s j) w).card < m + (j : ℕ) := by  intro n  induction n with  | zero =>      intro X h hr      exact ⟨Fin.elim0, fun i => i.elim0, fun i => i.elim0, fun i => i.elim0⟩  | succ n ih =>      intro X h hr      have hne : X.Nonempty := Finset.card_pos.mp (by omega)      obtain ⟨s0, hs0X, hsink⟩ := h X (Finset.Subset.refl X) hne      have h' : ∀ T ⊆ X.erase s0, T.Nonempty → ∃ v ∈ T, (T.filter fun w => D.Adj v w).card < m :=        fun T hT hne => h T (hT.trans (Finset.erase_subset s0 X)) hne      have hr' : n ≤ (X.erase s0).card := by        rw [Finset.card_erase_of_mem hs0X]; omega      obtain ⟨s', hinj', hmem', hbound'⟩ := ih (X.erase s0) h' hr'      let s : Fin (n+1) → α := Fin.cons s0 s'      refine ⟨s, ?_, ?_, ?_⟩      · show Function.Injective (Fin.cons s0 s')        apply Fin.cons_injective_of_injective        · rintro ⟨i, hi⟩          exact (Finset.mem_erase.mp (hmem' i)).1 hi        · exact hinj'      · intro j        induction j using Fin.cases with        | zero => simpa only [s, Fin.cons_zero] using hs0X        | succ i => simpa only [s, Fin.cons_succ] using (Finset.mem_erase.mp (hmem' i)).2      · intro j        induction j using Fin.cases with        | zero => simpa only [s, Fin.cons_zero, Fin.val_zero, Nat.add_zero] using hsink        | succ i =>            simp only [s, Fin.cons_succ]            have hsub : X.filter (fun w => D.Adj (s' i) w)                ⊆ (X.erase s0).filter (fun w => D.Adj (s' i) w) ∪ ({s0} : Finset α) := by              intro w hw              simp only [Finset.mem_filter] at hw              rw [Finset.mem_union]              by_cases hw0 : w = s0              · right; simp [hw0]              · left                simp only [Finset.mem_filter, Finset.mem_erase]                exact ⟨⟨hw0, hw.1⟩, hw.2⟩            have h1 := Finset.card_le_card hsub            have h2 := Finset.card_union_le ((X.erase s0).filter (fun w => D.Adj (s' i) w)) ({s0} : Finset α)            have h3 := hbound' i            rw [Finset.card_singleton] at h2            simp only [Fin.val_succ]            omegatheorem digraph_packing_free_cut_peeling_bound    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (r m q : ℕ) (hm : m ≤ r) (B : Finset α) (hB : r - m + 1 ≤ B.card)    (hdeg : ∀ v ∈ B, r ≤ (Finset.univ.filter fun w => D.Adj v w).card)    (hcriterion : ∀ T : Finset α, T.Nonempty →      (∀ v ∈ T, m ≤ (T.filter fun w => D.Adj v w).card) →      ∃ c : Fin q → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)))    (hno : ¬ ∃ c : Fin q → Finset α,      (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j))) :    (r - m + 1) * (r - m + 2) / 2 ≤      ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card := by  classical  have hsmall : ∀ T ⊆ B, T.Nonempty → ∃ v ∈ T, (T.filter fun w => D.Adj v w).card < m := by    intro T hTB hT    by_contra hn    have hd : ∀ v ∈ T, m ≤ (T.filter fun w => D.Adj v w).card := by      intro v hv      by_contra hh      exact hn ⟨v, hv, by omega⟩    obtain ⟨c, hc, hp⟩ := hcriterion T hT hd    exact hno ⟨c, fun i => ⟨(hc i).1.trans hTB, (hc i).2⟩, hp⟩  let n := r - m + 1  obtain ⟨s, hinj, hmem, hbound⟩ := in516_peel α D m n B hsmall hB  have hterm : ∀ j : Fin n, n - (j:ℕ) ≤ (Bᶜ.filter fun w => D.Adj (s j) w).card := by    intro j    have hout := hdeg (s j) (hmem j)    have hint := hbound j    have hdisj : Disjoint (B.filter (fun w => D.Adj (s j) w)) (Bᶜ.filter (fun w => D.Adj (s j) w)) := by      rw [Finset.disjoint_left]      intro x hx hx'      simp only [Finset.mem_filter] at hx hx'      exact (Finset.mem_compl.mp hx'.1) hx.1    have hunion : B.filter (fun w => D.Adj (s j) w) ∪ Bᶜ.filter (fun w => D.Adj (s j) w)        = Finset.univ.filter (fun w => D.Adj (s j) w) := by      rw [← Finset.filter_union, Finset.union_compl]    have hpart : (Finset.univ.filter (fun w => D.Adj (s j) w)).card        = (B.filter (fun w => D.Adj (s j) w)).card + (Bᶜ.filter (fun w => D.Adj (s j) w)).card := by      rw [← hunion, Finset.card_union_of_disjoint hdisj]    dsimp [n] at *    omega  have hsum_ge : n * (n + 1) / 2 ≤ ∑ j : Fin n, (Bᶜ.filter fun w => D.Adj (s j) w).card := by    have h1 : ∑ j : Fin n, (n - (j:ℕ)) ≤ ∑ j : Fin n, (Bᶜ.filter fun w => D.Adj (s j) w).card :=      Finset.sum_le_sum (fun j _ => hterm j)    rwa [in516_triangular_sum n] at h1  have hsum_le : ∑ j : Fin n, (Bᶜ.filter fun w => D.Adj (s j) w).card      ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card := by    have himg : ∑ j : Fin n, (Bᶜ.filter fun w => D.Adj (s j) w).card        = ∑ v ∈ (Finset.univ.image s), (Bᶜ.filter fun w => D.Adj v w).card := by      rw [Finset.sum_image (f := fun v => (Bᶜ.filter fun w => D.Adj v w).card)            (g := s) (s := Finset.univ) (fun i _ j _ h => hinj h)]    rw [himg]    exact Finset.sum_le_sum_of_subset_of_nonneg      (Finset.image_subset_iff.mpr (fun j _ => hmem j))      (fun v _ _ => Nat.zero_le _)  have hfinal := le_trans hsum_ge hsum_le  dsimp [n] at hfinal  convert hfinal using 1
See it in the graphDiscuss this resultChallenge it