digraph_general_robust_two_cycle_free_cut
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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.
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).
uses
Finset.card_union_of_disjoint,Finset.mem_filterclassical rw [← Finset.card_union_of_disjoint] · congr 1 ext x; simp [Finset.mem_filter]; tauto
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.
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
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)).
uses
Finset.mem_filter,Finset.mem_sdiffclassical ext x simp only [Finset.mem_filter, Finset.mem_sdiff] tauto
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.
uses
digraph_general_robust_two_cycle_free_cut_aux_filter_sdiff,Finset.mem_filter,Finset.card_sdiffclassical 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]
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.
uses
Finset.filter_subset,Or.inlclassical 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
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.
uses
Finset.sdiff_subset,Finset.card_sdiff_add_card_eq_card,Finset.nonempty_iff_ne_emptyhave 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
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.
uses
digraph_general_robust_two_cycle_free_cut_aux_partition_cardhave 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
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.
uses
Finset.mem_sdiff,Finset.mem_filter,digraph_general_robust_two_cycle_free_cut_aux_card_sdiff_filter,Finset.card_le_card,Finset.filter_subsethave 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
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.
uses
Finset.Subset.transhave 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⟩
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.
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_poshave 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
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.
uses
Finset.mem_filterhave 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
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.
uses
Finset.mem_filter,Finset.disjoint_left,Finset.mem_sdiff,Finset.card_union_of_disjoint,Finset.card_le_card,Finset.union_subsethave 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
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).
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_rangeclassical 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
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.
uses
Finset.sum_range_succinduction m with | zero => simp | succ m ih => rw [Finset.sum_range_succ] push_cast nlinarith [ih]
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.
uses
Nat.cast_sub,Finset.mem_range,Nat.lt_or_geclassical 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
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.
uses
Finset.mem_filter,Finset.mem_range,Finset.mem_union,Finset.mem_image,Finset.mem_singleton,Or.inr,Nat.cast_subhave 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
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.
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_singletonhave 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
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).
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] omegaWith 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.
uses
Finset.card_le_card,Finset.mem_filter,le_transclassical 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⟩
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.
uses
digraph_general_robust_two_cycle_free_cut_aux_thresholdhave 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
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.
uses
digraph_general_robust_two_cycle_free_cut_aux_arith,digraph_general_robust_two_cycle_free_cut_aux_layer_cake,le_transexact 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).
- The arithmetic deduction in digraph_general_robust_two_cycle_free_cut_aux_arith that ∑ E(k) ≥ -1 implies ∑ n(k+1) ≥ choose(d, 2) - 1 relies on integer casting and nonlinear arithmetic automation (nlinarith, omega), formalising calculations that on paper would be carried out over the integers or rationals.
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.
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'