AFTD Auto-Formalizing Theoretical Domains

digraph_general_robust_two_cycle_free_cut

theoremverified

Assuming the displayed robust two-cycle criterion, every two-cycle-free part of size at least d in a graph with outdegree at least d on the part has at least choose(d,2)−1 outgoing arcs, for d≥3.

Statement

theorem digraph_general_robust_two_cycle_free_cut
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (d : ℕ) (hd : 3 ≤ d) (B : Finset α) (hB : d ≤ B.card)
    (hdeg : ∀ v ∈ B, d ≤ (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))) :
    Nat.choose d 2 - 1 ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card
Source
General form of the robust two-cycle cut-layer argument for OP-110; experiment 26331 checks the finite layer optimization for d through 24.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

To bound from below the number of outgoing arcs from a vertex set B of size at least d having outdegree at least d and containing no two disjoint directed cycles, the proof counts vertices by their external outdegree a(v) = |N⁺(v) ∩ Bᶜ| using layer-cake summation. For each threshold j ∈ {1, ..., d-2}, either at least d - 1 - j vertices have a(v) ≥ j + 1, or the remaining subgraph B \ S forces—via the contrapositive of the robust two-cycle criterion—at least three vertices to have a(v) = j, giving at least d + 1 - j vertices with a(v) ≥ j. An arithmetic charging argument on the excess sequence E(k) = n(k+1) + k - (d-1) proves that any decreasing sequence satisfying this dichotomy has sum ∑_{k=0}^{d-2} n(k+1) ≥ choose(d, 2) - 1. Combining this arithmetic bound with the layer-cake inequality completes the proof.

  1. The cardinality of the set of elements in the universe satisfying p equals the cardinality of the union (B ∩ p) ∪ (Bᶜ ∩ p).

    Applying Finset.card_union_of_disjoint expresses the sum of sizes of two disjoint finsets as the size of their union. By extensionality and propositional logic, the elements of univ satisfying p coincide with (B ∩ p) ∪ (Bᶜ ∩ p).

    lines 4–7

    uses Finset.card_union_of_disjoint, Finset.mem_filter

      classical
      rw [← Finset.card_union_of_disjoint]
      · congr 1
        ext x; simp [Finset.mem_filter]; tauto
  2. The filtered sets B ∩ p and Bᶜ ∩ p are disjoint, completing the proof of digraph_general_robust_two_cycle_free_cut_aux_partition_card.

    By Finset.disjoint_left, it suffices to check that no element belongs to both sets. Any common element would have to belong to both B and its complement Bᶜ, a direct contradiction.

    lines 8–11

    uses Finset.disjoint_left, Finset.mem_filter, Finset.mem_compl

      · rw [Finset.disjoint_left]
        intro x hx hy
        simp only [Finset.mem_filter, Finset.mem_compl] at hx hy
        exact hy.1 hx.1
  3. Filtering a set difference B \ S by p equals the set difference of the filtered sets (B ∩ p) \ (S ∩ p).

    By extensionality, an element x is in (B \ S) ∩ p if and only if x ∈ B, x ∉ S, and p(x) holds. Propositional logic simplifies this to (x ∈ B ∧ p(x)) ∧ ¬(x ∈ S ∧ p(x)).

    lines 16–19

    uses Finset.mem_filter, Finset.mem_sdiff

      classical
      ext x
      simp only [Finset.mem_filter, Finset.mem_sdiff]
      tauto
  4. When S ⊆ B, the cardinality of (B \ S) ∩ p is |B ∩ p| - |S ∩ p|.

    By digraph_general_robust_two_cycle_free_cut_aux_filter_sdiff, the filtered set is (B ∩ p) \ (S ∩ p). Since S ⊆ B implies S ∩ p ⊆ B ∩ p, the intersection of the two filtered sets is S ∩ p, so Finset.card_sdiff gives the difference of their cardinalities.

    lines 24–30

    uses digraph_general_robust_two_cycle_free_cut_aux_filter_sdiff, Finset.mem_filter, Finset.card_sdiff

      classical
      rw [digraph_general_robust_two_cycle_free_cut_aux_filter_sdiff]
      have hsub : S.filter p ⊆ B.filter p := by
        intro x hx
        simp only [Finset.mem_filter] at hx ⊢
        exact ⟨hSB hx.1, hx.2⟩
      rw [Finset.card_sdiff, Finset.inter_eq_left.mpr hsub]
  5. Define S = {v ∈ B | a(v) ≥ j + 1}; if |S| ≥ d - 1 - j, the first alternative holds.

    We define a(v) as the number of outgoing arcs from v into Bᶜ, and S as the subset of B where a(v) ≥ j + 1. Case analysis on whether |S| ≥ d - 1 - j directly dispatches the positive case via Or.inl.

    lines 46–52

    uses Finset.filter_subset, Or.inl

      classical
      set a : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card with ha
      set S : Finset α := B.filter (fun v => j + 1 ≤ a v) with hS
      have hSB : S ⊆ B := Finset.filter_subset _ _
      by_cases hSc : d - 1 - j ≤ S.card
      · exact Or.inl hSc
      · right
  6. If |S| ≤ d - 2 - j, the complement T = B \ S has size at least j + 2 ≥ 3, hence is nonempty.

    Since S ⊆ B, we have |B \ S| = |B| - |S| ≥ d - (d - 2 - j) = j + 2. Because j ≥ 1, this cardinality is at least 3, which implies B \ S is nonempty.

    lines 53–62

    uses Finset.sdiff_subset, Finset.card_sdiff_add_card_eq_card, Finset.nonempty_iff_ne_empty

        have hScard_le : S.card ≤ d - 2 - j := by omega
        have hTS : B \ S ⊆ B := Finset.sdiff_subset
        have hTcard : j + 2 ≤ (B \ S).card := by
          have h := Finset.card_sdiff_add_card_eq_card hSB
          omega
        have hTne : (B \ S).Nonempty := by
          rw [Finset.nonempty_iff_ne_empty]
          intro h
          rw [h] at hTcard
          simp at hTcard
  7. For every vertex v, its total outdegree decomposes as its outdegree in B plus a(v).

    By digraph_general_robust_two_cycle_free_cut_aux_partition_card applied to the neighborhood of v, the total outdegree is the sum of outdegrees into B and Bᶜ, the latter being a(v) by definition.

    lines 63–68

    uses digraph_general_robust_two_cycle_free_cut_aux_partition_card

        have hsplit : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card
            = (B.filter fun w => D.Adj v w).card + a v := by
          intro v
          have h := digraph_general_robust_two_cycle_free_cut_aux_partition_card B (fun w => D.Adj v w)
          have hav : a v = (Bᶜ.filter fun w => D.Adj v w).card := rfl
          omega
  8. Every vertex in B \ S has outdegree at least 2 in B \ S.

    Any vertex v ∈ B \ S is not in S, so a(v) ≤ j. Its total outdegree is at least d, so its outdegree into B is at least d - a(v) ≥ d - j. Removing S reduces this outdegree by at most |S| ≤ d - 2 - j, leaving an outdegree in B \ S of at least (d - j) - (d - 2 - j) = 2.

    lines 69–81

    uses Finset.mem_sdiff, Finset.mem_filter, digraph_general_robust_two_cycle_free_cut_aux_card_sdiff_filter, Finset.card_le_card, Finset.filter_subset

        have hmin : ∀ v ∈ B \ S, 2 ≤ ((B \ S).filter fun w => D.Adj v w).card := by
          intro v hv
          have hvB : v ∈ B := hTS hv
          have hvS : v ∉ S := (Finset.mem_sdiff.mp hv).2
          have hav : a v ≤ j := by
            by_contra h
            exact hvS (Finset.mem_filter.mpr ⟨hvB, by omega⟩)
          have hsp := hsplit v
          have hdegv := hdeg v hvB
          have hcard := digraph_general_robust_two_cycle_free_cut_aux_card_sdiff_filter B S (fun w => D.Adj v w) hSB
          have hSf : (S.filter fun w => D.Adj v w).card ≤ S.card :=
            Finset.card_le_card (Finset.filter_subset _ _)
          omega
  9. At least 3 vertices in B \ S have outdegree in B \ S strictly less than 3.

    If there were at most 2 such vertices, the robust two-cycle criterion would yield two disjoint directed cycles in B \ S. Since B \ S ⊆ B, these would also be disjoint directed cycles in B, contradicting the hypothesis hno.

    lines 82–87

    uses Finset.Subset.trans

        have hcnt3 : 3 ≤ ((B \ S).filter fun v => ((B \ S).filter fun w => D.Adj v w).card < 3).card := by
          by_contra h
          push_neg at h
          have h2 : ((B \ S).filter fun v => ((B \ S).filter fun w => D.Adj v w).card < 3).card ≤ 2 := by omega
          obtain ⟨c, hc⟩ := hrobust (B \ S) hTne hmin h2
          exact hno ⟨c, fun i => ⟨Finset.Subset.trans (hc.1 i).1 hTS, (hc.1 i).2⟩, hc.2⟩
  10. The cardinality of S is exactly d - 2 - j.

    For every vertex v ∈ B \ S with outdegree < 3 in B \ S, its outdegree into B is at most 2 + |S|. But it is also at least d - a(v) ≥ d - j. This forces d - j ≤ 2 + |S|, so |S| ≥ d - 2 - j. Since we are in the case |S| ≤ d - 2 - j, equality |S| = d - 2 - j must hold.

    lines 88–109

    uses Finset.mem_filter, Finset.mem_sdiff, digraph_general_robust_two_cycle_free_cut_aux_card_sdiff_filter, Finset.card_le_card, Finset.filter_subset, Finset.card_pos

        have hsmall : ∀ v ∈ (B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3),
            a v ≤ j ∧ d - j ≤ (B.filter fun w => D.Adj v w).card
              ∧ (B.filter fun w => D.Adj v w).card ≤ 2 + S.card := by
          intro v hv
          obtain ⟨hvT, hlt⟩ := Finset.mem_filter.mp hv
          have hvB : v ∈ B := hTS hvT
          have hvS : v ∉ S := (Finset.mem_sdiff.mp hvT).2
          have hav : a v ≤ j := by
            by_contra h
            exact hvS (Finset.mem_filter.mpr ⟨hvB, by omega⟩)
          have hsp := hsplit v
          have hdegv := hdeg v hvB
          have hcard := digraph_general_robust_two_cycle_free_cut_aux_card_sdiff_filter B S (fun w => D.Adj v w) hSB
          have hSf : (S.filter fun w => D.Adj v w).card ≤ S.card :=
            Finset.card_le_card (Finset.filter_subset _ _)
          exact ⟨hav, by omega, by omega⟩
        have hSge : d - 2 - j ≤ S.card := by
          obtain ⟨v, hv⟩ := Finset.card_pos.mp (by omega : 0 < ((B \ S).filter fun v => ((B \ S).filter fun w => D.Adj v w).card < 3).card)
          have := (hsmall v hv).2.1
          have := (hsmall v hv).2.2
          omega
        have hSeq : S.card = d - 2 - j := by omega
  11. Every vertex in B \ S with outdegree < 3 in B \ S has exactly a(v) = j.

    For such a vertex v, its outdegree in B is sandwiched between d - j and 2 + |S| = d - j, so it is exactly d - j. Because the total outdegree is at least d, the outdegree a(v) into Bᶜ must be at least d - (d - j) = j, and since v ∉ S it is also at most j, forcing a(v) = j.

    lines 110–118

    uses Finset.mem_filter

        have hkey : ∀ v ∈ (B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3), a v = j := by
          intro v hv
          obtain ⟨hvT, hlt⟩ := Finset.mem_filter.mp hv
          obtain ⟨hav, hlow, hup⟩ := hsmall v hv
          have hvB : v ∈ B := hTS hvT
          have hsp := hsplit v
          have hdegv := hdeg v hvB
          have hb : (B.filter fun w => D.Adj v w).card = d - j := by omega
          omega
  12. At least d + 1 - j vertices in B satisfy a(v) ≥ j, completing the proof of digraph_general_robust_two_cycle_free_cut_aux_threshold.

    The set of vertices with a(v) ≥ j contains both S (where a(v) ≥ j + 1) and the vertices in B \ S of outdegree < 3 in B \ S (where a(v) = j). Because these two subsets are disjoint, the size of their union is at least |S| + 3 = (d - 2 - j) + 3 = d + 1 - j.

    lines 119–142

    uses Finset.mem_filter, Finset.disjoint_left, Finset.mem_sdiff, Finset.card_union_of_disjoint, Finset.card_le_card, Finset.union_subset

        have hnj : d + 1 - j ≤ (B.filter fun v => j ≤ a v).card := by
          have hSsub : S ⊆ B.filter (fun v => j ≤ a v) := by
            intro v hv
            have hh : v ∈ B ∧ j + 1 ≤ a v := Finset.mem_filter.mp hv
            exact Finset.mem_filter.mpr ⟨hh.1, by omega⟩
          have hXsub : (B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3)
              ⊆ B.filter (fun v => j ≤ a v) := by
            intro v hv
            have hvT : v ∈ B \ S := (Finset.mem_filter.mp hv).1
            have hone : a v = j := hkey v hv
            exact Finset.mem_filter.mpr ⟨hTS hvT, by omega⟩
          have hdisj : Disjoint S ((B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3)) := by
            rw [Finset.disjoint_left]
            intro v hvS hvX
            have hvT : v ∈ B \ S := (Finset.mem_filter.mp hvX).1
            exact (Finset.mem_sdiff.mp hvT).2 hvS
          have hunion : (S ∪ (B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3)).card
              = S.card + ((B \ S).filter fun v => ((B \ S).filter fun w => D.Adj v w).card < 3).card :=
            Finset.card_union_of_disjoint hdisj
          have hle : (S ∪ (B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3)).card
              ≤ (B.filter fun v => j ≤ a v).card :=
            Finset.card_le_card (Finset.union_subset hSsub hXsub)
          omega
        exact hnj
  13. The layer-cake sum ∑_{k=0}^{M-1} |{v ∈ B | a(v) ≥ k+1}| is at most ∑_{v ∈ B} a(v).

    By Finset.card_filter, each set cardinality is the sum of indicators 1_{k+1 ≤ a(v)}. Exchanging the order of summation with Finset.sum_comm yields ∑_{v ∈ B} ∑_{k=0}^{M-1} 1_{k < a(v)}. For each v, the inner sum counts indices k < min(M, a(v)), which is at most a(v).

    lines 147–168

    uses Finset.card_filter, Finset.sum_comm, Finset.sum_le_sum, Finset.sum_filter, Finset.sum_const_nat, Finset.mem_filter, Finset.mem_range, Finset.card_le_card, Finset.card_range

      classical
      have h1 : ∀ k, (B.filter fun v => k+1 ≤ a v).card = ∑ v ∈ B, (if k+1 ≤ a v then 1 else 0) := by
        intro k; rw [Finset.card_filter]
      simp only [h1]
      rw [Finset.sum_comm]
      apply Finset.sum_le_sum
      intro v hv
      have h2 : ∑ k ∈ Finset.range M, (if k+1 ≤ a v then 1 else 0)
          = ∑ k ∈ (Finset.range M).filter (fun k => k+1 ≤ a v), (1:ℕ) := by
        rw [Finset.sum_filter]
      rw [h2]
      have h3 : ((Finset.range M).filter (fun k => k+1 ≤ a v)).card * 1
          = ∑ k ∈ (Finset.range M).filter (fun k => k+1 ≤ a v), (1:ℕ) := by
        rw [Finset.sum_const_nat]; intro x hx; rfl
      rw [← h3]
      have hsub : (Finset.range M).filter (fun k => k+1 ≤ a v) ⊆ Finset.range (a v) := by
        intro k hk
        simp only [Finset.mem_filter, Finset.mem_range] at hk ⊢
        omega
      have := Finset.card_le_card hsub
      simp only [Finset.card_range] at this
      omega
  14. The identity 2 * ∑_{k=0}^{m-1} k = m(m-1) holds in ℤ for all m ∈ ℕ. automation

    We proceed by induction on m. The base case m = 0 is immediate. The induction step splits off the term m using Finset.sum_range_succ, and nonlinear integer arithmetic closes the goal.

    lines 172–177

    uses Finset.sum_range_succ

      induction m with
      | zero => simp
      | succ m ih =>
        rw [Finset.sum_range_succ]
        push_cast
        nlinarith [ih]
  15. For the excess function E(k) = n(k+1) + k - (d - 1), every k ∈ {0, ..., d-2} satisfies E(k) ≥ -1.

    When k = d - 2, E(d-2) = n(d-1) - 1 ≥ -1. When k ≤ d - 3, assuming E(k) ≤ -2 means n(k+1) + k ≤ d - 3, which contradicts the second alternative d + 1 - (k+1) ≤ n(k+1) at j = k+1. Thus the first alternative d - 1 - (k+1) ≤ n(k+2) must hold, forcing E(k+1) ≥ 0. But monotonicity n(k+2) ≤ n(k+1) forces E(k+1) ≤ -1, a contradiction.

    lines 185–224

    uses Nat.cast_sub, Finset.mem_range, Nat.lt_or_ge

      classical
      have hdm : ((d - 1 : ℕ) : ℤ) = (d : ℤ) - 1 := by
        rw [Nat.cast_sub (by omega : (1:ℕ) ≤ d)]; try norm_num
      set E : ℕ → ℤ := fun k => (n (k + 1) : ℤ) + (k : ℤ) - ((d : ℤ) - 1) with hE
      have hE1 : ∀ k ∈ Finset.range (d - 1), -1 ≤ E k := by
        intro k hk
        rw [Finset.mem_range] at hk
        rcases Nat.lt_or_ge k (d - 2) with hlt | hge
        · have hk3 : k ≤ d - 3 := by omega
          by_contra hcon
          push_neg at hcon
          have hA : (n (k+1) : ℤ) + (k:ℤ) ≤ (d:ℤ) - 3 := by
            simp only [hE] at hcon; push_cast at hcon ⊢; linarith
          have hAn : n (k+1) + k ≤ d - 3 := by
            have h3 : ((d - 3 : ℕ) : ℤ) = (d:ℤ) - 3 := by
              rw [Nat.cast_sub (by omega : (3:ℕ) ≤ d)]; try norm_num
            have : ((n (k+1) + k : ℕ) : ℤ) ≤ ((d - 3 : ℕ) : ℤ) := by push_cast; linarith
            exact_mod_cast this
          have hnot2 : ¬ (d + 1 - (k+1) ≤ n (k+1)) := by
            intro h; omega
          have h1 : 1 ≤ k+1 := by omega
          have h2 : k+1 ≤ d-2 := by omega
          rcases halt (k+1) h1 h2 with h | h
          · have hd1 : d ≤ n (k+1+1) + (k+2) := by omega
            have hE0 : 0 ≤ E (k+1) := by
              simp only [hE]
              have hcast : (d:ℤ) ≤ (n (k+1+1) : ℤ) + ((k+2 : ℕ) : ℤ) := by exact_mod_cast hd1
              push_cast at hcast ⊢
              linarith
            have hm := hmono (k+1) (k+1+1) (by omega)
            have hcast2 : (n (k+1+1) : ℤ) ≤ (n (k+1) : ℤ) := by exact_mod_cast hm
            have hEle : E (k+1) ≤ -1 := by
              simp only [hE]; push_cast; linarith
            linarith
          · exact absurd h hnot2
        · have hkc : (k : ℤ) = (d : ℤ) - 2 := by
            rw [show k = d - 2 by omega, Nat.cast_sub (by omega : (2:ℕ) ≤ d)]; try norm_num
          simp only [hE]
          have hpos : (0:ℤ) ≤ (n (k+1) : ℤ) := by positivity
          linarith
  16. The set of indices where E(k) = -1 is contained in {k+1 | E(k) ≥ 1} ∪ {0}.

    If E(k) = -1 and k > 0, we apply the threshold hypothesis at j = k. The first alternative d - 1 - k ≤ n(k+1) would imply E(k) ≥ 0, which is false. Hence the second alternative d + 1 - k ≤ n(k) holds, which rearranges to E(k-1) ≥ 1, showing k - 1 ∈ P and thus k ∈ P + 1.

    lines 225–253

    uses Finset.mem_filter, Finset.mem_range, Finset.mem_union, Finset.mem_image, Finset.mem_singleton, Or.inr, Nat.cast_sub

      have hMP : (Finset.range (d-1)).filter (fun k => E k = -1) ⊆
          ((Finset.range (d-1)).filter (fun k => 1 ≤ E k)).image (fun k => k + 1) ∪ {0} := by
        intro k hk
        simp only [Finset.mem_filter, Finset.mem_range, Finset.mem_union, Finset.mem_image,
          Finset.mem_singleton] at hk ⊢
        obtain ⟨hklt, hkE⟩ := hk
        by_cases hk0 : k = 0
        · exact Or.inr hk0
        · left
          have hk1 : 1 ≤ k := by omega
          have hk2 : k ≤ d - 2 := by omega
          rcases halt k hk1 hk2 with h | h
          · exfalso
            have hE0 : 0 ≤ E k := by
              simp only [hE]
              have hcast : ((d - 1 - k : ℕ) : ℤ) = (d:ℤ) - 1 - (k:ℤ) := by
                rw [Nat.cast_sub (by omega : k ≤ d - 1), hdm]; try norm_num
              have hle : ((d - 1 - k : ℕ) : ℤ) ≤ (n (k+1) : ℤ) := by exact_mod_cast h
              push_cast
              linarith
            linarith
          · refine ⟨k - 1, ⟨by omega, ?_⟩, by omega⟩
            have hkk : k - 1 + 1 = k := by omega
            have hcast : ((d + 1 - k : ℕ) : ℤ) = (d:ℤ) + 1 - (k:ℤ) := by
              rw [Nat.cast_sub (by omega : k ≤ d + 1)]; push_cast; try ring
            have hle : ((d + 1 - k : ℕ) : ℤ) ≤ (n k : ℤ) := by exact_mod_cast h
            simp only [hE, hkk]
            push_cast
            linarith
  17. The sum of the excesses ∑_{k=0}^{d-2} E(k) is at least -1.

    Let S = {0, ..., d-2}, M = {k ∈ S | E(k) = -1}, and P = {k ∈ S | E(k) ≥ 1}. Splitting the sum of E(k) + 1 over S gives ∑_{k ∈ S} (E(k)+1) = ∑_{k ∈ S \ M} (E(k)+1) ≥ |S \ M| + |P| = |S| - |M| + |P|. Since M ⊆ (P+1) ∪ {0}, we have |M| ≤ |P| + 1, so |P| - |M| ≥ -1. Subtracting |S| yields ∑_{k ∈ S} E(k) ≥ -1.

    lines 254–315

    uses Finset.filter_subset, Finset.mem_filter, Finset.mem_sdiff, Finset.sum_eq_zero, Finset.sum_sdiff, if_pos, if_neg, Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_boole, Finset.filter_mem_eq_inter, Finset.card_sdiff_add_card_eq_card, Finset.card_le_card, Finset.card_union_le, Finset.card_image_le, Finset.card_singleton

      have hsumE : (-1 : ℤ) ≤ ∑ k ∈ Finset.range (d - 1), E k := by
        set S := Finset.range (d - 1) with hS
        set M := S.filter (fun k => E k = -1) with hM
        set P := S.filter (fun k => 1 ≤ E k) with hP
        have hMS : M ⊆ S := Finset.filter_subset _ _
        have hPS : P ⊆ S := Finset.filter_subset _ _
        have hPM : P ⊆ S \ M := by
          intro x hx
          obtain ⟨hxS, hxE⟩ := Finset.mem_filter.mp hx
          exact Finset.mem_sdiff.mpr ⟨hxS, by intro h; rw [Finset.mem_filter] at h; linarith [h.2]⟩
        have hM0 : ∑ k ∈ M, (E k + 1) = 0 := by
          rw [Finset.sum_eq_zero]
          intro k hk
          have := (Finset.mem_filter.mp hk).2
          linarith
        have hsplit : ∑ k ∈ S, (E k + 1) = ∑ k ∈ M, (E k + 1) + ∑ k ∈ S \ M, (E k + 1) := by
          have := Finset.sum_sdiff hMS (f := fun k => E k + 1)
          linarith [this]
        have hpt : ∀ k ∈ S \ M, (1:ℤ) + (if k ∈ P then 1 else 0) ≤ E k + 1 := by
          intro k hk
          obtain ⟨hkS, hkM⟩ := Finset.mem_sdiff.mp hk
          by_cases hkP : k ∈ P
          · simp only [if_pos hkP]
            have := (Finset.mem_filter.mp hkP).2
            linarith
          · simp only [if_neg hkP]
            have h1 := hE1 k hkS
            have hne : E k ≠ -1 := by intro h; exact hkM (Finset.mem_filter.mpr ⟨hkS, h⟩)
            omega
        have hrest : ((S \ M).card : ℤ) + (P.card : ℤ) ≤ ∑ k ∈ S \ M, (E k + 1) := by
          have hle := Finset.sum_le_sum hpt
          have heq1 : ∑ k ∈ S \ M, ((1:ℤ) + (if k ∈ P then 1 else 0))
              = ((S \ M).card : ℤ) + ∑ k ∈ S \ M, (if k ∈ P then (1:ℤ) else 0) := by
            rw [Finset.sum_add_distrib]
            simp
          have heq2 : ∑ k ∈ S \ M, (if k ∈ P then (1:ℤ) else 0) = (P.card : ℤ) := by
            rw [Finset.sum_boole]
            have : (S \ M).filter (fun k => k ∈ P) = P := by
              rw [Finset.filter_mem_eq_inter, Finset.inter_eq_right.mpr hPM]
            rw [this]
          rw [heq1, heq2] at hle
          exact hle
        have hSMcard : ((S \ M).card : ℤ) = (S.card : ℤ) - (M.card : ℤ) := by
          have h := Finset.card_sdiff_add_card_eq_card hMS
          push_cast [h]; linarith
        have hPle : (P.card : ℤ) - (M.card : ℤ) ≥ -1 := by
          have hm : M ⊆ P.image (fun k => k + 1) ∪ {0} := hMP
          have h1 : M.card ≤ (P.image (fun k => k + 1) ∪ {0}).card := Finset.card_le_card hm
          have h2 : (P.image (fun k => k + 1) ∪ {0}).card ≤ P.card + 1 := by
            have h4 := Finset.card_union_le (P.image (fun k => k + 1)) ({0} : Finset ℕ)
            have h3 : (P.image (fun k => k + 1)).card ≤ P.card := Finset.card_image_le
            simp only [Finset.card_singleton] at h4 ⊢
            omega
          omega
        have hSsum : (S.card : ℤ) = (M.card : ℤ) + ((S \ M).card : ℤ) := by
          rw [hSMcard]; ring
        have hES : ∑ k ∈ S, E k = ∑ k ∈ S, (E k + 1) - (S.card : ℤ) := by
          rw [Finset.sum_add_distrib]
          simp
        rw [show ∑ k ∈ Finset.range (d-1), E k = ∑ k ∈ S, E k from rfl, hES, hsplit, hM0]
        linarith
      have hEsum : ∑ k ∈ Finset.range (d-1), E k
  18. The sum ∑_{k=0}^{d-2} n(k+1) is at least choose(d, 2) - 1, proving digraph_general_robust_two_cycle_free_cut_aux_arith.

    Expanding ∑ E(k) gives ∑ n(k+1) + ∑ k - (d-1)². Combining this with digraph_general_robust_two_cycle_free_cut_aux_sum_cast_double and ∑ E(k) ≥ -1 gives 2 * ∑ n(k+1) ≥ d(d-1) - 2. Dividing by 2 and using Nat.choose_two_right establishes the bound choose(d, 2) - 1 ≤ ∑ n(k+1).

    lines 316–341

    uses Finset.sum_sub_distrib, Finset.sum_add_distrib, Finset.card_range, digraph_general_robust_two_cycle_free_cut_aux_sum_cast_double, Nat.cast_mul, Nat.div_le_iff_le_mul, Nat.choose_two_right

          = (∑ k ∈ Finset.range (d-1), (n (k+1) : ℤ))
            + (∑ k ∈ Finset.range (d-1), (k:ℤ)) - ((d-1 : ℕ) : ℤ) * ((d:ℤ) - 1) := by
        simp only [hE]
        rw [Finset.sum_sub_distrib, Finset.sum_add_distrib]
        simp [Finset.card_range]
        try ring
      have hfinal : (d : ℤ) * ((d:ℤ) - 1) - 2 ≤ 2 * ∑ k ∈ Finset.range (d-1), (n (k+1) : ℤ) := by
        have hid := digraph_general_robust_two_cycle_free_cut_aux_sum_cast_double (d-1)
        rw [hdm] at hid
        have hsE := hsumE
        rw [hEsum, hdm] at hsE
        nlinarith [hsE, hid]
      have hnat : d * (d-1) ≤ 2 * (∑ k ∈ Finset.range (d-1), n (k+1) + 1) := by
        have h1' : ((d*(d-1) : ℕ) : ℤ) = (d:ℤ) * ((d:ℤ)-1) := by
          rw [Nat.cast_mul, hdm]; try ring
        have h2' : ((2 * (∑ k ∈ Finset.range (d-1), n (k+1) + 1) : ℕ) : ℤ)
            = 2 * ((∑ k ∈ Finset.range (d-1), (n (k+1) : ℤ)) + 1) := by
          push_cast; try ring
        have : ((d*(d-1) : ℕ) : ℤ) ≤ ((2 * (∑ k ∈ Finset.range (d-1), n (k+1) + 1) : ℕ) : ℤ) := by
          rw [h1', h2']; linarith [hfinal]
        exact_mod_cast this
      have h2 : d * (d - 1) / 2 ≤ ∑ k ∈ Finset.range (d-1), n (k+1) + 1 := by
        rw [Nat.div_le_iff_le_mul (by norm_num : 0 < 2)]
        omega
      rw [Nat.choose_two_right]
      omega
  19. With a(v) = |N⁺(v) ∩ Bᶜ|, the sequence n(k) = |{v ∈ B | a(v) ≥ k}| is weakly decreasing.

    If i ≤ j, then a(v) ≥ j implies a(v) ≥ i, so the subset of vertices for j is contained in that for i. The cardinality inequality follows by Finset.card_le_card.

    lines 355–364

    uses Finset.card_le_card, Finset.mem_filter, le_trans

      classical
      set a : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card with ha
      set n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ a v).card with hn
      have hmono : ∀ i j : ℕ, i ≤ j → n j ≤ n i := by
        intro i j hij
        show (B.filter fun v => j ≤ a v).card ≤ (B.filter fun v => i ≤ a v).card
        apply Finset.card_le_card
        intro v hv
        simp only [Finset.mem_filter] at hv ⊢
        exact ⟨hv.1, le_trans hij hv.2⟩
  20. The sequence n satisfies the threshold dichotomy: d - 1 - j ≤ n(j+1) ∨ d + 1 - j ≤ n(j) for all 1 ≤ j ≤ d - 2.

    This is the statement of digraph_general_robust_two_cycle_free_cut_aux_threshold applied to D, B, and the hypotheses.

    lines 365–369

    uses digraph_general_robust_two_cycle_free_cut_aux_threshold

      have hthresh : ∀ j : ℕ, 1 ≤ j → j ≤ d - 2 →
          d - 1 - j ≤ n (j + 1) ∨ d + 1 - j ≤ n j := by
        intro j hj1 hj2
        show d - 1 - j ≤ (B.filter fun v => j + 1 ≤ a v).card ∨
          d + 1 - j ≤ (B.filter fun v => j ≤ a v).card
  21. The cut size ∑_{v ∈ B} a(v) is at least choose(d, 2) - 1, proving the theorem.

    By digraph_general_robust_two_cycle_free_cut_aux_arith, choose(d, 2) - 1 ≤ ∑_{k=0}^{d-2} n(k+1). By the layer-cake bound digraph_general_robust_two_cycle_free_cut_aux_layer_cake, this sum is at most ∑_{v ∈ B} a(v). Transitivity of ≤ yields the conclusion.

    lines 370–374

    uses digraph_general_robust_two_cycle_free_cut_aux_arith, digraph_general_robust_two_cycle_free_cut_aux_layer_cake, le_trans

        exact digraph_general_robust_two_cycle_free_cut_aux_threshold α D d hd B hB hdeg hrobust hno j hj1 hj2
      have harith := digraph_general_robust_two_cycle_free_cut_aux_arith d hd n hmono hthresh
      have hlayer := digraph_general_robust_two_cycle_free_cut_aux_layer_cake B a (d-1)
      have hlayer' : ∑ k ∈ Finset.range (d-1), n (k+1) ≤ ∑ v ∈ B, a v := hlayer
      exact le_trans harith hlayer'
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.mem_filter
An element belongs to a filtered set {x ∈ s | p x} if and only if it belongs to s and satisfies p.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_compl
In a finite universe, an element belongs to the complement of s if and only if it does not belong to s.
Finset.mem_sdiff
An element belongs to the set difference s \ t if and only if it is in s and not in t.
digraph_general_robust_two_cycle_free_cut_aux_filter_sdiff
Filtering a set difference (B \ S) by a predicate p equals the set difference of the filtered sets (B ∩ p) \ (S ∩ p).
Finset.card_sdiff
The cardinality of t \ s is |t| - |s ∩ t|.
Finset.filter_subset
The filtered set {x ∈ s | p x} is a subset of s.
Or.inl
Introduces the left disjunct of a disjunction A ∨ B.
Finset.sdiff_subset
The set difference s \ t is a subset of s.
Finset.card_sdiff_add_card_eq_card
If s ⊆ t, then |t \ s| + |s| = |t|.
Finset.nonempty_iff_ne_empty
A finite set is nonempty if and only if it is not the empty set.
digraph_general_robust_two_cycle_free_cut_aux_partition_card
For any subset B of a finite universe, the number of elements satisfying p is the sum of those in B and those in Bᶜ satisfying p.
digraph_general_robust_two_cycle_free_cut_aux_card_sdiff_filter
If S ⊆ B, the number of elements in B \ S satisfying p is |B ∩ p| - |S ∩ p|.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
Finset.Subset.trans
Subset inclusion is transitive.
Finset.card_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
Finset.union_subset
If s ⊆ u and t ⊆ u, then s ∪ t ⊆ u.
Finset.card_filter
The cardinality of {x ∈ s | p x} equals the sum over x ∈ s of the indicator of p(x).
Finset.sum_comm
Fubini's theorem for finite sums: exchanging the order of summation preserves the sum.
Finset.sum_le_sum
If f(x) ≤ g(x) for all x ∈ s, then ∑_{x ∈ s} f(x) ≤ ∑_{x ∈ s} g(x).
Finset.sum_filter
Summing f(x) over elements of s satisfying p equals summing if p(x) then f(x) else 0 over all x ∈ s.
Finset.sum_const_nat
The sum of a constant natural number m over a finite set s is |s| * m.
Finset.mem_range
A natural number m belongs to range(n) = {0, ..., n-1} if and only if m < n.
Finset.card_range
The cardinality of range(n) is n.
Finset.sum_range_succ
Splitting off the last term of a sum: ∑_{k=0}^n f(k) = ∑_{k=0}^{n-1} f(k) + f(n).
Nat.cast_sub
If m ≤ n, the difference n - m in ℕ casts to n - m in an ordered ring.
Nat.lt_or_ge
For any natural numbers n and m, either n < m or n ≥ m.
Finset.mem_union
An element is in s ∪ t if and only if it is in s or in t.
Finset.mem_image
An element y is in f(s) if and only if y = f(x) for some x ∈ s.
Finset.mem_singleton
An element is in the singleton {a} if and only if it equals a.
Or.inr
Introduces the right disjunct of a disjunction A ∨ B.
Finset.sum_eq_zero
If every term in a finite sum is zero, the sum is zero.
Finset.sum_sdiff
For s₁ ⊆ s₂, the sum over s₂ is the sum over s₂ \ s₁ plus the sum over s₁.
if_pos
If a condition c is true, then if c then t else e equals t.
if_neg
If a condition c is false, then if c then t else e equals e.
Finset.sum_add_distrib
The sum of a sum of functions is the sum of their individual sums.
Finset.sum_boole
The sum of the indicator function of p(x) over s is the cardinality of {x ∈ s | p x}.
Finset.filter_mem_eq_inter
Filtering a set s by membership in t gives the intersection s ∩ t.
Finset.card_union_le
The cardinality of the union s ∪ t is at most |s| + |t|.
Finset.card_image_le
The image of a finite set under a function has size at most the size of the set.
Finset.card_singleton
A singleton set has cardinality 1.
Finset.sum_sub_distrib
The sum of a difference of functions is the difference of their individual sums.
digraph_general_robust_two_cycle_free_cut_aux_sum_cast_double
The identity 2 * ∑_{k=0}^{m-1} k = m(m-1) holds in ℤ.
Nat.cast_mul
The product of natural numbers casts to the product in a target semiring.
Nat.div_le_iff_le_mul
For k > 0, x / k ≤ y if and only if x ≤ y * k + k - 1.
Nat.choose_two_right
The binomial coefficient choose(n, 2) equals n(n-1)/2.
le_trans
The preorder relation ≤ is transitive.
digraph_general_robust_two_cycle_free_cut_aux_threshold
Under the robust two-cycle hypothesis, for any j with 1 ≤ j ≤ d - 2, either |{v ∈ B | a(v) ≥ j+1}| ≥ d - 1 - j or |{v ∈ B | a(v) ≥ j}| ≥ d + 1 - j.
digraph_general_robust_two_cycle_free_cut_aux_arith
Any decreasing sequence n satisfying the threshold dichotomy has sum ∑_{k=0}^{d-2} n(k+1) ≥ choose(d, 2) - 1.
digraph_general_robust_two_cycle_free_cut_aux_layer_cake
Discrete layer cake formula: ∑_{k=0}^{M-1} |{v ∈ B | a(v) ≥ k+1}| ≤ ∑_{v ∈ B} a(v).

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

lemma digraph_general_robust_two_cycle_free_cut_aux_partition_card    {α : Type} [Fintype α] [DecidableEq α] (B : Finset α) (p : α → Prop) [DecidablePred p] :    (Finset.univ.filter p).card = (B.filter p).card + (Bᶜ.filter p).card := by  classical  rw [← Finset.card_union_of_disjoint]  · congr 1    ext x; simp [Finset.mem_filter]; tauto  · rw [Finset.disjoint_left]    intro x hx hy    simp only [Finset.mem_filter, Finset.mem_compl] at hx hy    exact hy.1 hx.1lemma digraph_general_robust_two_cycle_free_cut_aux_filter_sdiff    {α : Type} [DecidableEq α] (B S : Finset α) (p : α → Prop) [DecidablePred p] :    (B \ S).filter p = (B.filter p) \ (S.filter p) := by  classical  ext x  simp only [Finset.mem_filter, Finset.mem_sdiff]  tautolemma digraph_general_robust_two_cycle_free_cut_aux_card_sdiff_filter    {α : Type} [DecidableEq α] (B S : Finset α) (p : α → Prop) [DecidablePred p] (hSB : S ⊆ B) :    ((B \ S).filter p).card = (B.filter p).card - (S.filter p).card := by  classical  rw [digraph_general_robust_two_cycle_free_cut_aux_filter_sdiff]  have hsub : S.filter p ⊆ B.filter p := by    intro x hx    simp only [Finset.mem_filter] at hx ⊢    exact ⟨hSB hx.1, hx.2⟩  rw [Finset.card_sdiff, Finset.inter_eq_left.mpr hsub]lemma digraph_general_robust_two_cycle_free_cut_aux_threshold    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (d : ℕ) (hd : 3 ≤ d) (B : Finset α) (hB : d ≤ B.card)    (hdeg : ∀ v ∈ B, d ≤ (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)))    (j : ℕ) (hj1 : 1 ≤ j) (hj2 : j ≤ d - 2) :    d - 1 - j ≤ (B.filter fun v => j + 1 ≤ (Bᶜ.filter fun w => D.Adj v w).card).card ∨    d + 1 - j ≤ (B.filter fun v => j ≤ (Bᶜ.filter fun w => D.Adj v w).card).card := by  classical  set a : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card with ha  set S : Finset α := B.filter (fun v => j + 1 ≤ a v) with hS  have hSB : S ⊆ B := Finset.filter_subset _ _  by_cases hSc : d - 1 - j ≤ S.card  · exact Or.inl hSc  · right    have hScard_le : S.card ≤ d - 2 - j := by omega    have hTS : B \ S ⊆ B := Finset.sdiff_subset    have hTcard : j + 2 ≤ (B \ S).card := by      have h := Finset.card_sdiff_add_card_eq_card hSB      omega    have hTne : (B \ S).Nonempty := by      rw [Finset.nonempty_iff_ne_empty]      intro h      rw [h] at hTcard      simp at hTcard    have hsplit : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card        = (B.filter fun w => D.Adj v w).card + a v := by      intro v      have h := digraph_general_robust_two_cycle_free_cut_aux_partition_card B (fun w => D.Adj v w)      have hav : a v = (Bᶜ.filter fun w => D.Adj v w).card := rfl      omega    have hmin : ∀ v ∈ B \ S, 2 ≤ ((B \ S).filter fun w => D.Adj v w).card := by      intro v hv      have hvB : v ∈ B := hTS hv      have hvS : v ∉ S := (Finset.mem_sdiff.mp hv).2      have hav : a v ≤ j := by        by_contra h        exact hvS (Finset.mem_filter.mpr ⟨hvB, by omega⟩)      have hsp := hsplit v      have hdegv := hdeg v hvB      have hcard := digraph_general_robust_two_cycle_free_cut_aux_card_sdiff_filter B S (fun w => D.Adj v w) hSB      have hSf : (S.filter fun w => D.Adj v w).card ≤ S.card :=        Finset.card_le_card (Finset.filter_subset _ _)      omega    have hcnt3 : 3 ≤ ((B \ S).filter fun v => ((B \ S).filter fun w => D.Adj v w).card < 3).card := by      by_contra h      push_neg at h      have h2 : ((B \ S).filter fun v => ((B \ S).filter fun w => D.Adj v w).card < 3).card ≤ 2 := by omega      obtain ⟨c, hc⟩ := hrobust (B \ S) hTne hmin h2      exact hno ⟨c, fun i => ⟨Finset.Subset.trans (hc.1 i).1 hTS, (hc.1 i).2⟩, hc.2⟩    have hsmall : ∀ v ∈ (B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3),        a v ≤ j ∧ d - j ≤ (B.filter fun w => D.Adj v w).card          ∧ (B.filter fun w => D.Adj v w).card ≤ 2 + S.card := by      intro v hv      obtain ⟨hvT, hlt⟩ := Finset.mem_filter.mp hv      have hvB : v ∈ B := hTS hvT      have hvS : v ∉ S := (Finset.mem_sdiff.mp hvT).2      have hav : a v ≤ j := by        by_contra h        exact hvS (Finset.mem_filter.mpr ⟨hvB, by omega⟩)      have hsp := hsplit v      have hdegv := hdeg v hvB      have hcard := digraph_general_robust_two_cycle_free_cut_aux_card_sdiff_filter B S (fun w => D.Adj v w) hSB      have hSf : (S.filter fun w => D.Adj v w).card ≤ S.card :=        Finset.card_le_card (Finset.filter_subset _ _)      exact ⟨hav, by omega, by omega⟩    have hSge : d - 2 - j ≤ S.card := by      obtain ⟨v, hv⟩ := Finset.card_pos.mp (by omega : 0 < ((B \ S).filter fun v => ((B \ S).filter fun w => D.Adj v w).card < 3).card)      have := (hsmall v hv).2.1      have := (hsmall v hv).2.2      omega    have hSeq : S.card = d - 2 - j := by omega    have hkey : ∀ v ∈ (B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3), a v = j := by      intro v hv      obtain ⟨hvT, hlt⟩ := Finset.mem_filter.mp hv      obtain ⟨hav, hlow, hup⟩ := hsmall v hv      have hvB : v ∈ B := hTS hvT      have hsp := hsplit v      have hdegv := hdeg v hvB      have hb : (B.filter fun w => D.Adj v w).card = d - j := by omega      omega    have hnj : d + 1 - j ≤ (B.filter fun v => j ≤ a v).card := by      have hSsub : S ⊆ B.filter (fun v => j ≤ a v) := by        intro v hv        have hh : v ∈ B ∧ j + 1 ≤ a v := Finset.mem_filter.mp hv        exact Finset.mem_filter.mpr ⟨hh.1, by omega⟩      have hXsub : (B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3)          ⊆ B.filter (fun v => j ≤ a v) := by        intro v hv        have hvT : v ∈ B \ S := (Finset.mem_filter.mp hv).1        have hone : a v = j := hkey v hv        exact Finset.mem_filter.mpr ⟨hTS hvT, by omega⟩      have hdisj : Disjoint S ((B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3)) := by        rw [Finset.disjoint_left]        intro v hvS hvX        have hvT : v ∈ B \ S := (Finset.mem_filter.mp hvX).1        exact (Finset.mem_sdiff.mp hvT).2 hvS      have hunion : (S ∪ (B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3)).card          = S.card + ((B \ S).filter fun v => ((B \ S).filter fun w => D.Adj v w).card < 3).card :=        Finset.card_union_of_disjoint hdisj      have hle : (S ∪ (B \ S).filter (fun v => ((B \ S).filter fun w => D.Adj v w).card < 3)).card          ≤ (B.filter fun v => j ≤ a v).card :=        Finset.card_le_card (Finset.union_subset hSsub hXsub)      omega    exact hnjlemma digraph_general_robust_two_cycle_free_cut_aux_layer_cake    {α : Type} [Fintype α] [DecidableEq α] (B : Finset α) (a : α → ℕ) (M : ℕ) :    ∑ k ∈ Finset.range M, (B.filter fun v => k+1 ≤ a v).card ≤ ∑ v ∈ B, a v := by  classical  have h1 : ∀ k, (B.filter fun v => k+1 ≤ a v).card = ∑ v ∈ B, (if k+1 ≤ a v then 1 else 0) := by    intro k; rw [Finset.card_filter]  simp only [h1]  rw [Finset.sum_comm]  apply Finset.sum_le_sum  intro v hv  have h2 : ∑ k ∈ Finset.range M, (if k+1 ≤ a v then 1 else 0)      = ∑ k ∈ (Finset.range M).filter (fun k => k+1 ≤ a v), (1:ℕ) := by    rw [Finset.sum_filter]  rw [h2]  have h3 : ((Finset.range M).filter (fun k => k+1 ≤ a v)).card * 1      = ∑ k ∈ (Finset.range M).filter (fun k => k+1 ≤ a v), (1:ℕ) := by    rw [Finset.sum_const_nat]; intro x hx; rfl  rw [← h3]  have hsub : (Finset.range M).filter (fun k => k+1 ≤ a v) ⊆ Finset.range (a v) := by    intro k hk    simp only [Finset.mem_filter, Finset.mem_range] at hk ⊢    omega  have := Finset.card_le_card hsub  simp only [Finset.card_range] at this  omegalemma digraph_general_robust_two_cycle_free_cut_aux_sum_cast_double (m : ℕ) :    (2 : ℤ) * ∑ k ∈ Finset.range m, (k : ℤ) = (m : ℤ) * ((m : ℤ) - 1) := by  induction m with  | zero => simp  | succ m ih =>    rw [Finset.sum_range_succ]    push_cast    nlinarith [ih]lemma digraph_general_robust_two_cycle_free_cut_aux_arith    (d : ℕ) (hd : 3 ≤ d) (n : ℕ → ℕ)    (hmono : ∀ i j : ℕ, i ≤ j → n j ≤ n i)    (halt : ∀ j : ℕ, 1 ≤ j → j ≤ d - 2 →      d - 1 - j ≤ n (j + 1) ∨ d + 1 - j ≤ n j) :    Nat.choose d 2 - 1 ≤ ∑ k ∈ Finset.range (d - 1), n (k + 1) := by  classical  have hdm : ((d - 1 : ℕ) : ℤ) = (d : ℤ) - 1 := by    rw [Nat.cast_sub (by omega : (1:ℕ) ≤ d)]; try norm_num  set E : ℕ → ℤ := fun k => (n (k + 1) : ℤ) + (k : ℤ) - ((d : ℤ) - 1) with hE  have hE1 : ∀ k ∈ Finset.range (d - 1), -1 ≤ E k := by    intro k hk    rw [Finset.mem_range] at hk    rcases Nat.lt_or_ge k (d - 2) with hlt | hge    · have hk3 : k ≤ d - 3 := by omega      by_contra hcon      push_neg at hcon      have hA : (n (k+1) : ℤ) + (k:ℤ) ≤ (d:ℤ) - 3 := by        simp only [hE] at hcon; push_cast at hcon ⊢; linarith      have hAn : n (k+1) + k ≤ d - 3 := by        have h3 : ((d - 3 : ℕ) : ℤ) = (d:ℤ) - 3 := by          rw [Nat.cast_sub (by omega : (3:ℕ) ≤ d)]; try norm_num        have : ((n (k+1) + k : ℕ) : ℤ) ≤ ((d - 3 : ℕ) : ℤ) := by push_cast; linarith        exact_mod_cast this      have hnot2 : ¬ (d + 1 - (k+1) ≤ n (k+1)) := by        intro h; omega      have h1 : 1 ≤ k+1 := by omega      have h2 : k+1 ≤ d-2 := by omega      rcases halt (k+1) h1 h2 with h | h      · have hd1 : d ≤ n (k+1+1) + (k+2) := by omega        have hE0 : 0 ≤ E (k+1) := by          simp only [hE]          have hcast : (d:ℤ) ≤ (n (k+1+1) : ℤ) + ((k+2 : ℕ) : ℤ) := by exact_mod_cast hd1          push_cast at hcast ⊢          linarith        have hm := hmono (k+1) (k+1+1) (by omega)        have hcast2 : (n (k+1+1) : ℤ) ≤ (n (k+1) : ℤ) := by exact_mod_cast hm        have hEle : E (k+1) ≤ -1 := by          simp only [hE]; push_cast; linarith        linarith      · exact absurd h hnot2    · have hkc : (k : ℤ) = (d : ℤ) - 2 := by        rw [show k = d - 2 by omega, Nat.cast_sub (by omega : (2:ℕ) ≤ d)]; try norm_num      simp only [hE]      have hpos : (0:ℤ) ≤ (n (k+1) : ℤ) := by positivity      linarith  have hMP : (Finset.range (d-1)).filter (fun k => E k = -1) ⊆      ((Finset.range (d-1)).filter (fun k => 1 ≤ E k)).image (fun k => k + 1) ∪ {0} := by    intro k hk    simp only [Finset.mem_filter, Finset.mem_range, Finset.mem_union, Finset.mem_image,      Finset.mem_singleton] at hk ⊢    obtain ⟨hklt, hkE⟩ := hk    by_cases hk0 : k = 0    · exact Or.inr hk0    · left      have hk1 : 1 ≤ k := by omega      have hk2 : k ≤ d - 2 := by omega      rcases halt k hk1 hk2 with h | h      · exfalso        have hE0 : 0 ≤ E k := by          simp only [hE]          have hcast : ((d - 1 - k : ℕ) : ℤ) = (d:ℤ) - 1 - (k:ℤ) := by            rw [Nat.cast_sub (by omega : k ≤ d - 1), hdm]; try norm_num          have hle : ((d - 1 - k : ℕ) : ℤ) ≤ (n (k+1) : ℤ) := by exact_mod_cast h          push_cast          linarith        linarith      · refine ⟨k - 1, ⟨by omega, ?_⟩, by omega⟩        have hkk : k - 1 + 1 = k := by omega        have hcast : ((d + 1 - k : ℕ) : ℤ) = (d:ℤ) + 1 - (k:ℤ) := by          rw [Nat.cast_sub (by omega : k ≤ d + 1)]; push_cast; try ring        have hle : ((d + 1 - k : ℕ) : ℤ) ≤ (n k : ℤ) := by exact_mod_cast h        simp only [hE, hkk]        push_cast        linarith  have hsumE : (-1 : ℤ) ≤ ∑ k ∈ Finset.range (d - 1), E k := by    set S := Finset.range (d - 1) with hS    set M := S.filter (fun k => E k = -1) with hM    set P := S.filter (fun k => 1 ≤ E k) with hP    have hMS : M ⊆ S := Finset.filter_subset _ _    have hPS : P ⊆ S := Finset.filter_subset _ _    have hPM : P ⊆ S \ M := by      intro x hx      obtain ⟨hxS, hxE⟩ := Finset.mem_filter.mp hx      exact Finset.mem_sdiff.mpr ⟨hxS, by intro h; rw [Finset.mem_filter] at h; linarith [h.2]⟩    have hM0 : ∑ k ∈ M, (E k + 1) = 0 := by      rw [Finset.sum_eq_zero]      intro k hk      have := (Finset.mem_filter.mp hk).2      linarith    have hsplit : ∑ k ∈ S, (E k + 1) = ∑ k ∈ M, (E k + 1) + ∑ k ∈ S \ M, (E k + 1) := by      have := Finset.sum_sdiff hMS (f := fun k => E k + 1)      linarith [this]    have hpt : ∀ k ∈ S \ M, (1:ℤ) + (if k ∈ P then 1 else 0) ≤ E k + 1 := by      intro k hk      obtain ⟨hkS, hkM⟩ := Finset.mem_sdiff.mp hk      by_cases hkP : k ∈ P      · simp only [if_pos hkP]        have := (Finset.mem_filter.mp hkP).2        linarith      · simp only [if_neg hkP]        have h1 := hE1 k hkS        have hne : E k ≠ -1 := by intro h; exact hkM (Finset.mem_filter.mpr ⟨hkS, h⟩)        omega    have hrest : ((S \ M).card : ℤ) + (P.card : ℤ) ≤ ∑ k ∈ S \ M, (E k + 1) := by      have hle := Finset.sum_le_sum hpt      have heq1 : ∑ k ∈ S \ M, ((1:ℤ) + (if k ∈ P then 1 else 0))          = ((S \ M).card : ℤ) + ∑ k ∈ S \ M, (if k ∈ P then (1:ℤ) else 0) := by        rw [Finset.sum_add_distrib]        simp      have heq2 : ∑ k ∈ S \ M, (if k ∈ P then (1:ℤ) else 0) = (P.card : ℤ) := by        rw [Finset.sum_boole]        have : (S \ M).filter (fun k => k ∈ P) = P := by          rw [Finset.filter_mem_eq_inter, Finset.inter_eq_right.mpr hPM]        rw [this]      rw [heq1, heq2] at hle      exact hle    have hSMcard : ((S \ M).card : ℤ) = (S.card : ℤ) - (M.card : ℤ) := by      have h := Finset.card_sdiff_add_card_eq_card hMS      push_cast [h]; linarith    have hPle : (P.card : ℤ) - (M.card : ℤ) ≥ -1 := by      have hm : M ⊆ P.image (fun k => k + 1) ∪ {0} := hMP      have h1 : M.card ≤ (P.image (fun k => k + 1) ∪ {0}).card := Finset.card_le_card hm      have h2 : (P.image (fun k => k + 1) ∪ {0}).card ≤ P.card + 1 := by        have h4 := Finset.card_union_le (P.image (fun k => k + 1)) ({0} : Finset ℕ)        have h3 : (P.image (fun k => k + 1)).card ≤ P.card := Finset.card_image_le        simp only [Finset.card_singleton] at h4 ⊢        omega      omega    have hSsum : (S.card : ℤ) = (M.card : ℤ) + ((S \ M).card : ℤ) := by      rw [hSMcard]; ring    have hES : ∑ k ∈ S, E k = ∑ k ∈ S, (E k + 1) - (S.card : ℤ) := by      rw [Finset.sum_add_distrib]      simp    rw [show ∑ k ∈ Finset.range (d-1), E k = ∑ k ∈ S, E k from rfl, hES, hsplit, hM0]    linarith  have hEsum : ∑ k ∈ Finset.range (d-1), E k      = (∑ k ∈ Finset.range (d-1), (n (k+1) : ℤ))        + (∑ k ∈ Finset.range (d-1), (k:ℤ)) - ((d-1 : ℕ) : ℤ) * ((d:ℤ) - 1) := by    simp only [hE]    rw [Finset.sum_sub_distrib, Finset.sum_add_distrib]    simp [Finset.card_range]    try ring  have hfinal : (d : ℤ) * ((d:ℤ) - 1) - 2 ≤ 2 * ∑ k ∈ Finset.range (d-1), (n (k+1) : ℤ) := by    have hid := digraph_general_robust_two_cycle_free_cut_aux_sum_cast_double (d-1)    rw [hdm] at hid    have hsE := hsumE    rw [hEsum, hdm] at hsE    nlinarith [hsE, hid]  have hnat : d * (d-1) ≤ 2 * (∑ k ∈ Finset.range (d-1), n (k+1) + 1) := by    have h1' : ((d*(d-1) : ℕ) : ℤ) = (d:ℤ) * ((d:ℤ)-1) := by      rw [Nat.cast_mul, hdm]; try ring    have h2' : ((2 * (∑ k ∈ Finset.range (d-1), n (k+1) + 1) : ℕ) : ℤ)        = 2 * ((∑ k ∈ Finset.range (d-1), (n (k+1) : ℤ)) + 1) := by      push_cast; try ring    have : ((d*(d-1) : ℕ) : ℤ) ≤ ((2 * (∑ k ∈ Finset.range (d-1), n (k+1) + 1) : ℕ) : ℤ) := by      rw [h1', h2']; linarith [hfinal]    exact_mod_cast this  have h2 : d * (d - 1) / 2 ≤ ∑ k ∈ Finset.range (d-1), n (k+1) + 1 := by    rw [Nat.div_le_iff_le_mul (by norm_num : 0 < 2)]    omega  rw [Nat.choose_two_right]  omegatheorem digraph_general_robust_two_cycle_free_cut    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (d : ℕ) (hd : 3 ≤ d) (B : Finset α) (hB : d ≤ B.card)    (hdeg : ∀ v ∈ B, d ≤ (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))) :    Nat.choose d 2 - 1 ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card := by  classical  set a : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card with ha  set n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ a v).card with hn  have hmono : ∀ i j : ℕ, i ≤ j → n j ≤ n i := by    intro i j hij    show (B.filter fun v => j ≤ a v).card ≤ (B.filter fun v => i ≤ a v).card    apply Finset.card_le_card    intro v hv    simp only [Finset.mem_filter] at hv ⊢    exact ⟨hv.1, le_trans hij hv.2⟩  have hthresh : ∀ j : ℕ, 1 ≤ j → j ≤ d - 2 →      d - 1 - j ≤ n (j + 1) ∨ d + 1 - j ≤ n j := by    intro j hj1 hj2    show d - 1 - j ≤ (B.filter fun v => j + 1 ≤ a v).card ∨      d + 1 - j ≤ (B.filter fun v => j ≤ a v).card    exact digraph_general_robust_two_cycle_free_cut_aux_threshold α D d hd B hB hdeg hrobust hno j hj1 hj2  have harith := digraph_general_robust_two_cycle_free_cut_aux_arith d hd n hmono hthresh  have hlayer := digraph_general_robust_two_cycle_free_cut_aux_layer_cake B a (d-1)  have hlayer' : ∑ k ∈ Finset.range (d-1), n (k+1) ≤ ∑ v ∈ B, a v := hlayer  exact le_trans harith hlayer'
See it in the graphDiscuss this resultChallenge it