AFTD Auto-Formalizing Theoretical Domains

digraph_seven_out_robust_cut_thresholds

theoremverified

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

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.

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

    lines 6–7

    uses Finset.Subset.rfl

      by_cases hsmall : B.card ≤ t
      · exact ⟨B, Finset.Subset.rfl, hAB, hsmall, by simp⟩
  2. 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`.

    lines 8–27

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

    lines 44–56

    uses Finset.mem_filter.mp, Finset.mem_filter.mpr, in833_select_thresholds

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

    lines 57–64

    uses Finset.filter_subset, Finset.card_pos.mp, Finset.card_sdiff_add_card_eq_card

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

    lines 65–84

    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_le

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

    lines 85–94

    uses Finset.mem_sdiff.mp, Finset.mem_filter.mpr

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

    lines 95–104

    uses Finset.mem_filter.mp, Finset.mem_sdiff.mp, Finset.mem_filter.mpr, Finset.mem_sdiff.mpr, Finset.card_le_card

      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
  8. 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`.

    lines 105–109

    uses Finset.sdiff_subset

      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⟩
  9. 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.

    lines 126–141

    uses in833_threshold_general

      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⟩
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).

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

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