AFTD Auto-Formalizing Theoretical Domains

digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four

theoremverified

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

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.

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

    lines 28–30

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

    lines 31–48

    uses digraph_packing_free_cut_peeling_bound

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

    lines 49–51

    uses digraph_seven_out_robust_two_cycle_free_cut_ge_twenty

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

    lines 52–58

    uses digraph_packing_free_cut_peeling_bound

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

    lines 59–66

    uses digraph_three_large_parts_no_four_cycles_cross_ge_forty_five_no_three_one

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

    lines 67–80

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

    lines 103–125

    uses Finset.sum_fiberwise, Finset.sum_congr, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_compl, Fin.sum_univ_three

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

    lines 126–128

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

    lines 129–143

    uses in833_cut_sum_of_two

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

    lines 144–153

    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.

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