digraph_twenty_cut_degree_profile_under_two_cycle_sequences
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
- 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…
- 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…
- digraph_cut_twenty_superlevel_equality_patternsThe five robust two-cycle superlevel alternatives have exactly four equality patterns when their six counts sum to twenty.
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.
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).
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
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).
uses
le_of_eq,digraph_seven_out_robust_cut_thresholdshave 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
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.
uses
Finset.card_union_of_disjoint,Finset.filter_union,Finset.union_compl,Finset.disjoint_left,Finset.mem_filter,Finset.mem_compl.mphave 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
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.
uses
Finset.filter_congrhave 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]
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.
uses
Finset.card_le_card,Finset.mem_filter,le_transhave 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)⟩
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.
uses
Finset.sum_filter,Finset.mem_filter,Finset.mem_range,Finset.card_eq_sum_ones,Finset.card_rangehave 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]
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.
uses
Finset.sum_congr,Finset.card_filter,Finset.sum_commhave 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
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.
uses
Finset.sum_range_succ,Finset.sum_range_zero,Nat.reduceAddhave 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
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).
uses
digraph_cut_twenty_superlevel_equality_patternshave 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.2If 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.
uses
Nat.not_le,Finset.mem_filter.2,Finset.card_pos.2have 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
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.
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
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.
· 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
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.
· 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
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.
· 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.
- The inequality 20 ≤ n 1 + n 2 + n 3 + n 4 + n 5 + n 6 in lines 99–103 is verified by splitting into 32 cases corresponding to the five threshold disjunctions and invoking the omega decision procedure on each branch.
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.
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⟩