graph_126_three_clique_partition_oriented_cross_bound
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
- digraph_126_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 126 vertices whose arcs have common predecessors and whose every in-neighborhood contains…
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.
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$.
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
$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$.
uses
sq_nonneghave 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
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`.
uses
Nat.zero_le,sq_nonneg,mul_nonneghave 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:ℤ)]
$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`.
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
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.
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_disjointclassical 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
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$.
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_zerohave 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
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.
uses
Finset.sum_fiberwise,Finset.sum_congr,Finset.mem_filter.mphave 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]
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.
uses
Finset.card_eq_sum_ones,Finset.sum_filter,Finset.sum_comm,Finset.sum_congr,Ne.symmhave 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]
$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.
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_zerohave 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
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$.
uses
in833_arithhave 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$.
- The non-linear arithmetic tactic `nlinarith` automatically completes the algebraic deductions in `in833_arith` (both the bound $x \le 21$ and the contradiction when a clique has size $\le 6$) by combining the given sum-of-squares certificates.
- The 3-clique partition is formalized via a coloring function `col : Fin 126 → Fin 3`, where each clique is the fiber of a color.
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 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