AFTD Auto-Formalizing Theoretical Domains

op_193_k3_m10_at_least_85_vertices

theoremverified

The stable triple graph of the ten-cycle plus an isolated vertex has at least 85 vertices.

Statement

theorem op_193_k3_m10_at_least_85_vertices :
    ∃ f : Fin 85 → {S : Finset (Fin 10 ⊕ Unit) //
      ((SimpleGraph.cycleGraph 10).sum (⊥ : SimpleGraph Unit)).IsNIndepSet 3 S},
      Function.Injective f
Source
Explicit finite enumeration for OP-193; experiment 23347.
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Used by 18
  • op_193_k3_m10_case_a5This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case a5).
  • op_193_k3_m10_case_b4x5This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b4x5).
  • op_193_k3_m10_case_a0This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case a0).
  • op_193_cycle_isolated_vertex_k3_m10The stable triple graph of the ten-cycle plus an isolated vertex has chromatic number seven.
  • op_193_k3_m10_case_b4x3This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b4x3).
  • op_193_k3_m10_case_b5x3This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b5x3).
  • op_193_k3_m10_case_a3This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case a3).
  • op_193_k3_m10_case_b5x0This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b5x0).
  • op_193_k3_m10_case_b4x0This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b4x0).
  • op_193_k3_m10_case_b3x1This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b3x1).
  • op_193_k3_m10_case_b2x1This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b2x1).
  • op_193_k3_m10_case_b5x4This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b5x4).
  • op_193_k3_m10_case_b2x4This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b2x4).
  • op_193_k3_m10_case_b3x4This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b3x4).
  • op_193_k3_m10_case_b3x0This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b3x0).
  • op_193_k3_m10_case_b3x5This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b3x5).
  • op_193_k3_m10_case_a4This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case a4).
  • op_193_k3_m10_case_b2x5This normalized partial six-coloring of the 85-vertex boundary graph is impossible (case b2x5).

The proof, explained

We construct an explicit list of 85 stable triples in C_10 + K_1 and verify by finite computation that they are distinct 3-element independent sets. We also set up and verify the soundness of a SAT encoding of proper 6-colorings on this graph.

  1. Decidability of adjacency on C_10 + Unit.

    By case analysis on whether the vertices are in C_10 or Unit.

    lines 6–7

      intro a b
      cases a <;> cases b <;> dsimp [SimpleGraph.sum] <;> infer_instance
  2. Modulus bound for indexing. automation

    Decided by kernel computation.

    line 96

      verts ⟨i % 85, Nat.mod_lt _ (by decide)⟩
  3. All 85 candidate sets are independent sets of size 3. automation

    Verified by exhaustive evaluation.

    line 100

      decide
  4. Normalization specification holds for permutations of 6 colors. automation

    Verified by finite case analysis.

    line 115

      decide
  5. Modulus bound for valuation indexing. automation

    Decided by computation.

    line 118

      fun n => (c ⟨(n / 6) % 85, Nat.mod_lt _ (by decide)⟩).val = n % 6
  6. Clause soundness for SAT encoding of 6-coloring.

    By case analysis on clause structure.

    lines 132–180

      rcases cl with _ | ⟨l, rest⟩
      · simp [clauseOK] at h
      rcases rest with _ | ⟨l2, rest⟩
      · cases l with
        | neg a => simp [clauseOK] at h
        | pos a =>
          have hm : a ∈ units := by simpa [clauseOK] using h
          simpa [Sat.Valuation.satisfies, Sat.Valuation.neg] using hunits a hm
      rcases rest with _ | ⟨l3, rest⟩
      · cases l <;> cases l2 <;> simp only [clauseOK, Bool.and_eq_true, beq_iff_eq, decide_eq_true_eq,
          Bool.false_eq_true] at h
        next a b =>
          rcases h with ⟨hab, hd⟩
          have hn := hproper ⟨(a/6)%85, Nat.mod_lt _ (by decide)⟩
            ⟨(b/6)%85, Nat.mod_lt _ (by decide)⟩ hd
          intro ha hb
          apply hn
          apply Fin.ext
          dsimp [valuation, Sat.Valuation.neg] at ha hb
          omega
      rcases rest with _ | ⟨l4, rest⟩
      · cases l <;> cases l2 <;> cases l3 <;> simp [clauseOK] at h
      rcases rest with _ | ⟨l5, rest⟩
      · cases l <;> cases l2 <;> cases l3 <;> cases l4 <;> simp [clauseOK] at h
      rcases rest with _ | ⟨l6, rest⟩
      · cases l <;> cases l2 <;> cases l3 <;> cases l4 <;> cases l5 <;> simp [clauseOK] at h
      rcases rest with _ | ⟨l7, rest⟩
      · cases l <;> cases l2 <;> cases l3 <;> cases l4 <;> cases l5 <;> cases l6 <;>
          simp only [clauseOK, Bool.and_eq_true, beq_iff_eq, Bool.false_eq_true] at h
        next a b d e f g =>
          rcases h with ⟨⟨⟨⟨⟨ha, hb⟩, hd⟩, he⟩, hf⟩, hg⟩
          subst b; subst d; subst e; subst f; subst g
          have hdiv1 : (a+1)/6 = a/6 := by omega
          have hdiv2 : (a+2)/6 = a/6 := by omega
          have hdiv3 : (a+3)/6 = a/6 := by omega
          have hdiv4 : (a+4)/6 = a/6 := by omega
          have hdiv5 : (a+5)/6 = a/6 := by omega
          have hmod1 : (a+1)%6 = 1 := by omega
          have hmod2 : (a+2)%6 = 2 := by omega
          have hmod3 : (a+3)%6 = 3 := by omega
          have hmod4 : (a+4)%6 = 4 := by omega
          have hmod5 : (a+5)%6 = 5 := by omega
          have bound := (c ⟨(a/6)%85, Nat.mod_lt _ (by decide)⟩).isLt
          simp only [Sat.Valuation.satisfies, Sat.Valuation.neg, valuation,
            hdiv1, hdiv2, hdiv3, hdiv4, hdiv5, ha, hmod1, hmod2, hmod3, hmod4, hmod5]
          omega
      cases l <;> cases l2 <;> cases l3 <;> cases l4 <;> cases l5 <;>
        cases l6 <;> cases l7 <;> simp [clauseOK] at h
    
  7. There are at least 85 stable triples.

    The map verts embeds Fin 85 injectively into the 3-independent sets.

    lines 187–190

      refine ⟨fun i => ⟨Inbox777M10.verts i, Inbox777M10.verts_valid i⟩, ?_⟩
      have hv : Function.Injective Inbox777M10.verts := by decide
      intro i j h
      exact hv (congrArg Subtype.val h)

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

Lean’s trace was cut to the first 400 of 573 tactics.

set_option maxRecDepth 100000set_option maxHeartbeats 40000000namespace Inbox777M10instance : DecidableRel (((SimpleGraph.cycleGraph 10).sum (⊥ : SimpleGraph Unit)).Adj) := by  intro a b  cases a <;> cases b <;> dsimp [SimpleGraph.sum] <;> infer_instancedef verts : Fin 85 → Finset (Fin 10 ⊕ Unit) := ![{Sum.inl (0 : Fin 10), Sum.inl (2 : Fin 10), Sum.inl (4 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (2 : Fin 10), Sum.inl (5 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (2 : Fin 10), Sum.inl (6 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (2 : Fin 10), Sum.inl (7 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (2 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (2 : Fin 10), Sum.inr ()},  {Sum.inl (0 : Fin 10), Sum.inl (3 : Fin 10), Sum.inl (5 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (3 : Fin 10), Sum.inl (6 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (3 : Fin 10), Sum.inl (7 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (3 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (3 : Fin 10), Sum.inr ()},  {Sum.inl (0 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (6 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (7 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (4 : Fin 10), Sum.inr ()},  {Sum.inl (0 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (7 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (5 : Fin 10), Sum.inr ()},  {Sum.inl (0 : Fin 10), Sum.inl (6 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (0 : Fin 10), Sum.inl (6 : Fin 10), Sum.inr ()},  {Sum.inl (0 : Fin 10), Sum.inl (7 : Fin 10), Sum.inr ()},  {Sum.inl (0 : Fin 10), Sum.inl (8 : Fin 10), Sum.inr ()},  {Sum.inl (1 : Fin 10), Sum.inl (3 : Fin 10), Sum.inl (5 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (3 : Fin 10), Sum.inl (6 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (3 : Fin 10), Sum.inl (7 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (3 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (3 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (3 : Fin 10), Sum.inr ()},  {Sum.inl (1 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (6 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (7 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (4 : Fin 10), Sum.inr ()},  {Sum.inl (1 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (7 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (5 : Fin 10), Sum.inr ()},  {Sum.inl (1 : Fin 10), Sum.inl (6 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (6 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (6 : Fin 10), Sum.inr ()},  {Sum.inl (1 : Fin 10), Sum.inl (7 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (1 : Fin 10), Sum.inl (7 : Fin 10), Sum.inr ()},  {Sum.inl (1 : Fin 10), Sum.inl (8 : Fin 10), Sum.inr ()},  {Sum.inl (1 : Fin 10), Sum.inl (9 : Fin 10), Sum.inr ()},  {Sum.inl (2 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (6 : Fin 10)},  {Sum.inl (2 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (7 : Fin 10)},  {Sum.inl (2 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (2 : Fin 10), Sum.inl (4 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (2 : Fin 10), Sum.inl (4 : Fin 10), Sum.inr ()},  {Sum.inl (2 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (7 : Fin 10)},  {Sum.inl (2 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (2 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (2 : Fin 10), Sum.inl (5 : Fin 10), Sum.inr ()},  {Sum.inl (2 : Fin 10), Sum.inl (6 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (2 : Fin 10), Sum.inl (6 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (2 : Fin 10), Sum.inl (6 : Fin 10), Sum.inr ()},  {Sum.inl (2 : Fin 10), Sum.inl (7 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (2 : Fin 10), Sum.inl (7 : Fin 10), Sum.inr ()},  {Sum.inl (2 : Fin 10), Sum.inl (8 : Fin 10), Sum.inr ()},  {Sum.inl (2 : Fin 10), Sum.inl (9 : Fin 10), Sum.inr ()},  {Sum.inl (3 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (7 : Fin 10)},  {Sum.inl (3 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (3 : Fin 10), Sum.inl (5 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (3 : Fin 10), Sum.inl (5 : Fin 10), Sum.inr ()},  {Sum.inl (3 : Fin 10), Sum.inl (6 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (3 : Fin 10), Sum.inl (6 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (3 : Fin 10), Sum.inl (6 : Fin 10), Sum.inr ()},  {Sum.inl (3 : Fin 10), Sum.inl (7 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (3 : Fin 10), Sum.inl (7 : Fin 10), Sum.inr ()},  {Sum.inl (3 : Fin 10), Sum.inl (8 : Fin 10), Sum.inr ()},  {Sum.inl (3 : Fin 10), Sum.inl (9 : Fin 10), Sum.inr ()},  {Sum.inl (4 : Fin 10), Sum.inl (6 : Fin 10), Sum.inl (8 : Fin 10)},  {Sum.inl (4 : Fin 10), Sum.inl (6 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (4 : Fin 10), Sum.inl (6 : Fin 10), Sum.inr ()},  {Sum.inl (4 : Fin 10), Sum.inl (7 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (4 : Fin 10), Sum.inl (7 : Fin 10), Sum.inr ()},  {Sum.inl (4 : Fin 10), Sum.inl (8 : Fin 10), Sum.inr ()},  {Sum.inl (4 : Fin 10), Sum.inl (9 : Fin 10), Sum.inr ()},  {Sum.inl (5 : Fin 10), Sum.inl (7 : Fin 10), Sum.inl (9 : Fin 10)},  {Sum.inl (5 : Fin 10), Sum.inl (7 : Fin 10), Sum.inr ()},  {Sum.inl (5 : Fin 10), Sum.inl (8 : Fin 10), Sum.inr ()},  {Sum.inl (5 : Fin 10), Sum.inl (9 : Fin 10), Sum.inr ()},  {Sum.inl (6 : Fin 10), Sum.inl (8 : Fin 10), Sum.inr ()},  {Sum.inl (6 : Fin 10), Sum.inl (9 : Fin 10), Sum.inr ()},  {Sum.inl (7 : Fin 10), Sum.inl (9 : Fin 10), Sum.inr ()}]def vertex (i : ℕ) : Finset (Fin 10 ⊕ Unit) :=  verts ⟨i % 85, Nat.mod_lt _ (by decide)⟩theorem verts_valid : ∀ i : Fin 85,    ((SimpleGraph.cycleGraph 10).sum (⊥ : SimpleGraph Unit)).IsNIndepSet 3 (verts i) := by  decidedef normalization (a b c d : Fin 6) : Equiv.Perm (Fin 6) :=  let e0 := Equiv.swap a 0  let e1 := Equiv.swap (e0 b) 1  let e2 := Equiv.swap (e1 (e0 c)) 2  let d' := e2 (e1 (e0 d))  let e3 := if d' = 2 then Equiv.refl _ else Equiv.swap d' 3  ((e0.trans e1).trans e2).trans e3theorem normalization_spec : ∀ a b c d : Fin 6,    a ≠ b → a ≠ c → b ≠ c → a ≠ d → b ≠ d →    normalization a b c d a = 0 ∧ normalization a b c d b = 1 ∧    normalization a b c d c = 2 ∧    (normalization a b c d d = 2 ∨ normalization a b c d d = 3) := by  decidedef valuation (c : Fin 85 → Fin 6) : Sat.Valuation :=  fun n => (c ⟨(n / 6) % 85, Nat.mod_lt _ (by decide)⟩).val = n % 6def clauseOK (units : List ℕ) : Sat.Clause → Bool  | [.pos a, .pos b, .pos c, .pos d, .pos e, .pos f] =>      a % 6 == 0 && b == a+1 && c == a+2 && d == a+3 && e == a+4 && f == a+5  | [.neg a, .neg b] =>      a % 6 == b % 6 && decide (Disjoint (vertex (a/6)) (vertex (b/6)))  | [.pos a] => units.contains a  | _ => falsetheorem clauseOK_sound (c : Fin 85 → Fin 6)    (hproper : ∀ i j, Disjoint (verts i) (verts j) → c i ≠ c j)    (units : List ℕ) (hunits : ∀ n ∈ units, valuation c n)    (cl : Sat.Clause) (h : clauseOK units cl = true) : (valuation c).satisfies cl := by  rcases cl with _ | ⟨l, rest⟩  · simp [clauseOK] at h  rcases rest with _ | ⟨l2, rest⟩  · cases l with    | neg a => simp [clauseOK] at h    | pos a =>      have hm : a ∈ units := by simpa [clauseOK] using h      simpa [Sat.Valuation.satisfies, Sat.Valuation.neg] using hunits a hm  rcases rest with _ | ⟨l3, rest⟩  · cases l <;> cases l2 <;> simp only [clauseOK, Bool.and_eq_true, beq_iff_eq, decide_eq_true_eq,      Bool.false_eq_true] at h    next a b =>      rcases h with ⟨hab, hd⟩      have hn := hproper ⟨(a/6)%85, Nat.mod_lt _ (by decide)⟩        ⟨(b/6)%85, Nat.mod_lt _ (by decide)⟩ hd      intro ha hb      apply hn      apply Fin.ext      dsimp [valuation, Sat.Valuation.neg] at ha hb      omega  rcases rest with _ | ⟨l4, rest⟩  · cases l <;> cases l2 <;> cases l3 <;> simp [clauseOK] at h  rcases rest with _ | ⟨l5, rest⟩  · cases l <;> cases l2 <;> cases l3 <;> cases l4 <;> simp [clauseOK] at h  rcases rest with _ | ⟨l6, rest⟩  · cases l <;> cases l2 <;> cases l3 <;> cases l4 <;> cases l5 <;> simp [clauseOK] at h  rcases rest with _ | ⟨l7, rest⟩  · cases l <;> cases l2 <;> cases l3 <;> cases l4 <;> cases l5 <;> cases l6 <;>      simp only [clauseOK, Bool.and_eq_true, beq_iff_eq, Bool.false_eq_true] at h    next a b d e f g =>      rcases h with ⟨⟨⟨⟨⟨ha, hb⟩, hd⟩, he⟩, hf⟩, hg⟩      subst b; subst d; subst e; subst f; subst g      have hdiv1 : (a+1)/6 = a/6 := by omega      have hdiv2 : (a+2)/6 = a/6 := by omega      have hdiv3 : (a+3)/6 = a/6 := by omega      have hdiv4 : (a+4)/6 = a/6 := by omega      have hdiv5 : (a+5)/6 = a/6 := by omega      have hmod1 : (a+1)%6 = 1 := by omega      have hmod2 : (a+2)%6 = 2 := by omega      have hmod3 : (a+3)%6 = 3 := by omega      have hmod4 : (a+4)%6 = 4 := by omega      have hmod5 : (a+5)%6 = 5 := by omega      have bound := (c ⟨(a/6)%85, Nat.mod_lt _ (by decide)⟩).isLt      simp only [Sat.Valuation.satisfies, Sat.Valuation.neg, valuation,        hdiv1, hdiv2, hdiv3, hdiv4, hdiv5, ha, hmod1, hmod2, hmod3, hmod4, hmod5]      omega  cases l <;> cases l2 <;> cases l3 <;> cases l4 <;> cases l5 <;>    cases l6 <;> cases l7 <;> simp [clauseOK] at hend Inbox777M10theorem op_193_k3_m10_at_least_85_vertices :    ∃ f : Fin 85 → {S : Finset (Fin 10 ⊕ Unit) //      ((SimpleGraph.cycleGraph 10).sum (⊥ : SimpleGraph Unit)).IsNIndepSet 3 S},      Function.Injective f := by  refine ⟨fun i => ⟨Inbox777M10.verts i, Inbox777M10.verts_valid i⟩, ?_⟩  have hv : Function.Injective Inbox777M10.verts := by decide  intro i j h  exact hv (congrArg Subtype.val h)
See it in the graphDiscuss this resultChallenge it