AFTD Auto-Formalizing Theoretical Domains

digraph_seven_out_robust_two_cycle_free_cut_ge_twenty

theoremverified

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
Used by 1

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.

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

    lines 12–14

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

    lines 18–23

    uses Finset.card_eq_sum_ones, Finset.sum_filter, Finset.sum_comm

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

    lines 24–31

    uses Finset.sum_le_sum, Finset.mem_filter.mp, Finset.mem_range.mpr, Finset.card_le_card, Finset.card_range

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

    lines 46–54

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

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

    lines 55–61

    uses digraph_seven_out_robust_cut_thresholds, in833_superlevel_count_arithmetic

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

    lines 62–67

    uses in833_layer_cake, Finset.sum_range_succ, Finset.sum_range_zero, Nat.zero_add

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

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

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