AFTD Auto-Formalizing Theoretical Domains

digraph_twenty_cut_degree_profile_under_two_cycle_sequences

theoremverified

For a seven-outregular two-cycle-free part with a twenty-arc outgoing cut, the displayed robust and two-cycle degree-sequence criteria force outside-degree multiset 6,5,4,3,2 and zeros.

Statement

theorem digraph_twenty_cut_degree_profile_under_two_cycle_sequences
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (B : Finset α) (hB : 7 ≤ B.card)
    (hdeg : ∀ v ∈ B, (Finset.univ.filter fun w => D.Adj v w).card = 7)
    (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)))
    (hseq1 : (∀ v ∈ B, 2 ≤ (B.filter fun w => D.Adj v w).card) →
      (B.filter fun v => (B.filter fun w => D.Adj v w).card < 4).card ≤ 3 →
      ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j)))
    (hseq2 : (∀ v ∈ B, 1 ≤ (B.filter fun w => D.Adj v w).card) →
      (B.filter fun v => (B.filter fun w => D.Adj v w).card < 3).card ≤ 1 →
      (B.filter fun v => (B.filter fun w => D.Adj v w).card < 4).card ≤ 4 →
      ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j)))
    (hseq3 : (∀ v ∈ B, 1 ≤ (B.filter fun w => D.Adj v w).card) →
      (B.filter fun v => (B.filter fun w => D.Adj v w).card < 4).card ≤ 2 →
      (B.filter fun v => (B.filter fun w => D.Adj v w).card < 5).card ≤ 6 →
      ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ 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)))
    (hcut : (∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card) = 20) :
    let N := fun k : ℕ => (B.filter fun v => k ≤ (Bᶜ.filter fun w => D.Adj v w).card).card
    N 1 = 5 ∧ N 2 = 5 ∧ N 3 = 4 ∧ N 4 = 3 ∧ N 5 = 2 ∧ N 6 = 1
Source
Degree-sequence criterion in https://arxiv.org/abs/2205.10826, Definition 1.3 and Theorem 1.4; experiments 26240, 26253 and 26254.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof determines the degree sequence of the 20-arc cut by analyzing the cumulative profile n(k) = |{v ∈ B : d(v) ≥ k}| of external degrees from a 7-outregular set B containing no two disjoint directed cycles. Applying a robust cut threshold theorem yields five disjunctive lower bounds on n(k), while summing n(k) across all levels expresses the total cut size 20 and forces n(7) = 0 and ∑_{k=1}^6 n(k) = 20. An equality pattern classification lemma restricts (n(1), ..., n(6)) to four possible integer profiles. Finally, three of these candidate profiles are ruled out because their internal degree counts satisfy one of three cycle-forcing degree-sequence criteria (hseq1, hseq2, hseq3), leaving (5, 5, 4, 3, 2, 1) as the unique profile.

  1. Define the external out-degree d(v) and cumulative superlevel counts n(k), and rephrase the goal in terms of n.

    We enable classical reasoning and introduce local definitions: d(v) is the number of out-neighbors of v outside B, and n(k) counts the vertices in B with external degree d(v) ≥ k. The goal is rephrased as asserting that the sequence (n(1), ..., n(6)) equals (5, 5, 4, 3, 2, 1).

    lines 30–33

      classical
      set d : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card with hd
      set n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ d v).card with hn
      change n 1 = 5 ∧ n 2 = 5 ∧ n 3 = 4 ∧ n 4 = 3 ∧ n 5 = 2 ∧ n 6 = 1
  2. The cumulative counts satisfy five threshold disjunctions derived from the robust cut theorem.

    Since each vertex in B has out-degree 7, its out-degree is in particular at least 7. Applying digraph_seven_out_robust_cut_thresholds under the assumptions |B| ≥ 7, robust cycle existence, and the absence of two disjoint cycles in B yields five threshold disjunctions bounding the values of n(k).

    lines 34–38

    uses le_of_eq, digraph_seven_out_robust_cut_thresholds

      have hdeg7 : ∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card :=
        fun v hv => le_of_eq (hdeg v hv).symm
      have hth := digraph_seven_out_robust_cut_thresholds α D B hB hdeg7 hrobust hno
      have hth' : (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) := hth
  3. For each vertex v in B, its internal out-degree within B plus its external out-degree d(v) equals 7.

    The total out-neighborhood of v is partitioned into the out-neighbors inside B and those in the complement Bᶜ. Since B and Bᶜ are disjoint and cover the vertex type, the sum of the cardinalities of these two neighborhoods equals the total out-degree of v, which is 7 by the out-regularity hypothesis.

    lines 39–52

    uses Finset.card_union_of_disjoint, Finset.filter_union, Finset.union_compl, Finset.disjoint_left, Finset.mem_filter, Finset.mem_compl.mp

      have hab : ∀ v ∈ B, (B.filter fun w => D.Adj v w).card + d v = 7 := by
        intro v hv
        show (B.filter fun w => D.Adj v w).card + (Bᶜ.filter fun w => D.Adj v w).card = 7
        have hunion : (B.filter fun w => D.Adj v w).card + (Bᶜ.filter fun w => D.Adj v w).card
            = (Finset.univ.filter fun w => D.Adj v w).card := by
          rw [← Finset.card_union_of_disjoint]
          · congr 1
            rw [← Finset.filter_union, Finset.union_compl]
          · rw [Finset.disjoint_left]
            intro a ha ha'
            simp only [Finset.mem_filter] at ha ha'
            exact (Finset.mem_compl.mp ha'.1) ha.1
        have h7 := hdeg v hv
        omega
  4. For 1 ≤ k ≤ 7, the number of vertices in B with internal out-degree strictly less than k equals n(8 - k).

    By degree conservation, a vertex in B has internal degree strictly less than k if and only if its external degree satisfies d(v) ≥ 8 - k. By Finset.filter_congr, the two corresponding subsets of B coincide, and the cardinality of the latter is n(8 - k) by definition.

    lines 53–62

    uses Finset.filter_congr

      have hAlt : ∀ (k : ℕ), 1 ≤ k → k ≤ 7 →
          (B.filter fun v => (B.filter fun w => D.Adj v w).card < k).card = n (8 - k) := by
        intro k hk1 hk7
        have hfe : (B.filter fun v => (B.filter fun w => D.Adj v w).card < k)
            = (B.filter fun v => 8 - k ≤ d v) := by
          apply Finset.filter_congr
          intro v hv
          have h := hab v hv
          constructor <;> intro hh <;> omega
        rw [hfe]
  5. The sequence n(k) is non-increasing: n(6) ≤ n(5) ≤ n(4) ≤ n(3) ≤ n(2) ≤ n(1).

    If a ≤ b, then b ≤ d(v) implies a ≤ d(v) by transitivity of ≤, so the set of vertices with external degree at least b is a subset of those with external degree at least a. By Finset.card_le_card, n(b) ≤ n(a). Evaluating this for consecutive indices gives the full chain of inequalities.

    lines 63–72

    uses Finset.card_le_card, Finset.mem_filter, le_trans

      have hmono : n 6 ≤ n 5 ∧ n 5 ≤ n 4 ∧ n 4 ≤ n 3 ∧ n 3 ≤ n 2 ∧ n 2 ≤ n 1 := by
        have key : ∀ a b : ℕ, a ≤ b → n b ≤ n a := by
          intro a b hab'
          show (B.filter fun v => b ≤ d v).card ≤ (B.filter fun v => a ≤ d v).card
          apply Finset.card_le_card
          intro v hv
          simp only [Finset.mem_filter] at hv ⊢
          exact ⟨hv.1, le_trans hab' hv.2⟩
        exact ⟨key 5 6 (by norm_num), key 4 5 (by norm_num), key 3 4 (by norm_num),
          key 2 3 (by norm_num), key 1 2 (by norm_num)⟩
  6. For any natural number m ≤ 7, the indicator sum over k from 0 to 6 of [k + 1 ≤ m] equals m.

    Rewriting the sum as a sum of 1 over the filtered range using Finset.sum_filter, the condition k + 1 ≤ m restricts {0, ..., 6} to range m. The sum of 1 over range m equals its cardinality, which is m.

    lines 73–80

    uses Finset.sum_filter, Finset.mem_filter, Finset.mem_range, Finset.card_eq_sum_ones, Finset.card_range

      have hkey : ∀ m : ℕ, m ≤ 7 → (∑ k ∈ Finset.range 7, (if k + 1 ≤ m then (1:ℕ) else 0)) = m := by
        intro m hm
        rw [← Finset.sum_filter]
        have hf : (Finset.range 7).filter (fun k => k + 1 ≤ m) = Finset.range m := by
          ext k
          simp only [Finset.mem_filter, Finset.mem_range]
          omega
        rw [hf, ← Finset.card_eq_sum_ones, Finset.card_range]
  7. The sum of the cumulative counts n(1) through n(7) equals the cut size 20.

    Expressing each n(k + 1) as the sum over v in B of the indicator that k + 1 ≤ d(v), we interchange the order of summation using Finset.sum_comm. The inner sum over k evaluates to d(v) by the indicator identity hkey, and summing d(v) over all v in B yields the outgoing cut size 20.

    lines 81–94

    uses Finset.sum_congr, Finset.card_filter, Finset.sum_comm

      have hIcc : ∑ k ∈ Finset.range 7, n (k + 1) = 20 := by
        calc ∑ k ∈ Finset.range 7, n (k + 1)
            = ∑ k ∈ Finset.range 7, ∑ v ∈ B, (if k + 1 ≤ d v then (1:ℕ) else 0) := by
              apply Finset.sum_congr rfl
              intro k hk
              show n (k+1) = ∑ v ∈ B, (if k + 1 ≤ d v then (1:ℕ) else 0)
              rw [show n (k+1) = (B.filter fun v => k + 1 ≤ d v).card from by simp only [hn]]
              exact Finset.card_filter (fun v => k + 1 ≤ d v) B
          _ = ∑ v ∈ B, ∑ k ∈ Finset.range 7, (if k + 1 ≤ d v then (1:ℕ) else 0) := Finset.sum_comm
          _ = ∑ v ∈ B, d v := by
              apply Finset.sum_congr rfl
              intro v hv
              exact hkey (d v) (by have h := hab v hv; omega)
          _ = 20 := by simpa only [hd] using hcut
  8. n(7) = 0 and n(1) + n(2) + n(3) + n(4) + n(5) + n(6) = 20.

    Unfolding the range-7 sum gives n(1) + ... + n(7) = 20. Meanwhile, case analysis across the 32 combinations of the five threshold disjunctions, together with monotonicity, shows that n(1) + ... + n(6) ≥ 20. Since all values are non-negative, n(7) must vanish and the sum of the first six terms must be exactly 20.

    lines 95–105

    uses Finset.sum_range_succ, Finset.sum_range_zero, Nat.reduceAdd

      have hsum7 : n 1 + n 2 + n 3 + n 4 + n 5 + n 6 + n 7 = 20 := by
        have h := hIcc
        simp only [Finset.sum_range_succ, Finset.sum_range_zero, Nat.reduceAdd] at h
        omega
      have harith : 20 ≤ n 1 + n 2 + n 3 + n 4 + n 5 + n 6 := by
        obtain ⟨m65, m54, m43, m32, m21⟩ := hmono
        obtain ⟨a1, a2, a3, a4, a5⟩ := hth'
        rcases a1 with h | h <;> rcases a2 with h' | h' <;> rcases a3 with h'' | h'' <;>
          rcases a4 with h''' | h''' <;> rcases a5 with h'''' | h'''' <;> omega
      have hn7 : n 7 = 0 := by omega
      have hnsum : n 1 + n 2 + n 3 + n 4 + n 5 + n 6 = 20 := by omega
  9. The sequence (n(1), ..., n(6)) must match one of four candidate patterns.

    We apply digraph_cut_twenty_superlevel_equality_patterns, which classifies all non-increasing 6-tuples summing to 20 that satisfy the five threshold disjunctions into four specific candidate profiles: (5,5,4,3,3,0), (5,5,4,4,1,1), (5,5,5,2,2,1), and (5,5,4,3,2,1).

    lines 106–107

    uses digraph_cut_twenty_superlevel_equality_patterns

      have hpat := digraph_cut_twenty_superlevel_equality_patterns (n 1) (n 2) (n 3) (n 4) (n 5) (n 6)
        hmono hnsum hth'.1 hth'.2.1 hth'.2.2.1 hth'.2.2.2.1 hth'.2.2.2.2
  10. If n(c) = 0 with c = 8 - k, every vertex in B has internal out-degree at least k.

    If some vertex v in B had internal out-degree strictly less than k, it would belong to the set of vertices with internal degree < k, making that set non-empty and of strictly positive size. But by the duality lemma hAlt, this size is n(8 - k) = n(c) = 0, giving a contradiction.

    lines 108–118

    uses Nat.not_le, Finset.mem_filter.2, Finset.card_pos.2

      have hge : ∀ (k c : ℕ), 1 ≤ k → k ≤ 7 → 8 - k = c → n c = 0 →
          ∀ v ∈ B, k ≤ (B.filter fun w => D.Adj v w).card := by
        intro k c hk1 hk7 hkc hnc v hv
        by_contra h
        rw [Nat.not_le] at h
        have hmem : v ∈ B.filter (fun v => (B.filter fun w => D.Adj v w).card < k) :=
          Finset.mem_filter.2 ⟨hv, h⟩
        have hcard : 0 < (B.filter (fun v => (B.filter fun w => D.Adj v w).card < k)).card :=
          Finset.card_pos.2 ⟨v, hmem⟩
        rw [hAlt k hk1 hk7, hkc] at hcard
        omega
  11. The profile (5, 5, 4, 3, 3, 0) is impossible.

    In this case n(6) = 0, so every vertex in B has internal out-degree at least 2. Moreover, the number of vertices with internal out-degree < 4 is n(4) = 3 ≤ 3. These conditions satisfy the hypotheses of hseq1, producing two disjoint directed cycles in B and contradicting hno.

    lines 119–127

      rcases hpat with hp | hp | hp | hp
      · obtain ⟨e1, e2, e3, e4, e5, e6⟩ := hp
        exfalso
        apply hno
        apply hseq1
        · exact hge 2 6 (by norm_num) (by norm_num) (by norm_num) e6
        · have eq4 : n (8 - 4) = n 4 := by norm_num
          have k4 := hAlt 4 (by norm_num) (by norm_num)
          omega
  12. The profile (5, 5, 4, 4, 1, 1) is impossible.

    Because n(7) = 0, every vertex in B has internal out-degree at least 1. The number of vertices with internal out-degree < 3 is n(5) = 1 ≤ 1, and the count < 4 is n(4) = 4 ≤ 4. These satisfy the hypotheses of hseq2, producing two disjoint directed cycles and contradicting hno.

    lines 128–138

      · obtain ⟨e1, e2, e3, e4, e5, e6⟩ := hp
        exfalso
        apply hno
        apply hseq2
        · exact hge 1 7 (by norm_num) (by norm_num) (by norm_num) hn7
        · have eq3 : n (8 - 3) = n 5 := by norm_num
          have k3 := hAlt 3 (by norm_num) (by norm_num)
          omega
        · have eq4 : n (8 - 4) = n 4 := by norm_num
          have k4 := hAlt 4 (by norm_num) (by norm_num)
          omega
  13. The profile (5, 5, 5, 2, 2, 1) is impossible.

    Again n(7) = 0 ensures all internal out-degrees are at least 1. The number of vertices with internal out-degree < 4 is n(4) = 2 ≤ 2, and the count < 5 is n(3) = 5 ≤ 6. These satisfy the hypotheses of hseq3, producing two disjoint directed cycles and contradicting hno.

    lines 139–149

      · obtain ⟨e1, e2, e3, e4, e5, e6⟩ := hp
        exfalso
        apply hno
        apply hseq3
        · exact hge 1 7 (by norm_num) (by norm_num) (by norm_num) hn7
        · have eq4 : n (8 - 4) = n 4 := by norm_num
          have k4 := hAlt 4 (by norm_num) (by norm_num)
          omega
        · have eq5 : n (8 - 5) = n 3 := by norm_num
          have k5 := hAlt 5 (by norm_num) (by norm_num)
          omega
  14. The unique surviving profile is n(1) = 5, n(2) = 5, n(3) = 4, n(4) = 3, n(5) = 2, and n(6) = 1.

    With the other three candidate patterns ruled out, the fourth candidate must hold, establishing the exact profile asserted by the theorem.

    lines 150–151

      · obtain ⟨e1, e2, e3, e4, e5, e6⟩ := hp
        exact ⟨e1, e2, e3, e4, e5, e6⟩
le_of_eq
If a = b, then a ≤ b.
digraph_seven_out_robust_cut_thresholds
For a 7-outregular vertex subset B of cardinality at least 7 in a digraph with no two disjoint directed cycles, its external degree superlevel counts satisfy five lower-bound disjunctions.
Finset.card_union_of_disjoint
If two finite sets are disjoint, the cardinality of their union is the sum of their cardinalities.
Finset.filter_union
Filtering a predicate over the union of two finite sets equals the union of the filtered sets.
Finset.union_compl
The union of a finite set with its complement is the universal set.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_compl.mp
If an element belongs to the complement of a set, it does not belong to the set.
Finset.filter_congr
If two predicates agree on every element of a finite set, filtering by either yields the same subset.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the cardinality of the other.
le_trans
The relation ≤ is transitive: a ≤ b and b ≤ c imply a ≤ c.
Finset.sum_filter
The sum of a function over a filtered finite set equals the sum over the entire set with terms not satisfying the condition replaced by zero.
Finset.mem_range
A natural number m belongs to range n if and only if m < n.
Finset.card_eq_sum_ones
The cardinality of a finite set equals the sum of 1 over its elements.
Finset.card_range
The cardinality of range n is n.
Finset.sum_congr
Two finite sums are equal if their index sets are identical and their summands agree on all elements.
Finset.card_filter
The cardinality of a filtered subset equals the sum over the base set of the indicator of the predicate.
Finset.sum_comm
Double summation over two finite sets can be interchanged.
Finset.sum_range_succ
The sum of a function over range (n + 1) equals the sum over range n plus the value at n.
Finset.sum_range_zero
The sum of a function over range 0 is zero.
Nat.reduceAdd
Simplification procedure that computes concrete additions of natural numbers.
digraph_cut_twenty_superlevel_equality_patterns
Any non-increasing 6-tuple of natural numbers that sums to 20 and satisfies the five robust cut threshold inequalities must be one of four specific candidate profiles.
Nat.not_le
For natural numbers a and b, the negation ¬(a ≤ b) is equivalent to b < a.
Finset.mem_filter.2
If an element belongs to a set and satisfies a predicate, it belongs to the filtered subset.
Finset.card_pos.2
If a finite set has an element, its cardinality is strictly positive.

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

theorem digraph_twenty_cut_degree_profile_under_two_cycle_sequences    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (B : Finset α) (hB : 7 ≤ B.card)    (hdeg : ∀ v ∈ B, (Finset.univ.filter fun w => D.Adj v w).card = 7)    (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)))    (hseq1 : (∀ v ∈ B, 2 ≤ (B.filter fun w => D.Adj v w).card) →      (B.filter fun v => (B.filter fun w => D.Adj v w).card < 4).card ≤ 3 →      ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)))    (hseq2 : (∀ v ∈ B, 1 ≤ (B.filter fun w => D.Adj v w).card) →      (B.filter fun v => (B.filter fun w => D.Adj v w).card < 3).card ≤ 1 →      (B.filter fun v => (B.filter fun w => D.Adj v w).card < 4).card ≤ 4 →      ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)))    (hseq3 : (∀ v ∈ B, 1 ≤ (B.filter fun w => D.Adj v w).card) →      (B.filter fun v => (B.filter fun w => D.Adj v w).card < 4).card ≤ 2 →      (B.filter fun v => (B.filter fun w => D.Adj v w).card < 5).card ≤ 6 →      ∃ c : Fin 2 → Finset α, (∀ i, c i ⊆ B ∧ 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)))    (hcut : (∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card) = 20) :    let N := fun k : ℕ => (B.filter fun v => k ≤ (Bᶜ.filter fun w => D.Adj v w).card).card    N 1 = 5 ∧ N 2 = 5 ∧ N 3 = 4 ∧ N 4 = 3 ∧ N 5 = 2 ∧ N 6 = 1 := by  classical  set d : α → ℕ := fun v => (Bᶜ.filter fun w => D.Adj v w).card with hd  set n : ℕ → ℕ := fun k => (B.filter fun v => k ≤ d v).card with hn  change n 1 = 5 ∧ n 2 = 5 ∧ n 3 = 4 ∧ n 4 = 3 ∧ n 5 = 2 ∧ n 6 = 1  have hdeg7 : ∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card :=    fun v hv => le_of_eq (hdeg v hv).symm  have hth := digraph_seven_out_robust_cut_thresholds α D B hB hdeg7 hrobust hno  have hth' : (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) := hth  have hab : ∀ v ∈ B, (B.filter fun w => D.Adj v w).card + d v = 7 := by    intro v hv    show (B.filter fun w => D.Adj v w).card + (Bᶜ.filter fun w => D.Adj v w).card = 7    have hunion : (B.filter fun w => D.Adj v w).card + (Bᶜ.filter fun w => D.Adj v w).card        = (Finset.univ.filter fun w => D.Adj v w).card := by      rw [← Finset.card_union_of_disjoint]      · congr 1        rw [← Finset.filter_union, Finset.union_compl]      · rw [Finset.disjoint_left]        intro a ha ha'        simp only [Finset.mem_filter] at ha ha'        exact (Finset.mem_compl.mp ha'.1) ha.1    have h7 := hdeg v hv    omega  have hAlt : ∀ (k : ℕ), 1 ≤ k → k ≤ 7 →      (B.filter fun v => (B.filter fun w => D.Adj v w).card < k).card = n (8 - k) := by    intro k hk1 hk7    have hfe : (B.filter fun v => (B.filter fun w => D.Adj v w).card < k)        = (B.filter fun v => 8 - k ≤ d v) := by      apply Finset.filter_congr      intro v hv      have h := hab v hv      constructor <;> intro hh <;> omega    rw [hfe]  have hmono : n 6 ≤ n 5 ∧ n 5 ≤ n 4 ∧ n 4 ≤ n 3 ∧ n 3 ≤ n 2 ∧ n 2 ≤ n 1 := by    have key : ∀ a b : ℕ, a ≤ b → n b ≤ n a := by      intro a b hab'      show (B.filter fun v => b ≤ d v).card ≤ (B.filter fun v => a ≤ d v).card      apply Finset.card_le_card      intro v hv      simp only [Finset.mem_filter] at hv ⊢      exact ⟨hv.1, le_trans hab' hv.2⟩    exact ⟨key 5 6 (by norm_num), key 4 5 (by norm_num), key 3 4 (by norm_num),      key 2 3 (by norm_num), key 1 2 (by norm_num)⟩  have hkey : ∀ m : ℕ, m ≤ 7 → (∑ k ∈ Finset.range 7, (if k + 1 ≤ m then (1:ℕ) else 0)) = m := by    intro m hm    rw [← Finset.sum_filter]    have hf : (Finset.range 7).filter (fun k => k + 1 ≤ m) = Finset.range m := by      ext k      simp only [Finset.mem_filter, Finset.mem_range]      omega    rw [hf, ← Finset.card_eq_sum_ones, Finset.card_range]  have hIcc : ∑ k ∈ Finset.range 7, n (k + 1) = 20 := by    calc ∑ k ∈ Finset.range 7, n (k + 1)        = ∑ k ∈ Finset.range 7, ∑ v ∈ B, (if k + 1 ≤ d v then (1:ℕ) else 0) := by          apply Finset.sum_congr rfl          intro k hk          show n (k+1) = ∑ v ∈ B, (if k + 1 ≤ d v then (1:ℕ) else 0)          rw [show n (k+1) = (B.filter fun v => k + 1 ≤ d v).card from by simp only [hn]]          exact Finset.card_filter (fun v => k + 1 ≤ d v) B      _ = ∑ v ∈ B, ∑ k ∈ Finset.range 7, (if k + 1 ≤ d v then (1:ℕ) else 0) := Finset.sum_comm      _ = ∑ v ∈ B, d v := by          apply Finset.sum_congr rfl          intro v hv          exact hkey (d v) (by have h := hab v hv; omega)      _ = 20 := by simpa only [hd] using hcut  have hsum7 : n 1 + n 2 + n 3 + n 4 + n 5 + n 6 + n 7 = 20 := by    have h := hIcc    simp only [Finset.sum_range_succ, Finset.sum_range_zero, Nat.reduceAdd] at h    omega  have harith : 20 ≤ n 1 + n 2 + n 3 + n 4 + n 5 + n 6 := by    obtain ⟨m65, m54, m43, m32, m21⟩ := hmono    obtain ⟨a1, a2, a3, a4, a5⟩ := hth'    rcases a1 with h | h <;> rcases a2 with h' | h' <;> rcases a3 with h'' | h'' <;>      rcases a4 with h''' | h''' <;> rcases a5 with h'''' | h'''' <;> omega  have hn7 : n 7 = 0 := by omega  have hnsum : n 1 + n 2 + n 3 + n 4 + n 5 + n 6 = 20 := by omega  have hpat := digraph_cut_twenty_superlevel_equality_patterns (n 1) (n 2) (n 3) (n 4) (n 5) (n 6)    hmono hnsum hth'.1 hth'.2.1 hth'.2.2.1 hth'.2.2.2.1 hth'.2.2.2.2  have hge : ∀ (k c : ℕ), 1 ≤ k → k ≤ 7 → 8 - k = c → n c = 0 →      ∀ v ∈ B, k ≤ (B.filter fun w => D.Adj v w).card := by    intro k c hk1 hk7 hkc hnc v hv    by_contra h    rw [Nat.not_le] at h    have hmem : v ∈ B.filter (fun v => (B.filter fun w => D.Adj v w).card < k) :=      Finset.mem_filter.2 ⟨hv, h⟩    have hcard : 0 < (B.filter (fun v => (B.filter fun w => D.Adj v w).card < k)).card :=      Finset.card_pos.2 ⟨v, hmem⟩    rw [hAlt k hk1 hk7, hkc] at hcard    omega  rcases hpat with hp | hp | hp | hp  · obtain ⟨e1, e2, e3, e4, e5, e6⟩ := hp    exfalso    apply hno    apply hseq1    · exact hge 2 6 (by norm_num) (by norm_num) (by norm_num) e6    · have eq4 : n (8 - 4) = n 4 := by norm_num      have k4 := hAlt 4 (by norm_num) (by norm_num)      omega  · obtain ⟨e1, e2, e3, e4, e5, e6⟩ := hp    exfalso    apply hno    apply hseq2    · exact hge 1 7 (by norm_num) (by norm_num) (by norm_num) hn7    · have eq3 : n (8 - 3) = n 5 := by norm_num      have k3 := hAlt 3 (by norm_num) (by norm_num)      omega    · have eq4 : n (8 - 4) = n 4 := by norm_num      have k4 := hAlt 4 (by norm_num) (by norm_num)      omega  · obtain ⟨e1, e2, e3, e4, e5, e6⟩ := hp    exfalso    apply hno    apply hseq3    · exact hge 1 7 (by norm_num) (by norm_num) (by norm_num) hn7    · have eq4 : n (8 - 4) = n 4 := by norm_num      have k4 := hAlt 4 (by norm_num) (by norm_num)      omega    · have eq5 : n (8 - 5) = n 3 := by norm_num      have k5 := hAlt 5 (by norm_num) (by norm_num)      omega  · obtain ⟨e1, e2, e3, e4, e5, e6⟩ := hp    exact ⟨e1, e2, e3, e4, e5, e6⟩
See it in the graphDiscuss this resultChallenge it