digraph_seven_out_robust_cut_thresholds
Under the displayed robust two-cycle criterion, if a set of at least seven vertices in a digraph of minimum outdegree seven contains no two disjoint directed cycles, then its numbers of vertices with at least each specified outside outdegree satisfy the five displayed alternatives.
Statement
theorem digraph_seven_out_robust_cut_thresholds (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (B : Finset α) (hB : 7 ≤ B.card) (hdeg : ∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hrobust : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) → (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 → ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hno : ¬ ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) : let n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ (Bᶜ.filter fun w => D.Adj v w).card).card (1 ≤ n 6 ∨ 3 ≤ n 5) ∧ (2 ≤ n 5 ∨ 4 ≤ n 4) ∧ (3 ≤ n 4 ∨ 5 ≤ n 3) ∧ (4 ≤ n 3 ∨ 6 ≤ n 2) ∧ (5 ≤ n 2 ∨ 7 ≤ n 1)
- Source
- Superlevel-count reduction for the robust cut lemma in OP-110; experiment 26115 checks the resulting arithmetic.
- Verified
- 14 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 2
- digraph_twenty_cut_degree_profile_under_two_cycle_sequencesFor a seven-outregular two-cycle-free part with a twenty-arc outgoing cut, the displayed robust and two-cycle degree-sequence criteria…
- digraph_seven_out_robust_two_cycle_free_cut_ge_twentyA set of at least seven vertices in a digraph of minimum outdegree seven, containing no two disjoint directed cycles, has at least twenty…
The proof, explained
The theorem is proven by establishing a general threshold lemma: for any t ≤ 4, either t + 1 ≤ n(6 - t) or t + 3 ≤ n(5 - t), where n(k) counts vertices in B with outside outdegree at least k. To prove this by contradiction, if both inequalities fail, a selection lemma extracts a subset S ⊆ B of size at most t containing all vertices with outside outdegree ≥ 6 - t such that at most 2 vertices with outside outdegree ≥ 5 - t remain in T = B \ S. The induced subgraph on T then satisfies the robust two-cycle criterion (minimum outdegree at least 2, and at most two vertices of outdegree 2), producing two disjoint directed cycles in T ⊆ B and contradicting the hypothesis. Finally, instantiating this general lemma for t = 0, 1, 2, 3, 4 yields the conjunction of the five threshold alternatives.
In the selection lemma, if |B| ≤ t, the choice S = B satisfies all requirements.
When |B| ≤ t, we take S = B. Then S ⊆ B by reflexivity (`Finset.Subset.rfl`), A ⊆ S follows from A ⊆ B, |S| ≤ t holds by the case hypothesis, and |B \ S| = |∅| = 0 ≤ 2.
uses
Finset.Subset.rflby_cases hsmall : B.card ≤ t · exact ⟨B, Finset.Subset.rfl, hAB, hsmall, by simp⟩
In the selection lemma, if |B| > t, setting S = A ∪ R for an appropriate subset R ⊆ B \ A of size t - |A| satisfies all requirements.
Since |B| > t and |A| ≤ t, the difference B \ A has size |B| - |A| ≥ t - |A| by `Finset.card_sdiff_of_subset`. By `Finset.exists_subset_card_eq`, there is a subset R ⊆ B \ A of size exactly t - |A|. Taking S = A ∪ R, we have S ⊆ B and A ⊆ S. Because A and R are disjoint (by `Finset.disjoint_left.mpr` and `Finset.mem_sdiff.mp`), |S| = |A| + |R| = t ≤ t by `Finset.card_union_of_disjoint`. Finally, |B \ S| = |B| - |S| ≤ (t + 2) - t = 2 by `Finset.card_sdiff_of_subset`.
uses
Finset.card_sdiff_of_subset,Finset.exists_subset_card_eq,Finset.union_subset,Finset.sdiff_subset,Finset.subset_union_left,Finset.disjoint_left.mpr,Finset.mem_sdiff.mp,Finset.card_union_of_disjoint· have hd : t - A.card ≤ (B \ A).card := by rw [Finset.card_sdiff_of_subset hAB] omega obtain ⟨R, hRB, hRcard⟩ := Finset.exists_subset_card_eq hd refine ⟨A ∪ R, ?_, ?_, ?_, ?_⟩ · exact Finset.union_subset hAB (hRB.trans (Finset.sdiff_subset)) · exact Finset.subset_union_left · have hdis : Disjoint A R := by apply Finset.disjoint_left.mpr intro v hvA hvR exact (Finset.mem_sdiff.mp (hRB hvR)).2 hvA rw [Finset.card_union_of_disjoint hdis, hRcard] omega · have hsub : A ∪ R ⊆ B := Finset.union_subset hAB (hRB.trans Finset.sdiff_subset) have hdis : Disjoint A R := by apply Finset.disjoint_left.mpr intro v hvA hvR exact (Finset.mem_sdiff.mp (hRB hvR)).2 hvA rw [Finset.card_sdiff_of_subset hsub, Finset.card_union_of_disjoint hdis, hRcard] omega
In the general threshold theorem, assuming the conclusion fails, there exists S ⊆ P containing A with |S| ≤ t and |P \ S| ≤ 2.
We argue by contradiction. Suppose the disjunction fails, so |A| ≤ t and |P| ≤ t + 2, where A = {v ∈ B | 6 - t ≤ d(v)} and P = {v ∈ B | 5 - t ≤ d(v)} and d(v) = |N⁺(v) \ B|. Because 6 - t ≥ 5 - t, any vertex in A is in P, so A ⊆ P. Applying the helper lemma `in833_select_thresholds` to A and P produces a subset S ⊆ P containing A such that |S| ≤ t and |P \ S| ≤ 2.
uses
Finset.mem_filter.mp,Finset.mem_filter.mpr,in833_select_thresholdsclassical let d : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card let A := B.filter fun v => 6-t ≤ d v let P := B.filter fun v => 5-t ≤ d v change t+1 ≤ A.card ∨ t+3 ≤ P.card by_contra hh have hA : A.card ≤ t := by omega have hP : P.card ≤ t+2 := by omega have hAP : A ⊆ P := by intro v hv have h := Finset.mem_filter.mp hv exact Finset.mem_filter.mpr ⟨h.1, by omega⟩ obtain ⟨S,hSP,hAS,hScard,hPS⟩ := in833_select_thresholds A P t hAP hA hP
The complement T = B \ S is a nonempty subset of B.
Since P ⊆ B by `Finset.filter_subset`, we have S ⊆ B. Define T = B \ S. By `Finset.card_sdiff_add_card_eq_card`, |T| + |S| = |B|. Since |B| ≥ 7 and |S| ≤ t ≤ 4, |T| ≥ 7 - 4 = 3 > 0. By `Finset.card_pos.mp`, T is nonempty.
uses
Finset.filter_subset,Finset.card_pos.mp,Finset.card_sdiff_add_card_eq_cardhave hPB : P ⊆ B := Finset.filter_subset _ _ have hSB : S ⊆ B := hSP.trans hPB let T := B \ S have hT : T.Nonempty := by apply Finset.card_pos.mp change 0 < (B \ S).card have h := Finset.card_sdiff_add_card_eq_card hSB omega
For every vertex v ∈ B, its total outdegree 7 is bounded by |N⁺(v) ∩ T| + |S| + d(v).
Every out-neighbor w of v in the digraph lies either in T = B \ S, in S, or outside B in Bᶜ. Hence the out-neighborhood of v is a subset of (N⁺(v) ∩ T) ∪ S ∪ (N⁺(v) ∩ Bᶜ). Applying `Finset.card_le_card` together with union subadditivity `Finset.card_union_le` and the minimum outdegree hypothesis hdeg (giving 7 ≤ |N⁺(v)|), we obtain 7 ≤ |N⁺(v) ∩ T| + |S| + d(v).
uses
Finset.mem_filter.mp,Finset.mem_union_left,Finset.mem_union_right,Finset.mem_filter.mpr,Finset.mem_sdiff.mpr,Finset.mem_compl.mpr,Finset.card_le_card,Finset.card_union_lehave hsum (v : α) (hv : v ∈ B) : 7 ≤ (T.filter fun w => D.Adj v w).card + S.card + d v := by have hsubset : (Finset.univ.filter fun w => D.Adj v w) ⊆ (T.filter fun w => D.Adj v w) ∪ S ∪ (Bᶜ.filter fun w => D.Adj v w) := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 by_cases hwB : w ∈ B · by_cases hwS : w ∈ S · exact Finset.mem_union_left _ (Finset.mem_union_right _ hwS) · apply Finset.mem_union_left apply Finset.mem_union_left exact Finset.mem_filter.mpr ⟨Finset.mem_sdiff.mpr ⟨hwB,hwS⟩,hadj⟩ · apply Finset.mem_union_right exact Finset.mem_filter.mpr ⟨Finset.mem_compl.mpr hwB,hadj⟩ have hc := Finset.card_le_card hsubset have hu1 := Finset.card_union_le ((T.filter fun w => D.Adj v w) ∪ S) (Bᶜ.filter fun w => D.Adj v w) have hu2 := Finset.card_union_le (T.filter fun w => D.Adj v w) S have hvdeg := hdeg v hv dsimp [d] omega
Every vertex in T has outdegree at least 2 into T.
For any v ∈ T = B \ S, v ∉ S and therefore v ∉ A (since A ⊆ S). Hence d(v) < 6 - t, meaning d(v) ≤ 5 - t. Combining this with the degree bound 7 ≤ |N⁺(v) ∩ T| + |S| + d(v) and |S| ≤ t, linear arithmetic gives |N⁺(v) ∩ T| ≥ 7 - t - (5 - t) = 2.
uses
Finset.mem_sdiff.mp,Finset.mem_filter.mprhave hTdeg : ∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card := by intro v hv have hvB := (Finset.mem_sdiff.mp hv).1 have hvS := (Finset.mem_sdiff.mp hv).2 have hvA : v ∉ A := fun ha => hvS (hAS ha) have hd : d v < 6-t := by by_contra h exact hvA (Finset.mem_filter.mpr ⟨hvB, by omega⟩) have hn := hsum v hvB omega
At most two vertices in T have outdegree strictly less than 3 into T.
If v ∈ T satisfies |N⁺(v) ∩ T| < 3, then 7 ≤ 2 + |S| + d(v) ≤ 2 + t + d(v), so d(v) ≥ 5 - t, which places v in P. Since v ∈ T = B \ S, v must belong to P \ S. Therefore, the set of vertices in T with low outdegree in T is a subset of P \ S. Since |P \ S| ≤ 2, `Finset.card_le_card` implies that at most 2 vertices in T have outdegree less than 3.
uses
Finset.mem_filter.mp,Finset.mem_sdiff.mp,Finset.mem_filter.mpr,Finset.mem_sdiff.mpr,Finset.card_le_cardhave hbadsub : (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3) ⊆ P \ S := by intro v hv obtain ⟨hvT,hvlow⟩ := Finset.mem_filter.mp hv have hvB := (Finset.mem_sdiff.mp hvT).1 have hvS := (Finset.mem_sdiff.mp hvT).2 have hn := hsum v hvB have hvP : v ∈ P := Finset.mem_filter.mpr ⟨hvB, by omega⟩ exact Finset.mem_sdiff.mpr ⟨hvP,hvS⟩ have hbad : (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 := (Finset.card_le_card hbadsub).trans hPS
The robust two-cycle criterion applies to T, producing two disjoint cycles in B and contradicting the hypothesis hno.
Having verified that T is nonempty, every vertex in T has outdegree at least 2 in T, and at most 2 vertices have outdegree less than 3, the robust two-cycle hypothesis `hrobust` guarantees two vertex-disjoint directed cycles in T. Because T ⊆ B by `Finset.sdiff_subset`, these cycles lie in B, contradicting `hno`. This completes the contradiction in `in833_threshold_general`.
uses
Finset.sdiff_subsetobtain ⟨c,hc,hpair⟩ := hrobust T hT hTdeg hbad apply hno refine ⟨c, ?_, hpair⟩ intro i exact ⟨(hc i).1.trans (Finset.sdiff_subset), (hc i).2⟩
The five threshold alternatives hold simultaneously.
We apply `in833_threshold_general` for each t ∈ {0, 1, 2, 3, 4}. For t = 0, it yields 1 ≤ n(6) ∨ 3 ≤ n(5); for t = 1, it yields 2 ≤ n(5) ∨ 4 ≤ n(4); for t = 2, it yields 3 ≤ n(4) ∨ 5 ≤ n(3); for t = 3, it yields 4 ≤ n(3) ∨ 6 ≤ n(2); and for t = 4, it yields 5 ≤ n(2) ∨ 7 ≤ n(1). Combining these five results gives the required conjunction.
uses
in833_threshold_generalclassical let d : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card let n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ d v).card change (1 ≤ n 6 ∨ 3 ≤ n 5) ∧ (2 ≤ n 5 ∨ 4 ≤ n 4) ∧ (3 ≤ n 4 ∨ 5 ≤ n 3) ∧ (4 ≤ n 3 ∨ 6 ≤ n 2) ∧ (5 ≤ n 2 ∨ 7 ≤ n 1) have h0 := in833_threshold_general α D B hB hdeg hrobust hno 0 (by omega) have h1 := in833_threshold_general α D B hB hdeg hrobust hno 1 (by omega) have h2 := in833_threshold_general α D B hB hdeg hrobust hno 2 (by omega) have h3 := in833_threshold_general α D B hB hdeg hrobust hno 3 (by omega) have h4 := in833_threshold_general α D B hB hdeg hrobust hno 4 (by omega) change 1 ≤ n 6 ∨ 3 ≤ n 5 at h0 change 2 ≤ n 5 ∨ 4 ≤ n 4 at h1 change 3 ≤ n 4 ∨ 5 ≤ n 3 at h2 change 4 ≤ n 3 ∨ 6 ≤ n 2 at h3 change 5 ≤ n 2 ∨ 7 ≤ n 1 at h4 exact ⟨h0,h1,h2,h3,h4⟩
Finset.Subset.rfl- Every set is a subset of itself: s ⊆ s.
Finset.card_sdiff_of_subset- If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.exists_subset_card_eq- If n ≤ |s|, then s contains a subset of cardinality n.
Finset.union_subset- If s ⊆ u and t ⊆ u, then s ∪ t ⊆ u.
Finset.sdiff_subset- For any sets s and t, the set difference s \ t is a subset of s.
Finset.subset_union_left- Any set s₁ is a subset of the union s₁ ∪ s₂.
Finset.disjoint_left.mpr- Two sets are disjoint if no element of the first belongs to the second.
Finset.mem_sdiff.mp- If an element belongs to s \ t, then it belongs to s and not to t.
Finset.mem_sdiff.mpr- If an element belongs to s and does not belong to t, then it belongs to s \ t.
Finset.card_union_of_disjoint- The cardinality of the union of disjoint finite sets is the sum of their cardinalities.
Finset.mem_filter.mp- If an element belongs to {x ∈ s | p x}, then it belongs to s and satisfies p.
Finset.mem_filter.mpr- If an element belongs to s and satisfies p, then it belongs to {x ∈ s | p x}.
in833_select_thresholds- Given finite sets A ⊆ B with |A| ≤ t and |B| ≤ t + 2, there exists a subset S ⊆ B containing A such that |S| ≤ t and |B \ S| ≤ 2.
Finset.filter_subset- Filtering a set by a predicate produces a subset of the original set.
Finset.card_pos.mp- A finite set with strictly positive cardinality is nonempty.
Finset.card_sdiff_add_card_eq_card- If s ⊆ t, then |t \ s| + |s| = |t|.
Finset.mem_union_left- If an element belongs to s, then it belongs to s ∪ t.
Finset.mem_union_right- If an element belongs to t, then it belongs to s ∪ t.
Finset.mem_compl.mpr- If an element does not belong to s, then it belongs to the complement sᶜ.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Finset.card_union_le- The cardinality of a union s ∪ t is at most |s| + |t|.
in833_threshold_general- Under the robust two-cycle criterion, if a set B of size ≥ 7 in a digraph of minimum outdegree 7 contains no two disjoint directed cycles, then for any t ≤ 4, either t + 1 ≤ n(6 - t) or t + 3 ≤ n(5 - t).
- The proof factors the problem into a parametric lemma `in833_threshold_general` valid for any t ≤ 4, which is then instantiated at t = 0, 1, 2, 3, 4 to yield the five conjuncts of the main theorem.
- Cardinality arithmetic and linear inequalities over ℕ are discharged throughout by the `omega` Presburger arithmetic tactic.
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.
set_option maxHeartbeats 3000000set_option maxRecDepth 4096private lemma in833_select_thresholds {α : Type} [DecidableEq α] (A B : Finset α) (t : ℕ) (hAB : A ⊆ B) (hA : A.card ≤ t) (hB : B.card ≤ t + 2) : ∃ S : Finset α, S ⊆ B ∧ A ⊆ S ∧ S.card ≤ t ∧ (B \ S).card ≤ 2 := by by_cases hsmall : B.card ≤ t · exact ⟨B, Finset.Subset.rfl, hAB, hsmall, by simp⟩ · have hd : t - A.card ≤ (B \ A).card := by rw [Finset.card_sdiff_of_subset hAB] omega obtain ⟨R, hRB, hRcard⟩ := Finset.exists_subset_card_eq hd refine ⟨A ∪ R, ?_, ?_, ?_, ?_⟩ · exact Finset.union_subset hAB (hRB.trans (Finset.sdiff_subset)) · exact Finset.subset_union_left · have hdis : Disjoint A R := by apply Finset.disjoint_left.mpr intro v hvA hvR exact (Finset.mem_sdiff.mp (hRB hvR)).2 hvA rw [Finset.card_union_of_disjoint hdis, hRcard] omega · have hsub : A ∪ R ⊆ B := Finset.union_subset hAB (hRB.trans Finset.sdiff_subset) have hdis : Disjoint A R := by apply Finset.disjoint_left.mpr intro v hvA hvR exact (Finset.mem_sdiff.mp (hRB hvR)).2 hvA rw [Finset.card_sdiff_of_subset hsub, Finset.card_union_of_disjoint hdis, hRcard] omegaprivate theorem in833_threshold_general (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (B : Finset α) (hB : 7 ≤ B.card) (hdeg : ∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hrobust : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) → (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 → ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hno : ¬ ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (t : ℕ) (ht : t ≤ 4) : let n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ (Bᶜ.filter fun w => D.Adj v w).card).card t+1 ≤ n (6-t) ∨ t+3 ≤ n (5-t) := by classical let d : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card let A := B.filter fun v => 6-t ≤ d v let P := B.filter fun v => 5-t ≤ d v change t+1 ≤ A.card ∨ t+3 ≤ P.card by_contra hh have hA : A.card ≤ t := by omega have hP : P.card ≤ t+2 := by omega have hAP : A ⊆ P := by intro v hv have h := Finset.mem_filter.mp hv exact Finset.mem_filter.mpr ⟨h.1, by omega⟩ obtain ⟨S,hSP,hAS,hScard,hPS⟩ := in833_select_thresholds A P t hAP hA hP have hPB : P ⊆ B := Finset.filter_subset _ _ have hSB : S ⊆ B := hSP.trans hPB let T := B \ S have hT : T.Nonempty := by apply Finset.card_pos.mp change 0 < (B \ S).card have h := Finset.card_sdiff_add_card_eq_card hSB omega have hsum (v : α) (hv : v ∈ B) : 7 ≤ (T.filter fun w => D.Adj v w).card + S.card + d v := by have hsubset : (Finset.univ.filter fun w => D.Adj v w) ⊆ (T.filter fun w => D.Adj v w) ∪ S ∪ (Bᶜ.filter fun w => D.Adj v w) := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 by_cases hwB : w ∈ B · by_cases hwS : w ∈ S · exact Finset.mem_union_left _ (Finset.mem_union_right _ hwS) · apply Finset.mem_union_left apply Finset.mem_union_left exact Finset.mem_filter.mpr ⟨Finset.mem_sdiff.mpr ⟨hwB,hwS⟩,hadj⟩ · apply Finset.mem_union_right exact Finset.mem_filter.mpr ⟨Finset.mem_compl.mpr hwB,hadj⟩ have hc := Finset.card_le_card hsubset have hu1 := Finset.card_union_le ((T.filter fun w => D.Adj v w) ∪ S) (Bᶜ.filter fun w => D.Adj v w) have hu2 := Finset.card_union_le (T.filter fun w => D.Adj v w) S have hvdeg := hdeg v hv dsimp [d] omega have hTdeg : ∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card := by intro v hv have hvB := (Finset.mem_sdiff.mp hv).1 have hvS := (Finset.mem_sdiff.mp hv).2 have hvA : v ∉ A := fun ha => hvS (hAS ha) have hd : d v < 6-t := by by_contra h exact hvA (Finset.mem_filter.mpr ⟨hvB, by omega⟩) have hn := hsum v hvB omega have hbadsub : (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3) ⊆ P \ S := by intro v hv obtain ⟨hvT,hvlow⟩ := Finset.mem_filter.mp hv have hvB := (Finset.mem_sdiff.mp hvT).1 have hvS := (Finset.mem_sdiff.mp hvT).2 have hn := hsum v hvB have hvP : v ∈ P := Finset.mem_filter.mpr ⟨hvB, by omega⟩ exact Finset.mem_sdiff.mpr ⟨hvP,hvS⟩ have hbad : (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 := (Finset.card_le_card hbadsub).trans hPS obtain ⟨c,hc,hpair⟩ := hrobust T hT hTdeg hbad apply hno refine ⟨c, ?_, hpair⟩ intro i exact ⟨(hc i).1.trans (Finset.sdiff_subset), (hc i).2⟩theorem digraph_seven_out_robust_cut_thresholds (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (B : Finset α) (hB : 7 ≤ B.card) (hdeg : ∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hrobust : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) → (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 → ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hno : ¬ ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) : let n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ (Bᶜ.filter fun w => D.Adj v w).card).card (1 ≤ n 6 ∨ 3 ≤ n 5) ∧ (2 ≤ n 5 ∨ 4 ≤ n 4) ∧ (3 ≤ n 4 ∨ 5 ≤ n 3) ∧ (4 ≤ n 3 ∨ 6 ≤ n 2) ∧ (5 ≤ n 2 ∨ 7 ≤ n 1) := by classical let d : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card let n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ d v).card change (1 ≤ n 6 ∨ 3 ≤ n 5) ∧ (2 ≤ n 5 ∨ 4 ≤ n 4) ∧ (3 ≤ n 4 ∨ 5 ≤ n 3) ∧ (4 ≤ n 3 ∨ 6 ≤ n 2) ∧ (5 ≤ n 2 ∨ 7 ≤ n 1) have h0 := in833_threshold_general α D B hB hdeg hrobust hno 0 (by omega) have h1 := in833_threshold_general α D B hB hdeg hrobust hno 1 (by omega) have h2 := in833_threshold_general α D B hB hdeg hrobust hno 2 (by omega) have h3 := in833_threshold_general α D B hB hdeg hrobust hno 3 (by omega) have h4 := in833_threshold_general α D B hB hdeg hrobust hno 4 (by omega) change 1 ≤ n 6 ∨ 3 ≤ n 5 at h0 change 2 ≤ n 5 ∨ 4 ≤ n 4 at h1 change 3 ≤ n 4 ∨ 5 ≤ n 3 at h2 change 4 ≤ n 3 ∨ 6 ≤ n 2 at h3 change 5 ≤ n 2 ∨ 7 ≤ n 1 at h4 exact ⟨h0,h1,h2,h3,h4⟩