digraph_seven_out_robust_two_cycle_free_cut_ge_twenty
A set of at least seven vertices in a digraph of minimum outdegree seven, containing no two disjoint directed cycles, has at least twenty arcs leaving it if the stated robust two-cycle criterion is available on its subsets.
Statement
theorem digraph_seven_out_robust_two_cycle_free_cut_ge_twenty (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (B : Finset α) (hB : 7 ≤ B.card) (hdeg : ∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hrobust : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) → (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 → ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hno : ¬ ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) : 20 ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card
- Source
- Robust peeling step for the minimum-counterexample campaign route to OP-110; experiment 12598 exhausts the degree arithmetic.
- 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…
- sorted_seven_robust_peeling_capacitySeven decreasing nonnegative counts satisfying the five displayed robust-peeling alternatives have sum at least twenty.
- digraph_seven_out_robust_cut_thresholdsUnder the displayed robust two-cycle criterion, if a set of at least seven vertices in a digraph of minimum outdegree seven contains no…
- Used by 1
- digraph_three_large_parts_no_four_cycles_cross_ge_fifty_fourIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles and its vertices are partitioned into three parts each…
The proof, explained
The proof lower-bounds the cut size ∑_{v ∈ B} d(v) by expressing it via the discrete layer-cake principle as at least the sum of the first six superlevel counts, ∑_{k=1}^6 n(k), where n(k) is the number of vertices in B with at least k outgoing arcs leaving B. The structural threshold lemma `digraph_seven_out_robust_cut_thresholds` provides five disjunctive lower bounds on these level counts under the robust cycle-free hypothesis. Since the level counts are monotonically non-increasing, a Presburger arithmetic case analysis (`in833_superlevel_count_arithmetic`) shows that ∑_{k=1}^6 n(k) ≥ 20, which directly bounds the cut size from below by 20.
If n₁ ≥ n₂ ≥ n₃ ≥ n₄ ≥ n₅ ≥ n₆ and the five disjunctions (1 ≤ n₆ ∨ 3 ≤ n₅, 2 ≤ n₅ ∨ 4 ≤ n₄, 3 ≤ n₄ ∨ 5 ≤ n₃, 4 ≤ n₃ ∨ 6 ≤ n₂, 5 ≤ n₂ ∨ 7 ≤ n₁) hold, then n₁ + n₂ + n₃ + n₄ + n₅ + n₆ ≥ 20. automation
We perform a complete case split across the five disjunctive hypotheses, yielding 2⁵ = 32 cases. In every branch, the monotonicity relations and lower bounds on the variables force the sum n₁ + n₂ + n₃ + n₄ + n₅ + n₆ to be at least 20, which is verified automatically by Presburger linear arithmetic (`omega`).
rcases h0 with h0 | h0 <;> rcases h1 with h1 | h1 <;> rcases h2 with h2 | h2 <;> rcases h3 with h3 | h3 <;> rcases h4 with h4 | h4 <;> omega
The sum over k ∈ {0, ..., 5} of the number of vertices v ∈ B with d(v) ≥ k + 1 equals the sum over v ∈ B of the number of indices k ∈ {0, ..., 5} with k + 1 ≤ d(v).
Each set cardinality is rewritten as a sum of ones using `Finset.card_eq_sum_ones`, and the filter conditions are turned into indicator functions over ambient sets with `Finset.sum_filter`. Exchanging the order of summation using `Finset.sum_comm` rewrites the double sum into a sum over vertices v ∈ B.
uses
Finset.card_eq_sum_ones,Finset.sum_filter,Finset.sum_commclassical have hswap : (∑ k ∈ Finset.range 6, (B.filter fun v => k+1 ≤ d v).card) = ∑ v ∈ B, ((Finset.range 6).filter fun k => k+1 ≤ d v).card := by simp only [Finset.card_eq_sum_ones, Finset.sum_filter] rw [Finset.sum_comm] rw [hswap]
For any function d : B → ℕ, the layer-cake sum ∑_{k=0}^5 |{v ∈ B | k + 1 ≤ d(v)}| is at most ∑_{v ∈ B} d(v).
By `Finset.sum_le_sum`, it suffices to bound each vertex's term individually. For each v ∈ B, the set of indices {k ∈ {0, ..., 5} | k + 1 ≤ d(v)} is a subset of {0, ..., d(v) - 1} because k + 1 ≤ d(v) implies k < d(v) (via `Finset.mem_filter.mp` and `Finset.mem_range.mpr`). By subset monotonicity of cardinality (`Finset.card_le_card`) and the size of a range (`Finset.card_range`), each term is at most d(v).
uses
Finset.sum_le_sum,Finset.mem_filter.mp,Finset.mem_range.mpr,Finset.card_le_card,Finset.card_rangeapply Finset.sum_le_sum intro v hv have hsub : (Finset.range 6).filter (fun k => k+1 ≤ d v) ⊆ Finset.range (d v) := by intro k hk have hk' := (Finset.mem_filter.mp hk).2 exact Finset.mem_range.mpr (by omega) have h := Finset.card_le_card hsub simpa only [Finset.card_range] using h
With d(v) defined as the number of arcs leaving B from v, and n(k) defined as the number of vertices in B with d(v) ≥ k, the function n is monotonically non-increasing (n(j) ≤ n(i) whenever i ≤ j).
For any vertex v ∈ B, if d(v) ≥ j and i ≤ j, then d(v) ≥ i by transitivity of inequality (`le_trans`). Using `Finset.mem_filter.mp` and `Finset.mem_filter.mpr`, this implies that the level set {v ∈ B | j ≤ d(v)} is a subset of {v ∈ B | i ≤ d(v)}. The monotonicity of n then follows by `Finset.card_le_card`.
uses
Finset.card_le_card,Finset.mem_filter.mp,Finset.mem_filter.mpr,le_transclassical let d : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card let n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ d v).card have hnmono : ∀ i j : ℕ, i ≤ j → n j ≤ n i := by intro i j hij apply Finset.card_le_card intro v hv have hh := Finset.mem_filter.mp hv exact Finset.mem_filter.mpr ⟨hh.1, le_trans hij hh.2⟩
The sum of the superlevel counts satisfies n(1) + n(2) + n(3) + n(4) + n(5) + n(6) ≥ 20.
Applying `digraph_seven_out_robust_cut_thresholds` yields five threshold disjunctions on the level counts: 1 ≤ n(6) ∨ 3 ≤ n(5), 2 ≤ n(5) ∨ 4 ≤ n(4), 3 ≤ n(4) ∨ 5 ≤ n(3), 4 ≤ n(3) ∨ 6 ≤ n(2), and 5 ≤ n(2) ∨ 7 ≤ n(1). Combining these conditions with the monotonicity of n (proved via `hnmono`), the arithmetic lemma `in833_superlevel_count_arithmetic` establishes that ∑_{k=1}^6 n(k) ≥ 20.
uses
digraph_seven_out_robust_cut_thresholds,in833_superlevel_count_arithmetichave ht := digraph_seven_out_robust_cut_thresholds α D B hB hdeg hrobust hno change (1 ≤ n 6 ∨ 3 ≤ n 5) ∧ (2 ≤ n 5 ∨ 4 ≤ n 4) ∧ (3 ≤ n 4 ∨ 5 ≤ n 3) ∧ (4 ≤ n 3 ∨ 6 ≤ n 2) ∧ (5 ≤ n 2 ∨ 7 ≤ n 1) at ht rcases ht with ⟨h0,h1,h2,h3,h4⟩ have hn := in833_superlevel_count_arithmetic (n 1) (n 2) (n 3) (n 4) (n 5) (n 6) (hnmono 1 2 (by omega)) (hnmono 2 3 (by omega)) (hnmono 3 4 (by omega)) (hnmono 4 5 (by omega)) (hnmono 5 6 (by omega)) h0 h1 h2 h3 h4
The total number of arcs leaving B is at least 20.
The layer-cake lemma `in833_layer_cake` bounds ∑_{k=0}^5 n(k + 1) by the cut size ∑_{v ∈ B} d(v). Expanding this range sum into n(1) + ... + n(6) with `Finset.sum_range_succ`, `Finset.sum_range_zero`, and `Nat.zero_add`, and combining it with the lower bound n(1) + ... + n(6) ≥ 20, linear arithmetic (`omega`) completes the proof.
uses
in833_layer_cake,Finset.sum_range_succ,Finset.sum_range_zero,Nat.zero_addhave hl : (∑ k ∈ Finset.range 6, n (k+1)) ≤ ∑ v ∈ B, d v := in833_layer_cake B d have hs : (∑ k ∈ Finset.range 6, n (k+1)) = n 1+n 2+n 3+n 4+n 5+n 6 := by simp only [Finset.sum_range_succ, Finset.sum_range_zero, Nat.zero_add] rw [hs] at hl change 20 ≤ ∑ v ∈ B, d v omega
Finset.card_eq_sum_ones- The cardinality of a finite set equals the sum of 1 over all of its elements.
Finset.sum_filter- Summing a function over a filtered subset equals summing an indicator (conditional) term over the ambient finite set.
Finset.sum_comm- The order of summation in a double sum over two finite sets can be exchanged (Fubini's theorem for finite sums).
Finset.sum_le_sum- If f(i) ≤ g(i) for every element i in a finite set, then the sum of f over the set is at most the sum of g over the set.
Finset.mem_filter.mp- If an element belongs to a filtered set, then it belongs to the base set and satisfies the filtering predicate.
Finset.mem_range.mpr- A natural number k belongs to the range {0, ..., n - 1} if and only if k < n.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to the cardinality of the other.
Finset.card_range- The cardinality of the range {0, ..., n - 1} is n.
Finset.mem_filter.mpr- If an element belongs to the base set and satisfies the predicate, it belongs to the filtered set.
le_trans- Transitivity of the ordering: if a ≤ b and b ≤ c, then a ≤ c.
digraph_seven_out_robust_cut_thresholds- For a subset B of at least seven vertices in a digraph of minimum outdegree 7 containing no two disjoint cycles and satisfying the robust criterion, the level set counts n(k) of out-degrees leaving B satisfy five coupled threshold disjunctions.
in833_superlevel_count_arithmetic- If six natural numbers n₁ ≥ n₂ ≥ n₃ ≥ n₄ ≥ n₅ ≥ n₆ satisfy the five threshold disjunctions, their sum n₁ + n₂ + n₃ + n₄ + n₅ + n₆ is at least 20.
in833_layer_cake- Discrete layer-cake principle: the sum of the cardinalities of the first six superlevel sets of a function d on B is bounded by the total sum of d over B.
Finset.sum_range_succ- Splitting off the last term in a sum over a range: the sum over {0, ..., n} equals the sum over {0, ..., n - 1} plus the term at n.
Finset.sum_range_zero- The sum over an empty range of natural numbers is zero.
Nat.zero_add- Zero is the left identity for natural addition: 0 + n = n.
- In `in833_superlevel_count_arithmetic`, the case analysis generates 32 branches that are all closed by Lean's linear arithmetic procedure `omega`.
- The structural threshold disjunctions on the level counts are provided by the external lemma `digraph_seven_out_robust_cut_thresholds`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option maxHeartbeats 3000000private theorem in833_superlevel_count_arithmetic (n1 n2 n3 n4 n5 n6 : ℕ) (h12 : n2 ≤ n1) (h23 : n3 ≤ n2) (h34 : n4 ≤ n3) (h45 : n5 ≤ n4) (h56 : n6 ≤ n5) (h0 : 1 ≤ n6 ∨ 3 ≤ n5) (h1 : 2 ≤ n5 ∨ 4 ≤ n4) (h2 : 3 ≤ n4 ∨ 5 ≤ n3) (h3 : 4 ≤ n3 ∨ 6 ≤ n2) (h4 : 5 ≤ n2 ∨ 7 ≤ n1) : 20 ≤ n1+n2+n3+n4+n5+n6 := by rcases h0 with h0 | h0 <;> rcases h1 with h1 | h1 <;> rcases h2 with h2 | h2 <;> rcases h3 with h3 | h3 <;> rcases h4 with h4 | h4 <;> omegaprivate lemma in833_layer_cake {α : Type} [DecidableEq α] (B : Finset α) (d : α → ℕ) : (∑ k ∈ Finset.range 6, (B.filter fun v => k+1 ≤ d v).card) ≤ ∑ v ∈ B, d v := by classical have hswap : (∑ k ∈ Finset.range 6, (B.filter fun v => k+1 ≤ d v).card) = ∑ v ∈ B, ((Finset.range 6).filter fun k => k+1 ≤ d v).card := by simp only [Finset.card_eq_sum_ones, Finset.sum_filter] rw [Finset.sum_comm] rw [hswap] apply Finset.sum_le_sum intro v hv have hsub : (Finset.range 6).filter (fun k => k+1 ≤ d v) ⊆ Finset.range (d v) := by intro k hk have hk' := (Finset.mem_filter.mp hk).2 exact Finset.mem_range.mpr (by omega) have h := Finset.card_le_card hsub simpa only [Finset.card_range] using htheorem digraph_seven_out_robust_two_cycle_free_cut_ge_twenty (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (B : Finset α) (hB : 7 ≤ B.card) (hdeg : ∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hrobust : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) → (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 → ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hno : ¬ ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) : 20 ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card := by classical let d : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card let n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ d v).card have hnmono : ∀ i j : ℕ, i ≤ j → n j ≤ n i := by intro i j hij apply Finset.card_le_card intro v hv have hh := Finset.mem_filter.mp hv exact Finset.mem_filter.mpr ⟨hh.1, le_trans hij hh.2⟩ have ht := digraph_seven_out_robust_cut_thresholds α D B hB hdeg hrobust hno change (1 ≤ n 6 ∨ 3 ≤ n 5) ∧ (2 ≤ n 5 ∨ 4 ≤ n 4) ∧ (3 ≤ n 4 ∨ 5 ≤ n 3) ∧ (4 ≤ n 3 ∨ 6 ≤ n 2) ∧ (5 ≤ n 2 ∨ 7 ≤ n 1) at ht rcases ht with ⟨h0,h1,h2,h3,h4⟩ have hn := in833_superlevel_count_arithmetic (n 1) (n 2) (n 3) (n 4) (n 5) (n 6) (hnmono 1 2 (by omega)) (hnmono 2 3 (by omega)) (hnmono 3 4 (by omega)) (hnmono 4 5 (by omega)) (hnmono 5 6 (by omega)) h0 h1 h2 h3 h4 have hl : (∑ k ∈ Finset.range 6, n (k+1)) ≤ ∑ v ∈ B, d v := in833_layer_cake B d have hs : (∑ k ∈ Finset.range 6, n (k+1)) = n 1+n 2+n 3+n 4+n 5+n 6 := by simp only [Finset.sum_range_succ, Finset.sum_range_zero, Nat.zero_add] rw [hs] at hl change 20 ≤ ∑ v ∈ B, d v omega