digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four
If a finite digraph of minimum outdegree seven has no four disjoint directed cycles and its vertices are partitioned into three parts each of size at least seven, then at least 54 arcs cross between parts, assuming the displayed one-, robust two- and three-cycle criteria.
Statement
theorem digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (col : α → Fin 3) (hsize : ∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card) (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hone : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) → ∃ C : Finset α, C ⊆ T ∧ digraph_directed_cycle_on D C) (htwo : ∀ 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))) (hthree : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 3 → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hno : ¬ ∃ c : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) : 54 ≤ ∑ v : α, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card
- Source
- Partition cut reduction for OP-110; experiments 12598 and 12606 check the degree and cycle-allocation arithmetic.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_packing_free_cut_peeling_boundIf a set of at least r−m+1 vertices contains no q disjoint directed cycles, while every nonempty induced digraph of minimum outdegree m…
- digraph_seven_out_robust_two_cycle_free_cut_ge_twentyA set of at least seven vertices in a digraph of minimum outdegree seven, containing no two disjoint directed cycles, has at least twenty…
- digraph_three_large_parts_no_four_cycles_cross_ge_forty_fiveIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles and its vertices are partitioned into three parts each…
- Used by 3
- digraph_125_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 125 vertices with dominated arcs and a cycle in every in-neighborhood contains four…
- digraph_three_large_parts_no_four_cycles_cross_ge_fifty_fiveIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles, its vertices are partitioned into three parts of size…
- digraph_125_no_four_cycles_overlap_windowFor a loopless oriented seven-outregular digraph on 125 vertices with dominated arcs, a cycle in each in-neighborhood, and no four…
The proof, explained
The theorem bounds the number of crossing arcs in a 3-partition of a digraph of minimum outdegree 7 with parts of size at least 7 and no four disjoint directed cycles by rewriting the total crossing arcs as the sum of the cuts of the three parts, cut(0) + cut(1) + cut(2). If no part contains two disjoint directed cycles, the robust 2-cycle criterion implies that each part's cut is at least 20, for a total of at least 60. When some part does contain two disjoint cycles, a helper lemma (in833_cut_sum_of_two) leverages the global cycle restriction together with 1- and 3-cycle peeling bounds to show that the three cuts sum to at least 54.
Define each color class B m and its outgoing cut size cut(m), reformulating the goal as 54 ≤ cut(i) + cut(j) + cut(k).
We introduce abbreviations B(m) for the vertices of color m and cut(m) for the number of directed arcs from B(m) to its complement, rewriting the target sum of cuts as cut(i) + cut(j) + cut(k).
let B (m : Fin 3) := Finset.univ.filter fun v => col v = m let cut (m : Fin 3) := ∑ v ∈ B m, ((B m)ᶜ.filter fun w => D.Adj v w).card change 54 ≤ cut i + cut j + cut k
For any part B(m), if B(m) contains no directed cycle, then cut(m) ≥ 28.
We adapt the 1-cycle hypothesis hone to a family of 1 cycle indexed by Fin 1 (which is vacuously pairwise disjoint). Because |B(m)| ≥ 7 and all vertices have outdegree at least 7 in D, the peeling bound digraph_packing_free_cut_peeling_bound with degree 7 and threshold 1 applies to give a cut of at least (7 - 1 + 1)(7 - 1 + 2) / 2 = 28.
uses
digraph_packing_free_cut_peeling_boundhave hcut1 : ∀ m : Fin 3, ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack1 D (B m) → 28 ≤ cut m := by intro m hm1 have hcriterion : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 1 → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j)) := by intro T hT hd obtain ⟨C, hC1, hC2⟩ := hone T hT hd refine ⟨fun _ => C, fun _ => ⟨hC1, hC2⟩, ?_⟩ intro a b hab; fin_cases a; fin_cases b; contradiction have hno_q : ¬ ∃ c : Fin 1 → Finset α, (∀ i, c i ⊆ B m ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j)) := by intro ⟨c, hc, _⟩; exact hm1 ⟨c 0, (hc 0).1, (hc 0).2⟩ have hBm : 7 - 1 + 1 ≤ (B m).card := by dsimp [B]; have := hsize m; omega have hbound := digraph_packing_free_cut_peeling_bound α D 7 1 1 (by omega) (B m) hBm (fun v _ => hdeg v) hcriterion hno_q have hcalc : (7 - 1 + 1) * (7 - 1 + 2) / 2 = 28 := by rfl rwa [hcalc] at hbound
For any part B(m), if B(m) contains no two disjoint directed cycles, then cut(m) ≥ 20.
Since B(m) has size at least 7 and all vertices have outdegree at least 7, the absence of two disjoint directed cycles within B(m) implies cut(m) ≥ 20 directly by digraph_seven_out_robust_two_cycle_free_cut_ge_twenty.
uses
digraph_seven_out_robust_two_cycle_free_cut_ge_twentyhave hcut2 : ∀ m : Fin 3, ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (B m) → 20 ≤ cut m := by intro m hm2 exact digraph_seven_out_robust_two_cycle_free_cut_ge_twenty α D (B m) (hsize m) (fun v _ => hdeg v) htwo hm2
For any part B(m), if B(m) contains no three disjoint directed cycles, then cut(m) ≥ 6.
The peeling bound digraph_packing_free_cut_peeling_bound with degree 7 and threshold 5, using the 3-cycle criterion hthree and |B(m)| ≥ 7 - 5 + 1 = 3, yields a cut lower bound of (7 - 5 + 1)(7 - 5 + 2) / 2 = 6.
uses
digraph_packing_free_cut_peeling_boundhave hcut3 : ∀ m : Fin 3, ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack3 D (B m) → 6 ≤ cut m := by intro m hm3 have hBm : 7 - 5 + 1 ≤ (B m).card := by dsimp [B]; have := hsize m; omega have hbound := digraph_packing_free_cut_peeling_bound α D 7 5 3 (by omega) (B m) hBm (fun v _ => hdeg v) hthree (by exact hm3) have hcalc : (7 - 5 + 1) * (7 - 5 + 2) / 2 = 6 := by rfl rwa [hcalc] at hbound
In in833_cut_sum_of_two, if part B(i) contains three disjoint directed cycles, then the total cut is at least 54.
Since the graph has no four disjoint cycles, neither part B(j) nor part B(k) can contain any directed cycle at all (digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_three_one). Hence cut(j) ≥ 28 and cut(k) ≥ 28 by hcut1, so cut(i) + cut(j) + cut(k) ≥ 0 + 28 + 28 = 56 ≥ 54.
uses
digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_three_oneby_cases h3 : digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack3 D (B i) · have hj1 : ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack1 D (B j) := fun hj => digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_three_one D col hno hij h3 hj have hk1 : ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack1 D (B k) := fun hk => digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_three_one D col hno hik h3 hk have bnd_j := hcut1 j hj1 have bnd_k := hcut1 k hk1 omega
In in833_cut_sum_of_two, if part B(i) contains two disjoint cycles but not three, then the total cut is at least 54.
Because B(i) has no 3-cycle packing, cut(i) ≥ 6. Since B(i) contains two disjoint cycles (hypothesis h2), neither B(j) nor B(k) can contain two disjoint cycles (digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_two), so cut(j) ≥ 20 and cut(k) ≥ 20. If B(j) contains one cycle, then B(k) cannot contain any cycle (digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_one_one), yielding cut(k) ≥ 28 and total cut ≥ 6 + 20 + 28 = 54. Otherwise B(j) has no cycle, yielding cut(j) ≥ 28 and total cut ≥ 6 + 28 + 20 = 54.
uses
digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_two,digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_one_one· have bnd_i := hcut3 i h3 have hj2 : ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (B j) := fun hj => digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_two D col hno hij h2 hj have hk2 : ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (B k) := fun hk => digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_two D col hno hik h2 hk have bnd_j2 := hcut2 j hj2 have bnd_k2 := hcut2 k hk2 by_cases hj1 : digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack1 D (B j) · have hk1 : ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack1 D (B k) := fun hk => digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_one_one D col hno hij hik hjk h2 hj1 hk have bnd_k1 := hcut1 k hk1 omega · have bnd_j1 := hcut1 j hj1 omega
The total number of crossing arcs equals cut(0) + cut(1) + cut(2).
Using Finset.sum_fiberwise, the sum of outgoing crossing edges over all vertices is partitioned by color into the sum of outgoing cut sizes across the three parts. The sum over Fin 3 then expands via Fin.sum_univ_three to cut(0) + cut(1) + cut(2).
uses
Finset.sum_fiberwise,Finset.sum_congr,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_compl,Fin.sum_univ_threehave hcross : ∑ v : α, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card = ∑ i : Fin 3, ∑ v ∈ (Finset.univ.filter fun v => col v = i), ((Finset.univ.filter fun v => col v = i)ᶜ.filter fun w => D.Adj v w).card := by rw [← Finset.sum_fiberwise Finset.univ col] apply Finset.sum_congr rfl intro i hi apply Finset.sum_congr rfl intro v hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv congr 1 ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_compl] constructor · rintro ⟨hne, hadj⟩ refine ⟨?_, hadj⟩ intro hw exact hne (hw.trans hv.symm) · rintro ⟨hw, hadj⟩ refine ⟨?_, hadj⟩ intro heq apply hw exact heq.trans hv rw [hcross, Fin.sum_univ_three]
It suffices to show that cut(0) + cut(1) + cut(2) ≥ 54.
We introduce the notation cut(m) for the outgoing cut of each color class m and change the goal to 54 ≤ cut(0) + cut(1) + cut(2).
let cut (m : Fin 3) := ∑ v ∈ (Finset.univ.filter fun v => col v = m), ((Finset.univ.filter fun v => col v = m)ᶜ.filter fun w => D.Adj v w).card change 54 ≤ cut 0 + cut 1 + cut 2
If some color class contains two disjoint directed cycles, the sum of cuts is at least 54.
Assuming there is a part i with two disjoint directed cycles, we case-split on i ∈ {0, 1, 2}. In each case, lemma in833_cut_sum_of_two applied to the corresponding permutation of indices establishes that cut(0) + cut(1) + cut(2) ≥ 54.
uses
in833_cut_sum_of_twoby_cases h : ∃ i : Fin 3, digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (Finset.univ.filter fun v => col v = i) · obtain ⟨i, hi⟩ := h fin_cases i · have h0 := in833_cut_sum_of_two α D col hsize hdeg hone htwo hthree hno 0 1 2 (by decide) (by decide) (by decide) hi dsimp [cut] exact h0 · have h1 := in833_cut_sum_of_two α D col hsize hdeg hone htwo hthree hno 1 0 2 (by decide) (by decide) (by decide) hi dsimp [cut] at * omega · have h2 := in833_cut_sum_of_two α D col hsize hdeg hone htwo hthree hno 2 0 1 (by decide) (by decide) (by decide) hi dsimp [cut] at * omega
If no color class contains two disjoint directed cycles, the sum of cuts is at least 54.
When no color class contains two disjoint cycles, the robust 2-cycle cut bound digraph_seven_out_robust_two_cycle_free_cut_ge_twenty applies to all three parts, giving cut(0) ≥ 20, cut(1) ≥ 20, and cut(2) ≥ 20. Summing these inequalities yields cut(0) + cut(1) + cut(2) ≥ 60 ≥ 54.
uses
digraph_seven_out_robust_two_cycle_free_cut_ge_twenty· have hnot : ∀ m : Fin 3, ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (Finset.univ.filter fun v => col v = m) := by intro m hm; exact h ⟨m, hm⟩ have hcut2 : ∀ m : Fin 3, 20 ≤ cut m := by intro m exact digraph_seven_out_robust_two_cycle_free_cut_ge_twenty α D (Finset.univ.filter fun v => col v = m) (hsize m) (fun v _ => hdeg v) htwo (hnot m) have c0 := hcut2 0 have c1 := hcut2 1 have c2 := hcut2 2 omega
Fin.sum_univ_three- In the three-element type Fin 3, the sum of a function over all elements is f(0) + f(1) + f(2).
Finset.mem_compl- An element belongs to the complement of a set if and only if it does not belong to the set.
Finset.mem_filter- An element belongs to a filtered finset if and only if it is in the original finset and satisfies the filter predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.sum_congr- Two sums over finsets are equal if their index sets are equal and their summands agree on every element.
Finset.sum_fiberwise- A sum over a finite set can be grouped as a double sum over the fibers of a mapping from that set.
digraph_packing_free_cut_peeling_bound- In a digraph of minimum outdegree r on a set B of size at least r - m + 1, if every nonempty subgraph with minimum outdegree at least m contains q disjoint cycles, but B itself has no q disjoint cycles, then the outgoing cut from B is at least (r - m + 1)(r - m + 2) / 2.
digraph_seven_out_robust_two_cycle_free_cut_ge_twenty- In a digraph with minimum outdegree at least 7, any subset of at least 7 vertices that satisfies the robust 2-cycle criterion and contains no two disjoint directed cycles has an outgoing cut of at least 20.
digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_one_one- In a digraph partitioned into color classes that contains no four disjoint directed cycles, one part cannot contain two disjoint cycles while two other distinct parts each contain one directed cycle.
digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_two- In a digraph partitioned into color classes that contains no four disjoint directed cycles, two distinct parts cannot each contain two disjoint directed cycles.
digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_three_one- In a digraph partitioned into color classes that contains no four disjoint directed cycles, one part cannot contain three disjoint cycles while another distinct part contains one directed cycle.
in833_cut_sum_of_two- In a 3-partition of a digraph of minimum outdegree 7 with parts of size at least 7 and no four disjoint cycles, if one part contains two disjoint directed cycles, the sum of the outgoing cuts of the three parts is at least 54.
true_and- The proposition True ∧ P is logically equivalent to P.
- In step 2, the 1-cycle criterion is formally converted to a family indexed by Fin 1, whose pairwise disjointness holds vacuously because Fin 1 has only one element.
- The proof uses a vertex-peeling lemma (digraph_packing_free_cut_peeling_bound) to derive cut lower bounds of 28 and 6 from the absence of 1- and 3-cycle packings, respectively.
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 3000000set_option maxRecDepth 4096private lemma in833_cut_sum_of_two (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (col : α → Fin 3) (hsize : ∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card) (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hone : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) → ∃ C : Finset α, C ⊆ T ∧ digraph_directed_cycle_on D C) (htwo : ∀ 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))) (hthree : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 3 → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hno : ¬ ∃ c : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (i j k : Fin 3) (hij : i ≠ j) (hik : i ≠ k) (hjk : j ≠ k) (h2 : digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (Finset.univ.filter fun v => col v = i)) : 54 ≤ ∑ v ∈ (Finset.univ.filter fun v => col v = i), ((Finset.univ.filter fun v => col v = i)ᶜ.filter fun w => D.Adj v w).card + ∑ v ∈ (Finset.univ.filter fun v => col v = j), ((Finset.univ.filter fun v => col v = j)ᶜ.filter fun w => D.Adj v w).card + ∑ v ∈ (Finset.univ.filter fun v => col v = k), ((Finset.univ.filter fun v => col v = k)ᶜ.filter fun w => D.Adj v w).card := by let B (m : Fin 3) := Finset.univ.filter fun v => col v = m let cut (m : Fin 3) := ∑ v ∈ B m, ((B m)ᶜ.filter fun w => D.Adj v w).card change 54 ≤ cut i + cut j + cut k have hcut1 : ∀ m : Fin 3, ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack1 D (B m) → 28 ≤ cut m := by intro m hm1 have hcriterion : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 1 → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j)) := by intro T hT hd obtain ⟨C, hC1, hC2⟩ := hone T hT hd refine ⟨fun _ => C, fun _ => ⟨hC1, hC2⟩, ?_⟩ intro a b hab; fin_cases a; fin_cases b; contradiction have hno_q : ¬ ∃ c : Fin 1 → Finset α, (∀ i, c i ⊆ B m ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j)) := by intro ⟨c, hc, _⟩; exact hm1 ⟨c 0, (hc 0).1, (hc 0).2⟩ have hBm : 7 - 1 + 1 ≤ (B m).card := by dsimp [B]; have := hsize m; omega have hbound := digraph_packing_free_cut_peeling_bound α D 7 1 1 (by omega) (B m) hBm (fun v _ => hdeg v) hcriterion hno_q have hcalc : (7 - 1 + 1) * (7 - 1 + 2) / 2 = 28 := by rfl rwa [hcalc] at hbound have hcut2 : ∀ m : Fin 3, ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (B m) → 20 ≤ cut m := by intro m hm2 exact digraph_seven_out_robust_two_cycle_free_cut_ge_twenty α D (B m) (hsize m) (fun v _ => hdeg v) htwo hm2 have hcut3 : ∀ m : Fin 3, ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack3 D (B m) → 6 ≤ cut m := by intro m hm3 have hBm : 7 - 5 + 1 ≤ (B m).card := by dsimp [B]; have := hsize m; omega have hbound := digraph_packing_free_cut_peeling_bound α D 7 5 3 (by omega) (B m) hBm (fun v _ => hdeg v) hthree (by exact hm3) have hcalc : (7 - 5 + 1) * (7 - 5 + 2) / 2 = 6 := by rfl rwa [hcalc] at hbound by_cases h3 : digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack3 D (B i) · have hj1 : ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack1 D (B j) := fun hj => digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_three_one D col hno hij h3 hj have hk1 : ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack1 D (B k) := fun hk => digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_three_one D col hno hik h3 hk have bnd_j := hcut1 j hj1 have bnd_k := hcut1 k hk1 omega · have bnd_i := hcut3 i h3 have hj2 : ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (B j) := fun hj => digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_two D col hno hij h2 hj have hk2 : ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (B k) := fun hk => digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_two D col hno hik h2 hk have bnd_j2 := hcut2 j hj2 have bnd_k2 := hcut2 k hk2 by_cases hj1 : digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack1 D (B j) · have hk1 : ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack1 D (B k) := fun hk => digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_two_one_one D col hno hij hik hjk h2 hj1 hk have bnd_k1 := hcut1 k hk1 omega · have bnd_j1 := hcut1 j hj1 omegatheorem digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (col : α → Fin 3) (hsize : ∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card) (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hone : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) → ∃ C : Finset α, C ⊆ T ∧ digraph_directed_cycle_on D C) (htwo : ∀ 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))) (hthree : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 3 → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hno : ¬ ∃ c : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) : 54 ≤ ∑ v : α, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card := by have hcross : ∑ v : α, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card = ∑ i : Fin 3, ∑ v ∈ (Finset.univ.filter fun v => col v = i), ((Finset.univ.filter fun v => col v = i)ᶜ.filter fun w => D.Adj v w).card := by rw [← Finset.sum_fiberwise Finset.univ col] apply Finset.sum_congr rfl intro i hi apply Finset.sum_congr rfl intro v hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv congr 1 ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_compl] constructor · rintro ⟨hne, hadj⟩ refine ⟨?_, hadj⟩ intro hw exact hne (hw.trans hv.symm) · rintro ⟨hw, hadj⟩ refine ⟨?_, hadj⟩ intro heq apply hw exact heq.trans hv rw [hcross, Fin.sum_univ_three] let cut (m : Fin 3) := ∑ v ∈ (Finset.univ.filter fun v => col v = m), ((Finset.univ.filter fun v => col v = m)ᶜ.filter fun w => D.Adj v w).card change 54 ≤ cut 0 + cut 1 + cut 2 by_cases h : ∃ i : Fin 3, digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (Finset.univ.filter fun v => col v = i) · obtain ⟨i, hi⟩ := h fin_cases i · have h0 := in833_cut_sum_of_two α D col hsize hdeg hone htwo hthree hno 0 1 2 (by decide) (by decide) (by decide) hi dsimp [cut] exact h0 · have h1 := in833_cut_sum_of_two α D col hsize hdeg hone htwo hthree hno 1 0 2 (by decide) (by decide) (by decide) hi dsimp [cut] at * omega · have h2 := in833_cut_sum_of_two α D col hsize hdeg hone htwo hthree hno 2 0 1 (by decide) (by decide) (by decide) hi dsimp [cut] at * omega · have hnot : ∀ m : Fin 3, ¬ digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_has_pack2 D (Finset.univ.filter fun v => col v = m) := by intro m hm; exact h ⟨m, hm⟩ have hcut2 : ∀ m : Fin 3, 20 ≤ cut m := by intro m exact digraph_seven_out_robust_two_cycle_free_cut_ge_twenty α D (Finset.univ.filter fun v => col v = m) (hsize m) (fun v _ => hdeg v) htwo (hnot m) have c0 := hcut2 0 have c1 := hcut2 1 have c2 := hcut2 2 omega