AFTD Auto-Formalizing Theoretical Domains

graph_126_three_clique_partition_oriented_cross_bound

theoremverified

For a graph on 126 vertices partitioned into three cliques, with at most 2604 graph edges, each part has at least seven vertices and every oriented subdigraph has at most 21 arcs between the parts.

Statement

theorem graph_126_three_clique_partition_oriented_cross_bound
    (G : SimpleGraph (Fin 126)) [DecidableRel G.Adj]
    (D : Digraph (Fin 126)) [DecidableRel D.Adj] (col : Fin 126 → Fin 3)
    (hclique : ∀ u v, col u = col v → u ≠ v → G.Adj u v)
    (hsub : ∀ u v, D.Adj u v → G.Adj u v)
    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)
    (hedges : G.edgeFinset.card ≤ 2604) :
    (∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card) ∧
    (∑ v : Fin 126, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) ≤ 21
Source
Edge-counting step for the order-126 reduction for OP-110.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem is proved by double-counting edges and applying Cauchy-Schwarz-type arithmetic bounds. For each vertex $v$, its neighbors within its clique, outgoing cross-arcs in the oriented subdigraph $D$, and incoming cross-arcs in $D$ are mutually disjoint and contained in its graph neighborhood, so their sizes sum to at most $\deg_G(v)$. Summing this over all 126 vertices gives $n_0(n_0-1) + n_1(n_1-1) + n_2(n_2-1) + 2x \le 2|E(G)| \le 5208$, where $n_i$ are the clique sizes and $x$ is the total number of cross-arcs. A helper lemma (`in833_arith`) then uses the algebraic constraint $n_0 + n_1 + n_2 = 126$ and the sum-of-squares inequality to deduce that $\sum n_i^2 \ge 5292$, which forces $x \le 21$ and prevents any clique from having fewer than 7 vertices.

  1. The sum of squares plus $2x$ satisfies $a^2 + b^2 + c^2 + 2x \le 5334$.

    By induction on $n$, we have $n(n - 1) + n = n^2$ for all natural numbers $n$. Applying this identity to $a, b, c$ and adding the result to $a(a-1) + b(b-1) + c(c-1) + 2x \le 5208$ using $a + b + c = 126$ yields $a^2 + b^2 + c^2 + 2x \le 5208 + 126 = 5334$.

    lines 6–13

      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 ≤ 5334 := by nlinarith
  2. $x \le 21$. automation

    The sum-of-squares inequality $(a-b)^2 + (b-c)^2 + (a-c)^2 \ge 0$ (via `sq_nonneg`) is equivalent to $3(a^2 + b^2 + c^2) \ge (a+b+c)^2 = 126^2 = 15876$, so $a^2 + b^2 + c^2 \ge 5292$. Combining this with $a^2 + b^2 + c^2 + 2x \le 5334$, non-linear integer arithmetic (`nlinarith`) deduces $2x \le 5334 - 5292 = 42$, whence $x \le 21$.

    lines 14–21

    uses sq_nonneg

      have hx : x ≤ 21 := 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 = 126 := by exact_mod_cast hs
        have hh' : (a:ℤ)*a + b*b + c*c + 2*x ≤ 5334 := by exact_mod_cast hsum
        have out : (x:ℤ) ≤ 21 := by nlinarith
        exact_mod_cast out
  3. If non-negative integers $p, q, r$ satisfy $p + q + r = 126$ and $p^2 + q^2 + r^2 \le 5334$, then $p \ge 7$. automation

    Suppose for contradiction that $p \le 6$. Then $q + r = 126 - p \ge 120$. Since $(q - r)^2 \ge 0$ and $(q + r - 120)(q + r + 120) \ge 0$, we have $2(q^2 + r^2) = (q + r)^2 + (q - r)^2 \ge 120^2 = 14400$, so $q^2 + r^2 \ge 7200 > 5334$, a contradiction derived by `nlinarith`.

    lines 22–35

    uses Nat.zero_le, sq_nonneg, mul_nonneg

      have hsize (p q r : ℕ) (hs : p+q+r=126)
          (hh : p*p + q*q + r*r ≤ 5334) : 7 ≤ p := by
        by_contra hp
        have hp' : p ≤ 6 := by omega
        have hs' : (p:ℤ) + q + r = 126 := by exact_mod_cast hs
        have hh' : (p:ℤ)*p + q*q + r*r ≤ 5334 := 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:ℤ)-120) * ((q:ℤ)+(r:ℤ)+120) :=
          mul_nonneg (by omega) (by omega)
        nlinarith [sq_nonneg (p:ℤ)]
  4. $7 \le a \land 7 \le b \land 7 \le c \land x \le 21$.

    Since $x \ge 0$, we have $a^2 + b^2 + c^2 \le 5334$. Applying the helper `hsize` to $(a, b, c)$, $(b, a, c)$, and $(c, a, b)$ gives $7 \le a$, $7 \le b$, and $7 \le c$, which together with $x \le 21$ completes the proof of `in833_arith`.

    lines 36–39

      have hh : a*a+b*b+c*c ≤ 5334 := by omega
      refine ⟨hsize a b c hs hh, ?_, ?_, hx⟩
      · apply hsize b a c <;> omega
      · apply hsize c a b <;> omega
  5. For each vertex $v$, its internal clique neighbors, outgoing cross-arcs in $D$, and incoming cross-arcs in $D$ are pairwise disjoint subsets of its graph neighborhood, so $|\text{inside}(v)| + |\text{out}(v)| + |\text{inc}(v)| \le \deg_G(v)$.

    Define the color classes $S_i$, their sizes $n_i$, the internal neighbors $\text{inside}(v) = S_{\text{col}(v)} \setminus \{v\}$, outgoing cross-neighbors $\text{out}(v)$, and incoming cross-neighbors $\text{inc}(v)$ in $D$. Internal neighbors share the color of $v$, whereas cross-neighbors have different colors, making $\text{inside}(v)$ disjoint from $\text{out}(v)$ and $\text{inc}(v)$. Since $D$ is an oriented graph, no pair has arcs in both directions, so $\text{out}(v)$ and $\text{inc}(v)$ are disjoint. All internal neighbors are adjacent to $v$ in $G$ because color classes are cliques, and all cross-neighbors are adjacent to $v$ in $G$ because $D$ is a subgraph of $G$. Thus their disjoint union is contained in the neighborhood of $v$, giving the degree bound.

    lines 50–91

    uses Finset.disjoint_left.mpr, Finset.mem_filter.mp, Finset.mem_erase.mp, Finset.disjoint_union_right.mpr, SimpleGraph.mem_neighborFinset, Finset.mem_union.mp, Finset.card_le_card, Finset.card_union_of_disjoint

      classical
      let S : Fin 3 → Finset (Fin 126) := fun i => Finset.univ.filter fun v => col v = i
      let n : Fin 3 → ℕ := fun i => (S i).card
      let inside : Fin 126 → Finset (Fin 126) := fun v => (S (col v)).erase v
      let out : Fin 126 → Finset (Fin 126) := fun v =>
        Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w
      let inc : Fin 126 → Finset (Fin 126) := fun v =>
        Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj w v
      have hlocal (v : Fin 126) : (inside v).card + (out v).card + (inc v).card ≤ G.degree v := by
        have hab : Disjoint (inside v) (out v) := by
          apply Finset.disjoint_left.mpr
          intro w hw1 hw2
          have h1 : col w = col v := (Finset.mem_filter.mp (Finset.mem_erase.mp hw1).2).2
          have h2 : col w ≠ col v := (Finset.mem_filter.mp hw2).2.1
          exact h2 h1
        have hac : Disjoint (inside v) (inc v) := by
          apply Finset.disjoint_left.mpr
          intro w hw1 hw2
          have h1 : col w = col v := (Finset.mem_filter.mp (Finset.mem_erase.mp hw1).2).2
          have h2 : col w ≠ col v := (Finset.mem_filter.mp hw2).2.1
          exact h2 h1
        have hbc : Disjoint (out v) (inc v) := by
          apply Finset.disjoint_left.mpr
          intro w hw1 hw2
          have h1 : D.Adj v w := (Finset.mem_filter.mp hw1).2.2
          have h2 : D.Adj w v := (Finset.mem_filter.mp hw2).2.2
          exact hori v w h1 h2
        have hall : Disjoint (inside v) (out v ∪ inc v) := Finset.disjoint_union_right.mpr ⟨hab, hac⟩
        have hsubset : inside v ∪ (out v ∪ inc v) ⊆ G.neighborFinset v := by
          intro w hw
          simp only [SimpleGraph.mem_neighborFinset]
          rcases Finset.mem_union.mp hw with ha | ha
          · have hw' := Finset.mem_erase.mp ha
            have hc : col w = col v := (Finset.mem_filter.mp hw'.2).2
            exact hclique v w hc.symm hw'.1.symm
          · rcases Finset.mem_union.mp ha with hb | hc
            · exact hsub v w (Finset.mem_filter.mp hb).2.2
            · exact (hsub w v (Finset.mem_filter.mp hc).2.2).symm
        have hh := Finset.card_le_card hsubset
        rw [Finset.card_union_of_disjoint hall, Finset.card_union_of_disjoint hbc] at hh
        change _ ≤ G.degree v at hh
        omega
  6. Each vertex has $n(\text{col}(v)) - 1$ internal neighbors, and the sizes of the three cliques sum to 126.

    Removing $v$ from its own clique $S_{\text{col}(v)}$ gives cardinality $n(\text{col}(v)) - 1$ via `Finset.card_erase_of_mem`. Partitioning the 126 vertices fiberwise by their color using `Finset.card_eq_sum_card_fiberwise` and summing over $\text{Fin } 3$ establishes $n(0) + n(1) + n(2) = 126$.

    lines 92–101

    uses Finset.card_erase_of_mem, Finset.card_eq_sum_card_fiberwise, Finset.card_univ, Fintype.card_fin, Fin.sum_univ_succ, Fin.sum_univ_zero, Nat.add_zero

      have hcount (v : Fin 126) : (inside v).card = n (col v) - 1 := by
        apply Finset.card_erase_of_mem
        simp [S]
      have hsizes : n 0 + n 1 + n 2 = 126 := by
        have h := Finset.card_eq_sum_card_fiberwise (f := col) (s := (Finset.univ : Finset (Fin 126)))
            (t := (Finset.univ : Finset (Fin 3))) (by simp)
        simp only [Finset.card_univ, Fintype.card_fin, Fin.sum_univ_succ,
          Fin.sum_univ_zero, Nat.add_zero] at h
        change 126 = n 0 + (n 1 + n 2) at h
        omega
  7. The sum of internal neighbor counts over all vertices is $\sum_{i=0}^2 n(i)(n(i) - 1)$.

    Grouping the sum over all vertices fiberwise by their color via `Finset.sum_fiberwise`, each color class $i$ contains $n(i)$ vertices that each have $n(i) - 1$ internal neighbors, giving the product $n(i)(n(i) - 1)$ for each part.

    lines 102–113

    uses Finset.sum_fiberwise, Finset.sum_congr, Finset.mem_filter.mp

      have hinside : (∑ v : Fin 126, (inside v).card) = ∑ i : Fin 3, n i * (n i - 1) := by
        simp_rw [hcount]
        rw [← Finset.sum_fiberwise Finset.univ col]
        apply Finset.sum_congr rfl
        intro i hi
        calc
          (∑ v ∈ Finset.univ.filter (fun v => col v = i), (n (col v) - 1)) =
              ∑ _v ∈ Finset.univ.filter (fun v => col v = i), (n i - 1) := by
                apply Finset.sum_congr rfl
                intro v hv
                rw [(Finset.mem_filter.mp hv).2]
          _ = n i * (n i - 1) := by simp [n,S]
  8. The total number of outgoing cross-arcs equals the total number of incoming cross-arcs.

    Double counting cross-arcs by exchanging the order of summation (`Finset.sum_comm`) shows that summing outgoing cross-degrees over all vertices gives the same total as summing incoming cross-degrees.

    lines 114–121

    uses Finset.card_eq_sum_ones, Finset.sum_filter, Finset.sum_comm, Finset.sum_congr, Ne.symm

      have hcross : (∑ v : Fin 126, (out v).card) = ∑ v : Fin 126, (inc v).card := by
        simp only [out, inc, Finset.card_eq_sum_ones, Finset.sum_filter]
        rw [Finset.sum_comm]
        apply Finset.sum_congr rfl
        intro v hv
        apply Finset.sum_congr rfl
        intro w hw
        by_cases h : col w = col v <;> by_cases hd : D.Adj v w <;> simp [h, Ne.symm, hd]
  9. $n(0)(n(0)-1) + n(1)(n(1)-1) + n(2)(n(2)-1) + 2 \sum_v |\text{out}(v)| \le 5208$.

    Summing the local bound $|\text{inside}(v)| + |\text{out}(v)| + |\text{inc}(v)| \le \deg_G(v)$ over all vertices and applying Euler's handshaking lemma (`G.sum_degrees_eq_twice_card_edges`) gives $\sum_i n(i)(n(i)-1) + 2 \sum_v |\text{out}(v)| \le \sum \deg_G(v) = 2 |E(G)| \le 2 \times 2604 = 5208$. Unfolding the sum over $\text{Fin } 3$ gives the explicit three-term sum.

    lines 122–135

    uses Finset.sum_le_sum, Finset.sum_add_distrib, G.sum_degrees_eq_twice_card_edges, Fin.sum_univ_succ, Fin.sum_univ_zero, Fin.succ_zero_eq_one, Fin.succ_one_eq_two, Nat.add_zero

      have hsum : (∑ i : Fin 3, n i * (n i - 1)) + 2 * (∑ v : Fin 126, (out v).card) ≤ 5208 := by
        have hh := Finset.sum_le_sum (fun v (_ : v ∈ (Finset.univ : Finset (Fin 126))) => hlocal v)
        simp only [Finset.sum_add_distrib] at hh
        rw [hinside, ← hcross, G.sum_degrees_eq_twice_card_edges] at hh
        omega
      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
      have hs : n 0 * (n 0 - 1) + n 1 * (n 1 - 1) + n 2 * (n 2 - 1) +
          2 * (∑ v : Fin 126, (out v).card) ≤ 5208 := by
        rw [hre] at hsum
        exact hsum
  10. Each clique has at least 7 vertices and the total number of cross-arcs in $D$ is at most 21.

    Applying the arithmetic lemma `in833_arith` with $a = n(0), b = n(1), c = n(2)$, and $x = \sum_v |\text{out}(v)|$ immediately yields $7 \le n(i)$ for all $i \in \{0, 1, 2\}$ and $x \le 21$.

    lines 136–144

    uses in833_arith

      have h := in833_arith (n 0) (n 1) (n 2) _ hsizes hs
      constructor
      · intro i
        change 7 ≤ n i
        fin_cases i
        · exact h.1
        · exact h.2.1
        · exact h.2.2.1
      · exact h.2.2.2
sq_nonneg
The square of any real or integer number is non-negative ($0 \le a^2$).
Nat.zero_le
Every natural number is greater than or equal to zero.
mul_nonneg
The product of two non-negative numbers is non-negative.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first set belongs to the second set.
Finset.mem_filter.mp
An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the condition.
Finset.mem_erase.mp
An element belongs to a set with an element erased if and only if it was in the original set and not equal to the erased element.
Finset.disjoint_union_right.mpr
If a set is disjoint from two sets, it is disjoint from their union.
SimpleGraph.mem_neighborFinset
A vertex is in the neighbor finset of $v$ if and only if it is adjacent to $v$.
Finset.mem_union.mp
An element of a union of two sets belongs to at least one of the two sets.
Finset.card_le_card
If $s \subseteq t$ for finite sets, then $|s| \le |t|$.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_erase_of_mem
Removing an element from a finite set decreases its cardinality by one.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set is the sum of the cardinalities of its fibers under a map.
Finset.card_univ
The cardinality of the universal set of a finite type is the cardinality of the type.
Fintype.card_fin
The standard finite type $\text{Fin } n$ has cardinality $n$.
Fin.sum_univ_succ
A sum over $\text{Fin } (n + 1)$ splits into the term at 0 plus the sum over the successors.
Fin.sum_univ_zero
A sum over the empty type $\text{Fin } 0$ is zero.
Nat.add_zero
Adding zero to a natural number does not change it.
Finset.sum_fiberwise
Summing over a finite set can be computed by grouping into fibers over a finite partition and summing fiberwise.
Finset.sum_congr
Two sums over the same finite set are equal if their summands agree on all elements.
Finset.card_eq_sum_ones
The cardinality of a finite set equals the sum of 1 over all of its elements.
Finset.sum_filter
Summing over a filtered set equals summing over the whole set with an indicator function for the predicate.
Finset.sum_comm
The order of two finite summations can be interchanged (Fubini's theorem for finite sums).
Ne.symm
Inequality is symmetric: $a \ne b \implies b \ne a$.
Finset.sum_le_sum
If $f(i) \le g(i)$ for all elements $i$ of a finite set, then $\sum_i f(i) \le \sum_i g(i)$.
Finset.sum_add_distrib
The sum of a sum of functions over a finite set equals the sum of their individual sums.
G.sum_degrees_eq_twice_card_edges
In any finite graph, the sum of vertex degrees equals twice the number of edges (Euler's handshaking lemma).
Fin.succ_zero_eq_one
The successor of 0 in $\text{Fin } (n + 2)$ is 1.
Fin.succ_one_eq_two
The successor of 1 in $\text{Fin } (n + 3)$ is 2.
in833_arith
An arithmetic lemma: if non-negative integers $a, b, c, x$ satisfy $a + b + c = 126$ and $a(a-1) + b(b-1) + c(c-1) + 2x \le 5208$, then $a \ge 7$, $b \ge 7$, $c \ge 7$, and $x \le 21$.

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 2000000set_option maxRecDepth 4096private lemma in833_arith (a b c x : ℕ) (hs : a + b + c = 126)    (h : a * (a - 1) + b * (b - 1) + c * (c - 1) + 2*x ≤ 5208) :    7 ≤ a ∧ 7 ≤ b ∧ 7 ≤ c ∧ x ≤ 21 := 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 ≤ 5334 := by nlinarith  have hx : x ≤ 21 := 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 = 126 := by exact_mod_cast hs    have hh' : (a:ℤ)*a + b*b + c*c + 2*x ≤ 5334 := by exact_mod_cast hsum    have out : (x:ℤ) ≤ 21 := by nlinarith    exact_mod_cast out  have hsize (p q r : ℕ) (hs : p+q+r=126)      (hh : p*p + q*q + r*r ≤ 5334) : 7 ≤ p := by    by_contra hp    have hp' : p ≤ 6 := by omega    have hs' : (p:ℤ) + q + r = 126 := by exact_mod_cast hs    have hh' : (p:ℤ)*p + q*q + r*r ≤ 5334 := 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:ℤ)-120) * ((q:ℤ)+(r:ℤ)+120) :=      mul_nonneg (by omega) (by omega)    nlinarith [sq_nonneg (p:ℤ)]  have hh : a*a+b*b+c*c ≤ 5334 := by omega  refine ⟨hsize a b c hs hh, ?_, ?_, hx⟩  · apply hsize b a c <;> omega  · apply hsize c a b <;> omegatheorem graph_126_three_clique_partition_oriented_cross_bound    (G : SimpleGraph (Fin 126)) [DecidableRel G.Adj]    (D : Digraph (Fin 126)) [DecidableRel D.Adj] (col : Fin 126 → Fin 3)    (hclique : ∀ u v, col u = col v → u ≠ v → G.Adj u v)    (hsub : ∀ u v, D.Adj u v → G.Adj u v)    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)    (hedges : G.edgeFinset.card ≤ 2604) :    (∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card) ∧    (∑ v : Fin 126, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) ≤ 21 := by  classical  let S : Fin 3 → Finset (Fin 126) := fun i => Finset.univ.filter fun v => col v = i  let n : Fin 3 → ℕ := fun i => (S i).card  let inside : Fin 126 → Finset (Fin 126) := fun v => (S (col v)).erase v  let out : Fin 126 → Finset (Fin 126) := fun v =>    Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w  let inc : Fin 126 → Finset (Fin 126) := fun v =>    Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj w v  have hlocal (v : Fin 126) : (inside v).card + (out v).card + (inc v).card ≤ G.degree v := by    have hab : Disjoint (inside v) (out v) := by      apply Finset.disjoint_left.mpr      intro w hw1 hw2      have h1 : col w = col v := (Finset.mem_filter.mp (Finset.mem_erase.mp hw1).2).2      have h2 : col w ≠ col v := (Finset.mem_filter.mp hw2).2.1      exact h2 h1    have hac : Disjoint (inside v) (inc v) := by      apply Finset.disjoint_left.mpr      intro w hw1 hw2      have h1 : col w = col v := (Finset.mem_filter.mp (Finset.mem_erase.mp hw1).2).2      have h2 : col w ≠ col v := (Finset.mem_filter.mp hw2).2.1      exact h2 h1    have hbc : Disjoint (out v) (inc v) := by      apply Finset.disjoint_left.mpr      intro w hw1 hw2      have h1 : D.Adj v w := (Finset.mem_filter.mp hw1).2.2      have h2 : D.Adj w v := (Finset.mem_filter.mp hw2).2.2      exact hori v w h1 h2    have hall : Disjoint (inside v) (out v ∪ inc v) := Finset.disjoint_union_right.mpr ⟨hab, hac⟩    have hsubset : inside v ∪ (out v ∪ inc v) ⊆ G.neighborFinset v := by      intro w hw      simp only [SimpleGraph.mem_neighborFinset]      rcases Finset.mem_union.mp hw with ha | ha      · have hw' := Finset.mem_erase.mp ha        have hc : col w = col v := (Finset.mem_filter.mp hw'.2).2        exact hclique v w hc.symm hw'.1.symm      · rcases Finset.mem_union.mp ha with hb | hc        · exact hsub v w (Finset.mem_filter.mp hb).2.2        · exact (hsub w v (Finset.mem_filter.mp hc).2.2).symm    have hh := Finset.card_le_card hsubset    rw [Finset.card_union_of_disjoint hall, Finset.card_union_of_disjoint hbc] at hh    change _ ≤ G.degree v at hh    omega  have hcount (v : Fin 126) : (inside v).card = n (col v) - 1 := by    apply Finset.card_erase_of_mem    simp [S]  have hsizes : n 0 + n 1 + n 2 = 126 := by    have h := Finset.card_eq_sum_card_fiberwise (f := col) (s := (Finset.univ : Finset (Fin 126)))        (t := (Finset.univ : Finset (Fin 3))) (by simp)    simp only [Finset.card_univ, Fintype.card_fin, Fin.sum_univ_succ,      Fin.sum_univ_zero, Nat.add_zero] at h    change 126 = n 0 + (n 1 + n 2) at h    omega  have hinside : (∑ v : Fin 126, (inside v).card) = ∑ i : Fin 3, n i * (n i - 1) := by    simp_rw [hcount]    rw [← Finset.sum_fiberwise Finset.univ col]    apply Finset.sum_congr rfl    intro i hi    calc      (∑ v ∈ Finset.univ.filter (fun v => col v = i), (n (col v) - 1)) =          ∑ _v ∈ Finset.univ.filter (fun v => col v = i), (n i - 1) := by            apply Finset.sum_congr rfl            intro v hv            rw [(Finset.mem_filter.mp hv).2]      _ = n i * (n i - 1) := by simp [n,S]  have hcross : (∑ v : Fin 126, (out v).card) = ∑ v : Fin 126, (inc v).card := by    simp only [out, inc, Finset.card_eq_sum_ones, Finset.sum_filter]    rw [Finset.sum_comm]    apply Finset.sum_congr rfl    intro v hv    apply Finset.sum_congr rfl    intro w hw    by_cases h : col w = col v <;> by_cases hd : D.Adj v w <;> simp [h, Ne.symm, hd]  have hsum : (∑ i : Fin 3, n i * (n i - 1)) + 2 * (∑ v : Fin 126, (out v).card) ≤ 5208 := by    have hh := Finset.sum_le_sum (fun v (_ : v ∈ (Finset.univ : Finset (Fin 126))) => hlocal v)    simp only [Finset.sum_add_distrib] at hh    rw [hinside, ← hcross, G.sum_degrees_eq_twice_card_edges] at hh    omega  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  have hs : n 0 * (n 0 - 1) + n 1 * (n 1 - 1) + n 2 * (n 2 - 1) +      2 * (∑ v : Fin 126, (out v).card) ≤ 5208 := by    rw [hre] at hsum    exact hsum  have h := in833_arith (n 0) (n 1) (n 2) _ hsizes hs  constructor  · intro i    change 7 ≤ n i    fin_cases i    · exact h.1    · exact h.2.1    · exact h.2.2.1  · exact h.2.2.2
See it in the graphDiscuss this resultChallenge it