op_193_k3_m10_at_least_85_vertices
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.
Decidability of adjacency on C_10 + Unit.
By case analysis on whether the vertices are in C_10 or Unit.
intro a b cases a <;> cases b <;> dsimp [SimpleGraph.sum] <;> infer_instance
Modulus bound for indexing. automation
Decided by kernel computation.
verts ⟨i % 85, Nat.mod_lt _ (by decide)⟩
All 85 candidate sets are independent sets of size 3. automation
Verified by exhaustive evaluation.
decideNormalization specification holds for permutations of 6 colors. automation
Verified by finite case analysis.
decideModulus bound for valuation indexing. automation
Decided by computation.
fun n => (c ⟨(n / 6) % 85, Nat.mod_lt _ (by decide)⟩).val = n % 6
Clause soundness for SAT encoding of 6-coloring.
By case analysis on clause structure.
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
There are at least 85 stable triples.
The map verts embeds Fin 85 injectively into the 3-independent sets.
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
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.
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)