AFTD Auto-Formalizing Theoretical Domains

graph_125_three_clique_partition_oriented_cross_bound

theoremverified

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

Statement

theorem graph_125_three_clique_partition_oriented_cross_bound
    (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj]
    (D : Digraph (Fin 125)) [DecidableRel D.Adj] (col : Fin 125 → 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 ≤ 2583) :
    (∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card) ∧
    (∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) ≤ 41
Source
Edge-counting step for the order-125 reduction for OP-110.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The theorem is proved by combining a general degree-counting inequality for clique-partitioned graphs with algebraic optimization. First, the general bound `graph_clique_partition_oriented_cross_degree_bound` shows that the three clique sizes n_0, n_1, n_2 and the number of cross-arcs x satisfy ∑_{i=0}^2 n_i(n_i-1) + 2x ≤ 2|E(G)| ≤ 5166. Since the parts partition the 125 vertices, adding n_0 + n_1 + n_2 = 125 yields n_0^2 + n_1^2 + n_2^2 + 2x ≤ 5291. By the Cauchy-Schwarz inequality, 3(n_0^2 + n_1^2 + n_2^2) ≥ (n_0 + n_1 + n_2)^2 = 125^2, which forces x ≤ 41. Finally, if any part had size at most 6, the sum of the remaining two would be at least 119, forcing the sum of their squares to exceed 5291; hence each part must have at least 7 vertices.

  1. a^2 + b^2 + c^2 + 2x ≤ 5291

    For any natural number n, the identity n(n - 1) + n = n^2 holds, checked by case analysis on whether n is 0 or succ n. Adding the equation a + b + c = 125 to the hypothesis a(a - 1) + b(b - 1) + c(c - 1) + 2x ≤ 5166 transforms each n(n - 1) + n into n^2, giving a^2 + b^2 + c^2 + 2x ≤ 5166 + 125 = 5291.

    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 ≤ 5291 := by nlinarith
  2. x ≤ 41

    Over the integers, the squares of differences (a - b)^2, (b - c)^2, and (a - c)^2 are non-negative. Expanding these differences gives 3(a^2 + b^2 + c^2) - (a + b + c)^2 ≥ 0, which implies 3(a^2 + b^2 + c^2) ≥ 125^2 = 15625. Multiplying a^2 + b^2 + c^2 + 2x ≤ 5291 by 3 gives 3(a^2 + b^2 + c^2) + 6x ≤ 15873, so 6x ≤ 15873 - 15625 = 248, which implies x ≤ 41.

    lines 14–21

    uses sq_nonneg

      have hx : x ≤ 41 := 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 = 125 := by exact_mod_cast hs
        have hh' : (a:ℤ)*a + b*b + c*c + 2*x ≤ 5291 := by exact_mod_cast hsum
        have out : (x:ℤ) ≤ 41 := by nlinarith
        exact_mod_cast out
  3. Any non-negative integers p, q, r satisfying p + q + r = 125 and p^2 + q^2 + r^2 ≤ 5291 satisfy p ≥ 7

    Suppose for contradiction that p ≤ 6. Then q + r = 125 - p ≥ 119, so (q + r - 119)(q + r + 119) ≥ 0. Together with the non-negativity of (q - r)^2, this implies 2(q^2 + r^2) ≥ (q + r)^2 ≥ 119^2 = 14161, whence q^2 + r^2 ≥ 7080.5. Since p^2 ≥ 0, this forces p^2 + q^2 + r^2 > 5291, contradicting the upper bound p^2 + q^2 + r^2 ≤ 5291.

    lines 22–35

    uses sq_nonneg, Nat.zero_le, mul_nonneg

      have hsize (p q r : ℕ) (hs : p+q+r=125)
          (hh : p*p + q*q + r*r ≤ 5291) : 7 ≤ p := by
        by_contra hp
        have hp' : p ≤ 6 := by omega
        have hs' : (p:ℤ) + q + r = 125 := by exact_mod_cast hs
        have hh' : (p:ℤ)*p + q*q + r*r ≤ 5291 := 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:ℤ)-119) * ((q:ℤ)+(r:ℤ)+119) :=
          mul_nonneg (by omega) (by omega)
        nlinarith [sq_nonneg (p:ℤ)]
  4. 7 ≤ a ∧ 7 ≤ b ∧ 7 ≤ c ∧ x ≤ 41

    Since 2x ≥ 0, we have a^2 + b^2 + c^2 ≤ 5291. Applying the helper bound `hsize` to (a, b, c), (b, a, c), and (c, a, b) gives 7 ≤ a, 7 ≤ b, and 7 ≤ c respectively. Combining these three inequalities with x ≤ 41 finishes the lemma.

    lines 36–39

      have hh : a*a+b*b+c*c ≤ 5291 := by omega
      refine ⟨hsize a b c hs hh, ?_, ?_, hx⟩
      · apply hsize b a c <;> omega
      · apply hsize c a b <;> omega
  5. The sizes n_0, n_1, n_2 of the three color classes satisfy n_0 + n_1 + n_2 = 125

    Let S_i = {v | col(v) = i} be the color classes, n_i = |S_i| their cardinalities, and cross the number of oriented cross-arcs. By `Finset.card_eq_sum_card_fiberwise`, the total number of vertices (125) equals the sum of the cardinalities of the fibers of col over Fin 3, which expands to n_0 + n_1 + n_2 = 125.

    lines 50–60

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

      classical
      let S : Fin 3 → Finset (Fin 125) := fun i => Finset.univ.filter fun v => col v = i
      let n : Fin 3 → ℕ := fun i => (S i).card
      let cross : ℕ := ∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card
      have hsizes : n 0 + n 1 + n 2 = 125 := by
        have h := Finset.card_eq_sum_card_fiberwise (f := col) (s := (Finset.univ : Finset (Fin 125)))
            (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 125 = n 0 + (n 1 + n 2) at h
        omega
  6. n_0(n_0 - 1) + n_1(n_1 - 1) + n_2(n_2 - 1) + 2 · cross ≤ 5166

    We apply `graph_clique_partition_oriented_cross_degree_bound`, which establishes that the sum of the clique edge terms plus 2 · cross is at most 2|E(G)|. Unfolding the sum over Fin 3 into the three explicit terms and using the graph edge bound |E(G)| ≤ 2583 yields the upper bound 2 · 2583 = 5166.

    lines 61–69

    uses graph_clique_partition_oriented_cross_degree_bound, Fin.sum_univ_succ, Fin.sum_univ_zero, Fin.succ_zero_eq_one, Fin.succ_one_eq_two, Nat.add_zero

      have hbound := graph_clique_partition_oriented_cross_degree_bound (Fin 125) (Fin 3) G D col hclique hsub hori
      change (∑ i : Fin 3, n i * (n i - 1)) + 2 * cross ≤ 2 * G.edgeFinset.card at 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 hbound
      have ht : n 0 * (n 0 - 1) + n 1 * (n 1 - 1) + n 2 * (n 2 - 1) + 2*cross ≤ 5166 := by omega
  7. The bounds 7 ≤ n_i for each i ∈ Fin 3 and cross ≤ 41 hold, completing the proof

    We instantiate lemma `in833_arith125` with the part sizes n_0, n_1, n_2 and the cross-arc count cross. This supplies 7 ≤ n_0, 7 ≤ n_1, 7 ≤ n_2, and cross ≤ 41. We conclude by dispatching the universal quantifier 7 ≤ n_i via case analysis on i ∈ Fin 3 and taking the cross-arc inequality directly.

    lines 70–78

    uses in833_arith125

      have h := in833_arith125 (n 0) (n 1) (n 2) cross hsizes ht
      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 element in an ordered semiring (such as the integers) is non-negative.
mul_nonneg
The product of two non-negative numbers is non-negative.
Nat.zero_le
Every natural number is greater than or equal to zero.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set is the sum of the cardinalities of its fibers under any map.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
Fin.sum_univ_succ
A sum over Fin (n + 1) splits into the term at 0 plus the sum over the remaining n elements.
Fin.sum_univ_zero
A sum over the empty type Fin 0 is 0.
Nat.add_zero
Adding zero to a natural number leaves it unchanged.
graph_clique_partition_oriented_cross_degree_bound
For a graph partitioned into cliques and any oriented subdigraph, the sum over all parts of n_i * (n_i - 1) plus twice the number of cross-arcs is at most twice the number of graph edges.
Fin.succ_zero_eq_one
The successor of 0 in Fin n is 1.
Fin.succ_one_eq_two
The successor of 1 in Fin n is 2.
in833_arith125
If natural numbers a, b, c sum to 125 and a(a-1) + b(b-1) + c(c-1) + 2x ≤ 5166, then a ≥ 7, b ≥ 7, c ≥ 7, and x ≤ 41.

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_arith125 (a b c x : ℕ) (hs : a + b + c = 125)    (h : a * (a - 1) + b * (b - 1) + c * (c - 1) + 2*x ≤ 5166) :    7 ≤ a ∧ 7 ≤ b ∧ 7 ≤ c ∧ x ≤ 41 := 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 ≤ 5291 := by nlinarith  have hx : x ≤ 41 := 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 = 125 := by exact_mod_cast hs    have hh' : (a:ℤ)*a + b*b + c*c + 2*x ≤ 5291 := by exact_mod_cast hsum    have out : (x:ℤ) ≤ 41 := by nlinarith    exact_mod_cast out  have hsize (p q r : ℕ) (hs : p+q+r=125)      (hh : p*p + q*q + r*r ≤ 5291) : 7 ≤ p := by    by_contra hp    have hp' : p ≤ 6 := by omega    have hs' : (p:ℤ) + q + r = 125 := by exact_mod_cast hs    have hh' : (p:ℤ)*p + q*q + r*r ≤ 5291 := 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:ℤ)-119) * ((q:ℤ)+(r:ℤ)+119) :=      mul_nonneg (by omega) (by omega)    nlinarith [sq_nonneg (p:ℤ)]  have hh : a*a+b*b+c*c ≤ 5291 := 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_clique_partition_oriented_cross_bound    (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj]    (D : Digraph (Fin 125)) [DecidableRel D.Adj] (col : Fin 125 → 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 ≤ 2583) :    (∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card) ∧    (∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) ≤ 41 := by  classical  let S : Fin 3 → Finset (Fin 125) := fun i => Finset.univ.filter fun v => col v = i  let n : Fin 3 → ℕ := fun i => (S i).card  let cross : ℕ := ∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card  have hsizes : n 0 + n 1 + n 2 = 125 := by    have h := Finset.card_eq_sum_card_fiberwise (f := col) (s := (Finset.univ : Finset (Fin 125)))        (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 125 = n 0 + (n 1 + n 2) at h    omega  have hbound := graph_clique_partition_oriented_cross_degree_bound (Fin 125) (Fin 3) G D col hclique hsub hori  change (∑ i : Fin 3, n i * (n i - 1)) + 2 * cross ≤ 2 * G.edgeFinset.card at 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 hbound  have ht : n 0 * (n 0 - 1) + n 1 * (n 1 - 1) + n 2 * (n 2 - 1) + 2*cross ≤ 5166 := by omega  have h := in833_arith125 (n 0) (n 1) (n 2) cross hsizes ht  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