AFTD Auto-Formalizing Theoretical Domains

graph_125_three_cliques_except_vertex_bounds

theoremverified

If a graph on 125 vertices has at most 2583 edges and its vertices other than one distinguished vertex form three cliques, then at least 2501 graph edges avoid that vertex and each clique has at least seven vertices.

Statement

theorem graph_125_three_cliques_except_vertex_bounds
    (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj] (x : Fin 125) (col : Fin 125 → Fin 3)
    (hclique : ∀ u v, u ≠ x → v ≠ x → col u = col v → u ≠ v → G.Adj u v)
    (hedges : G.edgeFinset.card ≤ 2583) :
    G.degree x + 2501 ≤ G.edgeFinset.card ∧
    (∀ i, 7 ≤ (Finset.univ.filter fun v => v ≠ x ∧ col v = i).card)
Source
Clique-edge capacity after deleting one vertex in the OP-110 order-125 reduction.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

To bound the edges avoiding a distinguished vertex x and the sizes of the three cliques partitioning the rest of the graph, we analyze the induced subgraph H = G[{x}ᶜ] on the remaining 124 vertices. Applying the cross-degree clique partition bound with the empty digraph shows that the clique sizes n_0, n_1, n_2 satisfy ∑ n_i(n_i - 1) ≤ 2 |E(H)| with n_0 + n_1 + n_2 = 124. Minimizing the sum of squares subject to this sum constraint yields |E(H)| ≥ 2501, which translates to deg(x) + 2501 ≤ |E(G)|. Furthermore, the upper bound |E(G)| ≤ 2583 forces 2 |E(H)| ≤ 5166, which arithmetically precludes any clique from having fewer than 7 vertices.

  1. For natural numbers a, b, c, x, e with a + b + c = 124 and a(a-1) + b(b-1) + c(c-1) + 2x ≤ 2e, the sum of squares satisfies a^2 + b^2 + c^2 + 2x ≤ 2e + 124. automation

    We first prove the identity n(n-1) + n = n^2 for any natural number n by case analysis. Applying this identity to a, b, and c, and substituting a + b + c = 124, the linear terms cancel to yield a^2 + b^2 + c^2 + 2x ≤ 2e + 124 via nonlinear arithmetic.

    lines 5–12

      have hprod (n : ℕ) : n*(n-1)+n=n*n := by
        cases n with
        | zero => simp
        | succ n => simp; ring
      have ha := hprod a
      have hb := hprod b
      have hc := hprod c
      have he : a*a+b*b+c*c+2*x ≤ 2*e+124 := by nlinarith
  2. Under the same hypotheses, 2501 + x ≤ e. automation

    Casting to integers, we use the fact that squares are non-negative (`sq_nonneg`), namely (a-b)^2 ≥ 0, (a-c)^2 ≥ 0, and (b-c)^2 ≥ 0. Summing these shows that 3(a^2 + b^2 + c^2) ≥ (a+b+c)^2 = 124^2 = 15376, which gives a^2 + b^2 + c^2 ≥ 5126. Combining this with a^2 + b^2 + c^2 + 2x ≤ 2e + 124 implies 2501 + x ≤ e via nonlinear arithmetic.

    lines 13–19

    uses sq_nonneg

      have hs' : (a:ℤ)+b+c=124 := by exact_mod_cast hs
      have he' : (a:ℤ)*a+b*b+c*c+2*x ≤ 2*e+124 := by exact_mod_cast he
      have h1 : (0:ℤ) ≤ ((a:ℤ)-b)^2 := sq_nonneg _
      have h2 : (0:ℤ) ≤ ((a:ℤ)-c)^2 := sq_nonneg _
      have h3 : (0:ℤ) ≤ ((b:ℤ)-c)^2 := sq_nonneg _
      have out : (2501:ℤ)+x ≤ e := by nlinarith
      exact_mod_cast out
  3. If a + b + c = 124 and a(a-1) + b(b-1) + c(c-1) + 2x ≤ 5166, then a^2 + b^2 + c^2 + 2x ≤ 5290. automation

    Using the identity n(n-1) + n = n^2 for a, b, c along with a + b + c = 124, the sum a(a-1) + b(b-1) + c(c-1) equals a^2 + b^2 + c^2 - 124. Adding 124 to both sides of the assumed inequality produces a^2 + b^2 + c^2 + 2x ≤ 5166 + 124 = 5290.

    lines 25–32

      have hprod (n : ℕ) : n * (n - 1) + n = n*n := by
        cases n with
        | zero => simp
        | succ n => simp; ring
      have ha := hprod a
      have hb := hprod b
      have hc := hprod c
      have hsum : a*a + b*b + c*c + 2*x ≤ 5290 := by nlinarith
  4. Under the same hypotheses, x ≤ 82. automation

    Casting to integers and applying the non-negativity of (a-b)^2, (b-c)^2, and (a-c)^2 (`sq_nonneg`), the minimal value of a^2 + b^2 + c^2 subject to a + b + c = 124 is 5126. Since a^2 + b^2 + c^2 + 2x ≤ 5290, nonlinear arithmetic concludes that 2x ≤ 5290 - 5126 = 164, so x ≤ 82.

    lines 33–40

    uses sq_nonneg

      have hx : x ≤ 82 := by
        have h1 : (0:ℤ) ≤ ((a:ℤ) - b)^2 := sq_nonneg _
        have h2 : (0:ℤ) ≤ ((b:ℤ) - c)^2 := sq_nonneg _
        have h3 : (0:ℤ) ≤ ((a:ℤ) - c)^2 := sq_nonneg _
        have hs' : (a:ℤ) + b + c = 124 := by exact_mod_cast hs
        have hh' : (a:ℤ)*a + b*b + c*c + 2*x ≤ 5290 := by exact_mod_cast hsum
        have out : (x:ℤ) ≤ 82 := by nlinarith
        exact_mod_cast out
  5. For any natural numbers p, q, r satisfying p + q + r = 124 and p^2 + q^2 + r^2 ≤ 5290, we must have p ≥ 7. automation

    We argue by contradiction: suppose p ≤ 6. Then q + r = 124 - p ≥ 118. Using (q-r)^2 ≥ 0 (`sq_nonneg`) and (q+r-118)(q+r+118) ≥ 0 (`mul_nonneg`), the sum q^2 + r^2 is minimized when q and r are nearly equal, giving q^2 + r^2 ≥ 1/2 (118^2) = 6962. Since p ≥ 0 (`Nat.zero_le`), this contradicts p^2 + q^2 + r^2 ≤ 5290.

    lines 41–54

    uses sq_nonneg, mul_nonneg, Nat.zero_le

      have hsize (p q r : ℕ) (hs : p+q+r=124)
          (hh : p*p + q*q + r*r ≤ 5290) : 7 ≤ p := by
        by_contra hp
        have hp' : p ≤ 6 := by omega
        have hs' : (p:ℤ) + q + r = 124 := by exact_mod_cast hs
        have hh' : (p:ℤ)*p + q*q + r*r ≤ 5290 := by exact_mod_cast hh
        have hp'' : (p:ℤ) ≤ 6 := by exact_mod_cast hp'
        have hn : (0:ℤ) ≤ p := by exact_mod_cast Nat.zero_le p
        have hq : (0:ℤ) ≤ q := by exact_mod_cast Nat.zero_le q
        have hr : (0:ℤ) ≤ r := by exact_mod_cast Nat.zero_le r
        have hdiff : (0:ℤ) ≤ ((q:ℤ)-(r:ℤ))^2 := sq_nonneg _
        have hbig : (0:ℤ) ≤ ((q:ℤ)+(r:ℤ)-118) * ((q:ℤ)+(r:ℤ)+118) :=
          mul_nonneg (by omega) (by omega)
        nlinarith [sq_nonneg (p:ℤ)]
  6. If a + b + c = 124 and a(a-1) + b(b-1) + c(c-1) + 2x ≤ 5166, then 7 ≤ a, 7 ≤ b, 7 ≤ c, and x ≤ 82.

    Since x ≥ 0, we have a^2 + b^2 + c^2 ≤ 5290. Applying the helper result `hsize` to the permutations (a, b, c), (b, a, c), and (c, a, b) yields a ≥ 7, b ≥ 7, and c ≥ 7. Combining this with x ≤ 82 finishes the lemma.

    lines 55–58

      have hh : a*a+b*b+c*c ≤ 5290 := by omega
      refine ⟨hsize a b c hs hh, ?_, ?_, hx⟩
      · apply hsize b a c <;> omega
      · apply hsize c a b <;> omega
  7. The vertex set S = {x}ᶜ obtained by removing x from the 125 vertices has cardinality 124.

    By the formula for the cardinality of the complement of a subset of a finite type (`Fintype.card_compl_set`), |S| = |Fin 125| - |{x}| = 125 - 1 = 124.

    lines 66–75

    uses Fintype.card_compl_set

      classical
      let S : Set (Fin 125) := {x}ᶜ
      let H := G.induce S
      let E : Digraph S := ⟨fun _ _ => False⟩
      let color : S → Fin 3 := fun u => col u.1
      let n : Fin 3 → ℕ := fun i => (Finset.univ.filter fun v : S => color v = i).card
      have hcard : Fintype.card S = 124 := by
        dsimp [S]
        rw [Fintype.card_compl_set]
        simp
  8. The sizes n 0, n 1, n 2 of the three color classes in S sum to 124.

    Partitioning S into fibers of the coloring function `color` (`Finset.card_eq_sum_card_fiberwise`), the sum of the fiber cardinalities over the three colors in Fin 3 equals |S| = 124 (`Finset.card_univ`, `Fin.sum_univ_succ`, `Fin.sum_univ_zero`, `Nat.add_zero`).

    lines 76–81

    uses Finset.card_eq_sum_card_fiberwise, Finset.card_univ, Fin.sum_univ_succ, Fin.sum_univ_zero, Nat.add_zero

      have hsizes : n 0+n 1+n 2=124 := by
        have h := Finset.card_eq_sum_card_fiberwise (f := color) (s := (Finset.univ : Finset S))
          (t := (Finset.univ : Finset (Fin 3))) (by simp)
        simp only [Finset.card_univ, hcard, Fin.sum_univ_succ, Fin.sum_univ_zero, Nat.add_zero] at h
        change 124 = n 0+(n 1+n 2) at h
        omega
  9. The induced subgraph H = G[S] satisfies ∑_{i=0}^2 n_i (n_i - 1) ≤ 2 |E(H)|.

    Any two distinct vertices of S of the same color are distinct from x, so by the clique hypothesis they are adjacent in G and thus in H. Choosing the empty digraph E on S, the general clique partition bound `graph_clique_partition_oriented_cross_degree_bound` applies, yielding ∑_{i=0}^2 n_i (n_i - 1) ≤ 2 |E(H)| because there are no cross-edges in E.

    lines 82–96

    uses Subtype.ext, Set.mem_compl_iff, Set.mem_singleton_iff, graph_clique_partition_oriented_cross_degree_bound

      have hc : ∀ u v : S, color u = color v → u ≠ v → H.Adj u v := by
        intro u v hcolor hne
        have hu : u.1 ≠ x := by
          have hp : u.1 ∈ ({x}ᶜ : Set (Fin 125)) := u.2
          simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hp
        have hv : v.1 ≠ x := by
          have hp : v.1 ∈ ({x}ᶜ : Set (Fin 125)) := v.2
          simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hp
        have huv : u.1 ≠ v.1 := fun h => hne (Subtype.ext h)
        exact hclique u.1 v.1 hu hv hcolor huv
      have hsub : ∀ u v : S, E.Adj u v → H.Adj u v := by intros u v h; exact h.elim
      have hori : ∀ u v : S, E.Adj u v → ¬ E.Adj v u := by intros u v h; exact h.elim
      have hbound := graph_clique_partition_oriented_cross_degree_bound S (Fin 3) H E color hc hsub hori
      have hbound0 : (∑ i : Fin 3, n i * (n i - 1)) ≤ 2 * H.edgeFinset.card := by
        simpa [E,n,color] using hbound
  10. The sum expands to n 0 (n 0 - 1) + n 1 (n 1 - 1) + n 2 (n 2 - 1), and |E(H)| = |E(G)| - deg(x).

    Unfolding the sum over Fin 3 gives n 0 (n 0 - 1) + n 1 (n 1 - 1) + n 2 (n 2 - 1) (`Fin.sum_univ_succ`, `Fin.sum_univ_zero`, `Fin.succ_zero_eq_one`, `Fin.succ_one_eq_two`, `Nat.add_zero`). Inducing on the complement of {x} removes precisely the edges incident to x, so |E(H)| = |E(G)| - deg(x) (`SimpleGraph.card_edgeFinset_induce_compl_singleton`, `SimpleGraph.card_edgeFinset_deleteIncidenceSet`).

    lines 97–105

    uses Fin.sum_univ_succ, Fin.sum_univ_zero, Fin.succ_zero_eq_one, Fin.succ_one_eq_two, Nat.add_zero, SimpleGraph.card_edgeFinset_induce_compl_singleton, SimpleGraph.card_edgeFinset_deleteIncidenceSet

      have hre : (∑ i : Fin 3, n i * (n i - 1)) =
          n 0*(n 0-1)+n 1*(n 1-1)+n 2*(n 2-1) := by
        simp only [Fin.sum_univ_succ, Fin.sum_univ_zero, Fin.succ_zero_eq_one,
          Fin.succ_one_eq_two, Nat.add_zero]
        omega
      rw [hre] at hbound0
      have hcount : H.edgeFinset.card = G.edgeFinset.card - G.degree x := by
        dsimp [H,S]
        rw [SimpleGraph.card_edgeFinset_induce_compl_singleton, SimpleGraph.card_edgeFinset_deleteIncidenceSet]
  11. 2501 ≤ |E(H)|, and each color class size satisfies n_i ≥ 7.

    Applying the first arithmetic lemma `in833_exsz_bound124_7f3` with x = 0 yields 2501 ≤ |E(H)|. Since |E(G)| ≤ 2583, we have 2 |E(H)| ≤ 2 |E(G)| ≤ 5166, so the second arithmetic lemma `in833_exsz_arith124_7f3` applies with x = 0, giving n_i ≥ 7 for each i ∈ {0, 1, 2}.

    lines 106–108

    uses in833_exsz_bound124_7f3, in833_exsz_arith124_7f3

      have hbase := in833_exsz_bound124_7f3 (n 0) (n 1) (n 2) 0 H.edgeFinset.card hsizes (by omega)
      have hnum : n 0*(n 0-1)+n 1*(n 1-1)+n 2*(n 2-1)+2*0 ≤ 5166 := by omega
      have hsize := in833_exsz_arith124_7f3 (n 0) (n 1) (n 2) 0 hsizes hnum
  12. For each color i, the fiber size n_i equals the number of vertices v ≠ x in G with col(v) = i.

    We construct a bijection (`Finset.card_bij`) between the fiber of color i in S and the set of vertices v ∈ Fin 125 satisfying v ≠ x and col(v) = i, using the canonical embedding from the subtype S = {x}ᶜ into Fin 125 (`Set.mem_compl_iff`, `Set.mem_singleton_iff`, `Finset.mem_filter`, `Finset.mem_univ`, `true_and`, `Subtype.ext`).

    lines 109–128

    uses Finset.card_bij, Set.mem_compl_iff, Set.mem_singleton_iff, Finset.mem_filter, Finset.mem_univ, true_and, Subtype.ext

      have hconvert (i : Fin 3) : n i =
          (Finset.univ.filter fun v => v ≠ x ∧ col v = i).card := by
        dsimp [n]
        refine Finset.card_bij (fun v _ => v.1) ?_ ?_ ?_
        · intro v hv
          have hvx : v.1 ≠ x := by
            have hp : v.1 ∈ ({x}ᶜ : Set (Fin 125)) := v.2
            simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hp
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv ⊢
          exact ⟨hvx,hv⟩
        · intro u hu v hv huv
          exact Subtype.ext huv
        · intro v hv
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv
          have hvS : v ∈ S := by
            change v ∈ ({x}ᶜ : Set (Fin 125))
            simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hv.1
          refine ⟨⟨v,hvS⟩, ?_, rfl⟩
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          exact hv.2
  13. deg(x) + 2501 ≤ |E(G)|, and each of the three cliques on S contains at least 7 vertices.

    From |E(H)| = |E(G)| - deg(x) and 2501 ≤ |E(H)|, linear arithmetic yields deg(x) + 2501 ≤ |E(G)|. For each color i ∈ {0, 1, 2}, rewriting n_i via the bijection and invoking n_i ≥ 7 shows that each of the three cliques has at least 7 vertices.

    lines 129–136

      constructor
      · omega
      · intro i
        rw [← hconvert]
        fin_cases i
        · exact hsize.1
        · exact hsize.2.1
        · exact hsize.2.2.1
sq_nonneg
In any ordered semiring, the square of any element is non-negative (0 ≤ a^2).
Nat.zero_le
For any natural number n, 0 ≤ n.
mul_nonneg
The product of two non-negative numbers is non-negative (0 ≤ a and 0 ≤ b imply 0 ≤ a * b).
Fintype.card_compl_set
For a subset s of a finite type α, the cardinality of its complement is |α| - |s|.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set s equals the sum over all fibers of the fiber cardinalities: |s| = ∑_b |{a ∈ s | f(a) = b}|.
Finset.card_univ
The cardinality of the universal finset of a finite type α equals Fintype.card α.
Fin.sum_univ_succ
A sum over Fin (n + 1) splits into the term at 0 plus the sum over the remaining n elements: ∑ i, f i = f 0 + ∑ i, f (succ i).
Fin.sum_univ_zero
A sum over the empty index type Fin 0 is 0.
Nat.add_zero
For any natural number n, n + 0 = n.
Set.mem_compl_iff
An element belongs to the complement sᶜ if and only if it does not belong to s.
Set.mem_singleton_iff
An element a belongs to the singleton {b} if and only if a = b.
Subtype.ext
Two subtype elements are equal if and only if their underlying values are equal.
graph_clique_partition_oriented_cross_degree_bound
In a graph partitioned into cliques, ∑_i n_i (n_i - 1) plus twice the number of directed cross-edges is at most 2 |E(G)|.
Fin.succ_zero_eq_one
The successor of 0 in Fin (n + 1) is 1.
Fin.succ_one_eq_two
The successor of 1 in Fin (n + 1) is 2.
SimpleGraph.card_edgeFinset_induce_compl_singleton
The number of edges in the induced subgraph on {x}ᶜ equals the number of edges after deleting the incidence set of x.
SimpleGraph.card_edgeFinset_deleteIncidenceSet
Deleting the incidence set of a vertex x leaves |E(G)| - deg(x) edges.
in833_exsz_bound124_7f3
If natural numbers a, b, c, x, e satisfy a + b + c = 124 and a(a-1) + b(b-1) + c(c-1) + 2x ≤ 2e, then 2501 + x ≤ e.
in833_exsz_arith124_7f3
If natural numbers a, b, c, x satisfy a + b + c = 124 and a(a-1) + b(b-1) + c(c-1) + 2x ≤ 5166, then 7 ≤ a, 7 ≤ b, 7 ≤ c, and x ≤ 82.
Finset.card_bij
Two finite sets have equal cardinality if there exists a bijection between them.
Finset.mem_filter
An element belongs to a filtered set {x ∈ s | p x} if and only if it belongs to s and satisfies p.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
true_and
For any proposition p, (True ∧ p) is 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 2500000set_option maxRecDepth 4096private lemma in833_exsz_bound124_7f3 (a b c x e : ℕ) (hs : a+b+c=124)    (hbound : a*(a-1)+b*(b-1)+c*(c-1)+2*x ≤ 2*e) : 2501+x ≤ e := by  have hprod (n : ℕ) : n*(n-1)+n=n*n := by    cases n with    | zero => simp    | succ n => simp; ring  have ha := hprod a  have hb := hprod b  have hc := hprod c  have he : a*a+b*b+c*c+2*x ≤ 2*e+124 := by nlinarith  have hs' : (a:ℤ)+b+c=124 := by exact_mod_cast hs  have he' : (a:ℤ)*a+b*b+c*c+2*x ≤ 2*e+124 := by exact_mod_cast he  have h1 : (0:ℤ) ≤ ((a:ℤ)-b)^2 := sq_nonneg _  have h2 : (0:ℤ) ≤ ((a:ℤ)-c)^2 := sq_nonneg _  have h3 : (0:ℤ) ≤ ((b:ℤ)-c)^2 := sq_nonneg _  have out : (2501:ℤ)+x ≤ e := by nlinarith  exact_mod_cast outprivate lemma in833_exsz_arith124_7f3 (a b c x : ℕ) (hs : a + b + c = 124)    (h : a * (a - 1) + b * (b - 1) + c * (c - 1) + 2*x ≤ 5166) :    7 ≤ a ∧ 7 ≤ b ∧ 7 ≤ c ∧ x ≤ 82 := by  have hprod (n : ℕ) : n * (n - 1) + n = n*n := by    cases n with    | zero => simp    | succ n => simp; ring  have ha := hprod a  have hb := hprod b  have hc := hprod c  have hsum : a*a + b*b + c*c + 2*x ≤ 5290 := by nlinarith  have hx : x ≤ 82 := by    have h1 : (0:ℤ) ≤ ((a:ℤ) - b)^2 := sq_nonneg _    have h2 : (0:ℤ) ≤ ((b:ℤ) - c)^2 := sq_nonneg _    have h3 : (0:ℤ) ≤ ((a:ℤ) - c)^2 := sq_nonneg _    have hs' : (a:ℤ) + b + c = 124 := by exact_mod_cast hs    have hh' : (a:ℤ)*a + b*b + c*c + 2*x ≤ 5290 := by exact_mod_cast hsum    have out : (x:ℤ) ≤ 82 := by nlinarith    exact_mod_cast out  have hsize (p q r : ℕ) (hs : p+q+r=124)      (hh : p*p + q*q + r*r ≤ 5290) : 7 ≤ p := by    by_contra hp    have hp' : p ≤ 6 := by omega    have hs' : (p:ℤ) + q + r = 124 := by exact_mod_cast hs    have hh' : (p:ℤ)*p + q*q + r*r ≤ 5290 := by exact_mod_cast hh    have hp'' : (p:ℤ) ≤ 6 := by exact_mod_cast hp'    have hn : (0:ℤ) ≤ p := by exact_mod_cast Nat.zero_le p    have hq : (0:ℤ) ≤ q := by exact_mod_cast Nat.zero_le q    have hr : (0:ℤ) ≤ r := by exact_mod_cast Nat.zero_le r    have hdiff : (0:ℤ) ≤ ((q:ℤ)-(r:ℤ))^2 := sq_nonneg _    have hbig : (0:ℤ) ≤ ((q:ℤ)+(r:ℤ)-118) * ((q:ℤ)+(r:ℤ)+118) :=      mul_nonneg (by omega) (by omega)    nlinarith [sq_nonneg (p:ℤ)]  have hh : a*a+b*b+c*c ≤ 5290 := by omega  refine ⟨hsize a b c hs hh, ?_, ?_, hx⟩  · apply hsize b a c <;> omega  · apply hsize c a b <;> omegatheorem graph_125_three_cliques_except_vertex_bounds    (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj] (x : Fin 125) (col : Fin 125 → Fin 3)    (hclique : ∀ u v, u ≠ x → v ≠ x → col u = col v → u ≠ v → G.Adj u v)    (hedges : G.edgeFinset.card ≤ 2583) :    G.degree x + 2501 ≤ G.edgeFinset.card ∧    (∀ i, 7 ≤ (Finset.univ.filter fun v => v ≠ x ∧ col v = i).card) := by  classical  let S : Set (Fin 125) := {x}ᶜ  let H := G.induce S  let E : Digraph S := ⟨fun _ _ => False⟩  let color : S → Fin 3 := fun u => col u.1  let n : Fin 3 → ℕ := fun i => (Finset.univ.filter fun v : S => color v = i).card  have hcard : Fintype.card S = 124 := by    dsimp [S]    rw [Fintype.card_compl_set]    simp  have hsizes : n 0+n 1+n 2=124 := by    have h := Finset.card_eq_sum_card_fiberwise (f := color) (s := (Finset.univ : Finset S))      (t := (Finset.univ : Finset (Fin 3))) (by simp)    simp only [Finset.card_univ, hcard, Fin.sum_univ_succ, Fin.sum_univ_zero, Nat.add_zero] at h    change 124 = n 0+(n 1+n 2) at h    omega  have hc : ∀ u v : S, color u = color v → u ≠ v → H.Adj u v := by    intro u v hcolor hne    have hu : u.1 ≠ x := by      have hp : u.1 ∈ ({x}ᶜ : Set (Fin 125)) := u.2      simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hp    have hv : v.1 ≠ x := by      have hp : v.1 ∈ ({x}ᶜ : Set (Fin 125)) := v.2      simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hp    have huv : u.1 ≠ v.1 := fun h => hne (Subtype.ext h)    exact hclique u.1 v.1 hu hv hcolor huv  have hsub : ∀ u v : S, E.Adj u v → H.Adj u v := by intros u v h; exact h.elim  have hori : ∀ u v : S, E.Adj u v → ¬ E.Adj v u := by intros u v h; exact h.elim  have hbound := graph_clique_partition_oriented_cross_degree_bound S (Fin 3) H E color hc hsub hori  have hbound0 : (∑ i : Fin 3, n i * (n i - 1)) ≤ 2 * H.edgeFinset.card := by    simpa [E,n,color] using hbound  have hre : (∑ i : Fin 3, n i * (n i - 1)) =      n 0*(n 0-1)+n 1*(n 1-1)+n 2*(n 2-1) := by    simp only [Fin.sum_univ_succ, Fin.sum_univ_zero, Fin.succ_zero_eq_one,      Fin.succ_one_eq_two, Nat.add_zero]    omega  rw [hre] at hbound0  have hcount : H.edgeFinset.card = G.edgeFinset.card - G.degree x := by    dsimp [H,S]    rw [SimpleGraph.card_edgeFinset_induce_compl_singleton, SimpleGraph.card_edgeFinset_deleteIncidenceSet]  have hbase := in833_exsz_bound124_7f3 (n 0) (n 1) (n 2) 0 H.edgeFinset.card hsizes (by omega)  have hnum : n 0*(n 0-1)+n 1*(n 1-1)+n 2*(n 2-1)+2*0 ≤ 5166 := by omega  have hsize := in833_exsz_arith124_7f3 (n 0) (n 1) (n 2) 0 hsizes hnum  have hconvert (i : Fin 3) : n i =      (Finset.univ.filter fun v => v ≠ x ∧ col v = i).card := by    dsimp [n]    refine Finset.card_bij (fun v _ => v.1) ?_ ?_ ?_    · intro v hv      have hvx : v.1 ≠ x := by        have hp : v.1 ∈ ({x}ᶜ : Set (Fin 125)) := v.2        simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hp      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv ⊢      exact ⟨hvx,hv⟩    · intro u hu v hv huv      exact Subtype.ext huv    · intro v hv      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv      have hvS : v ∈ S := by        change v ∈ ({x}ᶜ : Set (Fin 125))        simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hv.1      refine ⟨⟨v,hvS⟩, ?_, rfl⟩      simp only [Finset.mem_filter, Finset.mem_univ, true_and]      exact hv.2  constructor  · omega  · intro i    rw [← hconvert]    fin_cases i    · exact hsize.1    · exact hsize.2.1    · exact hsize.2.2.1
See it in the graphDiscuss this resultChallenge it