digraph_packing_free_cut_peeling_bound
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
- digraph_three_large_parts_no_four_cycles_cross_ge_forty_fiveIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles and its vertices are partitioned into three parts each…
- digraph_three_large_parts_no_four_cycles_cross_ge_fifty_fiveIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles, its vertices are partitioned into three parts of size…
- digraph_three_large_parts_no_four_cycles_cross_ge_fifty_fourIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles and its vertices are partitioned into three parts each…
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.
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.
uses
Finset.sum_fin_eq_sum_range,Finset.sum_congr,Finset.mem_rangehave 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]
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.
uses
Finset.sum_range_reflect,Finset.sum_congr,Finset.mem_rangehave 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]
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.
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_addrw [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
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.
uses
Fin.elim0intro n induction n with | zero => intro X h hr exact ⟨Fin.elim0, fun i => i.elim0, fun i => i.elim0, fun i => i.elim0⟩
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.
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'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.
uses
Fin.cons_injective_of_injective,Fin.cases,Fin.cons_zero,Fin.cons_succlet 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
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.
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
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.
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⟩
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.
uses
in516_peellet n := r - m + 1 obtain ⟨s, hinj, hmem, hbound⟩ := in516_peel α D m n B hsmall hB
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.
uses
Finset.disjoint_left,Finset.filter_union,Finset.union_compl,Finset.card_union_of_disjointhave 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
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}|.
uses
Finset.sum_le_sum,in516_triangular_sumhave 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
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.
uses
Finset.sum_image,Finset.sum_le_sum_of_subset_of_nonneg,Nat.zero_lehave 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 _)
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}|.
uses
le_transhave 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.
- The proof relies on two private helper lemmas proven in the same file: in516_triangular_sum, which computes the sum ∑_{j=0}^{r-1} (r - j) = r(r+1)/2, and in516_peel, which extracts an ordered sequence of vertices with sequentially bounded degrees by iteratively peeling a minimum-degree vertex.
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.
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