graph_125_three_cliques_except_vertex_bounds
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
- graph_clique_partition_oriented_cross_degree_boundIf the color classes of a finite graph are cliques and an oriented digraph is a spanning subgraph, then twice its number of crossing arcs…
- Used by 1
- 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…
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.
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.
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
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.
uses
sq_nonneghave 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
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.
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
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.
uses
sq_nonneghave 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
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.
uses
sq_nonneg,mul_nonneg,Nat.zero_lehave 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:ℤ)]
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.
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
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.
uses
Fintype.card_compl_setclassical 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
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`).
uses
Finset.card_eq_sum_card_fiberwise,Finset.card_univ,Fin.sum_univ_succ,Fin.sum_univ_zero,Nat.add_zerohave 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
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.
uses
Subtype.ext,Set.mem_compl_iff,Set.mem_singleton_iff,graph_clique_partition_oriented_cross_degree_boundhave 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
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`).
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_deleteIncidenceSethave 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]
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}.
uses
in833_exsz_bound124_7f3,in833_exsz_arith124_7f3have 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
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`).
uses
Finset.card_bij,Set.mem_compl_iff,Set.mem_singleton_iff,Finset.mem_filter,Finset.mem_univ,true_and,Subtype.exthave 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
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.
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.
- The quadratic optimization bounds on the clique sizes and edge count are verified algebraically over the integers using nonlinear arithmetic (nlinarith), which automatically combines Cauchy-Schwarz-type square inequalities such as (a - b)^2 ≥ 0 with the linear constraint a + b + c = 124.
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 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