simple_graph_two_edge_stable_connected_family_exchange_trap_counterexample
There is a connected 18-vertex graph with 57 edges, packing number 14, all edge pairs avoidable by maximum packings, at least three triangles per edge, a connected triangle family, and a vertex of degree at least 17, together with a maximum packing containing a fully forced triangle such that every one-triangle replacement remains forced.
Statement
theorem simple_graph_two_edge_stable_connected_family_exchange_trap_counterexample : ∃ (G : SimpleGraph (Fin 18)) (E : Finset (Sym2 (Fin 18))) (P : Finset (Finset (Sym2 (Fin 18)))), let F := simple_graph_triangle_edge_family G (↑E : Set (Sym2 (Fin 18))) = G.edgeSet ∧ E.card = 57 ∧ G.Connected ∧ (∀ a ∈ F, ∀ b ∈ F, Relation.ReflTransGen (fun x y : Finset (Sym2 (Fin 18)) => x ∈ F ∧ y ∈ F ∧ ¬ Disjoint x y) a b) ∧ (∀ Q : Finset (Finset (Sym2 (Fin 18))), Q ⊆ F → (Q : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint → Q.card ≤ 14) ∧ P ⊆ F ∧ P.card = 14 ∧ (P : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint ∧ (∀ e ∈ G.edgeSet, ∀ f ∈ G.edgeSet, e ≠ f → ∃ Q : Finset (Finset (Sym2 (Fin 18))), Q ⊆ F ∧ Q.card = 14 ∧ (Q : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint ∧ e ∉ Q.biUnion id ∧ f ∉ Q.biUnion id) ∧ (∀ e ∈ G.edgeSet, 3 ≤ (F.filter (fun t => e ∈ t)).card) ∧ (∃ v : Fin 18, ∃ N : Finset (Fin 18), N.card = 17 ∧ ∀ w ∈ N, G.Adj v w) ∧ (∃ p ∈ P, p ⊆ ((F.filter (fun t => (t ∩ P.biUnion id).card = 1)).biUnion id)) ∧ ∀ Q : Finset (Finset (Sym2 (Fin 18))), Q ⊆ F → Q.card = 14 → (Q : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint → (P \ Q).card = 1 → ∃ q ∈ Q, q ⊆ ((F.filter (fun t => (t ∩ Q.biUnion id).card = 1)).biUnion id)
- Source
- Finite edge-sum construction audited by experiments 17301, 17325 and 17337; no claim of novelty.
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - Arena.Reachable.transReachability is transitive.
- Used by 1
- ten_vertex_exchange_family_eqThe 52 explicit triangle edge sets are exactly the triangle family of the ten-vertex graph.
The proof, explained
An explicit 18-vertex graph is constructed to show the existence of an exchange trap.
The adjacency relation is symmetric. automation
Unfolding the definition and linear integer arithmetic verifies symmetry.
uses
decide_eq_true_equnfold ts18_adjB at * simp only [decide_eq_true_eq] at * omega
The adjacency relation is irreflexive. automation
No vertex is adjacent to itself.
unfold ts18_adjB simp
Sorting three vertices preserves the triangle edge set.
A case split on the order of the three vertices shows that the unordered pairs remain the same.
uses
Sym2.eq_swapunfold ts18_sort3 ts18_enc split_ifs <;> ext e <;> simp only [Finset.mem_insert, Finset.mem_singleton] <;> constructor <;> rintro (h | h | h) <;> subst h <;> simp [Sym2.eq_swap]
Every triangle of the graph belongs to the canonical list. automation
Kernel computation verifies that all triples of mutually adjacent vertices appear in ts18_L.
decide +kernelEvery triple in the canonical list is a sorted triangle in the graph. automation
Kernel computation verifies that all elements of ts18_L are strictly sorted and form triangles.
decide +kernelThe edge set of a 3-element vertex set is the three pairwise edges.
Unfolding finite_vertex_set_edge_encoding and considering elements of Sym2 shows it equals {s(a, b), s(a, c), s(b, c)}.
unfold finite_vertex_set_edge_encoding ext e induction e using Sym2.ind with | _ x y => simp only [Finset.mem_filter, Finset.mem_sym2_iff, Sym2.mem_iff, Sym2.mk_isDiag_iff, Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff] constructor · rintro ⟨h, hxy⟩ have hx := h x (Or.inl rfl) have hy := h y (Or.inr rfl) rcases hx with rfl | rfl | rfl <;> rcases hy with rfl | rfl | rfl <;> simp_all · rintro (h | h | h) <;> rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ <;> aesop
The triangle edge family of the graph coincides with the canonical family.
Every triangle clique corresponds to an element of the canonical list, and vice versa.
uses
ts18_sort3_mem,ts18_enc_sort3,ts18_fvsee_triple,ts18_L_tri,SimpleGraph.is3Clique_triple_iff,ne_of_ltclassical unfold simple_graph_triangle_edge_family ts18_F ext t simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, List.mem_toFinset, List.mem_map] constructor · rintro ⟨s, hs, rfl⟩ obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := Finset.card_eq_three.mp hs.card_eq obtain ⟨h1, h2, h3⟩ := (SimpleGraph.is3Clique_triple_iff).mp hs exact ⟨_, ts18_sort3_mem a b c h1 h2 h3, by rw [ts18_enc_sort3, ts18_fvsee_triple a b c hab hac hbc]⟩ · rintro ⟨x, hx, rfl⟩ obtain ⟨l1, l2, h1, h2, h3⟩ := ts18_L_tri x hx refine ⟨{x.1, x.2.1, x.2.2}, (SimpleGraph.is3Clique_triple_iff).mpr ⟨h1, h2, h3⟩, ?_⟩ rw [ts18_fvsee_triple _ _ _ (ne_of_lt l1) (ne_of_lt (l1.trans l2)) (ne_of_lt l2)] rfl
- Unresolved check: no step explains line(s) 89, 92, 93, 94, 105, 109, 111, 112, 113, 117, 118, 119, 120, 121, 125, 126, 127, 128, 129, 133 -- every tactic of the proof has to belong to some step
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 558 tactics.
open scoped Sym2def ts18_adjB (a b : ℕ) : Bool := decide (a ≠ b ∧ ((a < 9 ∧ b < 9 ∧ (4 ≤ a ∨ 4 ≤ b)) ∨ (9 ≤ a ∧ 9 ≤ b ∧ (a - 9) / 3 = (b - 9) / 3) ∨ (9 ≤ a ∧ (b = 0 ∨ b = 7)) ∨ (9 ≤ b ∧ (a = 0 ∨ a = 7))))theorem ts18_adjB_symm (a b : ℕ) (h : ts18_adjB a b = true) : ts18_adjB b a = true := by unfold ts18_adjB at * simp only [decide_eq_true_eq] at * omegatheorem ts18_adjB_irrefl (a : ℕ) : ¬ ts18_adjB a a = true := by unfold ts18_adjB simpdef ts18_G : SimpleGraph (Fin 18) where Adj a b := ts18_adjB a.val b.val = true symm := ⟨fun a b h => ts18_adjB_symm _ _ h⟩ loopless := ⟨fun a h => ts18_adjB_irrefl _ h⟩instance ts18_G_dec : DecidableRel ts18_G.Adj := fun a b => inferInstanceAs (Decidable (ts18_adjB a.val b.val = true))def ts18_enc (x : Fin 18 × Fin 18 × Fin 18) : Finset (Sym2 (Fin 18)) := {s(x.1, x.2.1), s(x.1, x.2.2), s(x.2.1, x.2.2)}def ts18_L : List (Fin 18 × Fin 18 × Fin 18) := [(0, 4, 5), (0, 4, 6), (0, 4, 7), (0, 4, 8), (0, 5, 6), (0, 5, 7), (0, 5, 8), (0, 6, 7), (0, 6, 8), (0, 7, 8), (0, 7, 9), (0, 7, 10), (0, 7, 11), (0, 7, 12), (0, 7, 13), (0, 7, 14), (0, 7, 15), (0, 7, 16), (0, 7, 17), (0, 9, 10), (0, 9, 11), (0, 10, 11), (0, 12, 13), (0, 12, 14), (0, 13, 14), (0, 15, 16), (0, 15, 17), (0, 16, 17), (1, 4, 5), (1, 4, 6), (1, 4, 7), (1, 4, 8), (1, 5, 6), (1, 5, 7), (1, 5, 8), (1, 6, 7), (1, 6, 8), (1, 7, 8), (2, 4, 5), (2, 4, 6), (2, 4, 7), (2, 4, 8), (2, 5, 6), (2, 5, 7), (2, 5, 8), (2, 6, 7), (2, 6, 8), (2, 7, 8), (3, 4, 5), (3, 4, 6), (3, 4, 7), (3, 4, 8), (3, 5, 6), (3, 5, 7), (3, 5, 8), (3, 6, 7), (3, 6, 8), (3, 7, 8), (4, 5, 6), (4, 5, 7), (4, 5, 8), (4, 6, 7), (4, 6, 8), (4, 7, 8), (5, 6, 7), (5, 6, 8), (5, 7, 8), (6, 7, 8), (7, 9, 10), (7, 9, 11), (7, 10, 11), (7, 12, 13), (7, 12, 14), (7, 13, 14), (7, 15, 16), (7, 15, 17), (7, 16, 17), (9, 10, 11), (12, 13, 14), (15, 16, 17)]def ts18_F : Finset (Finset (Sym2 (Fin 18))) := (ts18_L.map ts18_enc).toFinsetdef ts18_sort3 (a b c : Fin 18) : Fin 18 × Fin 18 × Fin 18 := if a < b then (if b < c then (a, b, c) else if a < c then (a, c, b) else (c, a, b)) else (if a < c then (b, a, c) else if b < c then (b, c, a) else (c, b, a))theorem ts18_enc_sort3 (a b c : Fin 18) : ts18_enc (ts18_sort3 a b c) = {s(a, b), s(a, c), s(b, c)} := by unfold ts18_sort3 ts18_enc split_ifs <;> ext e <;> simp only [Finset.mem_insert, Finset.mem_singleton] <;> constructor <;> rintro (h | h | h) <;> subst h <;> simp [Sym2.eq_swap]set_option maxRecDepth 100000 intheorem ts18_sort3_mem : ∀ a b c : Fin 18, ts18_G.Adj a b → ts18_G.Adj a c → ts18_G.Adj b c → ts18_sort3 a b c ∈ ts18_L := by decide +kernelset_option maxRecDepth 100000 intheorem ts18_L_tri : ∀ x ∈ ts18_L, x.1 < x.2.1 ∧ x.2.1 < x.2.2 ∧ ts18_G.Adj x.1 x.2.1 ∧ ts18_G.Adj x.1 x.2.2 ∧ ts18_G.Adj x.2.1 x.2.2 := by decide +kerneltheorem ts18_fvsee_triple {V : Type*} [DecidableEq V] (a b c : V) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) : finite_vertex_set_edge_encoding ({a, b, c} : Finset V) = {s(a, b), s(a, c), s(b, c)} := by unfold finite_vertex_set_edge_encoding ext e induction e using Sym2.ind with | _ x y => simp only [Finset.mem_filter, Finset.mem_sym2_iff, Sym2.mem_iff, Sym2.mk_isDiag_iff, Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff] constructor · rintro ⟨h, hxy⟩ have hx := h x (Or.inl rfl) have hy := h y (Or.inr rfl) rcases hx with rfl | rfl | rfl <;> rcases hy with rfl | rfl | rfl <;> simp_all · rintro (h | h | h) <;> rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ <;> aesoptheorem ts18_F_eq : simple_graph_triangle_edge_family ts18_G = ts18_F := by classical unfold simple_graph_triangle_edge_family ts18_F ext t simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, List.mem_toFinset, List.mem_map] constructor · rintro ⟨s, hs, rfl⟩ obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := Finset.card_eq_three.mp hs.card_eq obtain ⟨h1, h2, h3⟩ := (SimpleGraph.is3Clique_triple_iff).mp hs exact ⟨_, ts18_sort3_mem a b c h1 h2 h3, by rw [ts18_enc_sort3, ts18_fvsee_triple a b c hab hac hbc]⟩ · rintro ⟨x, hx, rfl⟩ obtain ⟨l1, l2, h1, h2, h3⟩ := ts18_L_tri x hx refine ⟨{x.1, x.2.1, x.2.2}, (SimpleGraph.is3Clique_triple_iff).mpr ⟨h1, h2, h3⟩, ?_⟩ rw [ts18_fvsee_triple _ _ _ (ne_of_lt l1) (ne_of_lt (l1.trans l2)) (ne_of_lt l2)] rflabbrev T18 := Fin 18 × Fin 18 × Fin 18def ts18_sc (a b : Fin 18) : ℕ := if a.val ≤ b.val then a.val * 18 + b.val else b.val * 18 + a.valtheorem ts18_sc_comm (a b : Fin 18) : ts18_sc a b = ts18_sc b a := by unfold ts18_sc; split_ifs <;> omegatheorem ts18_sc_eq_iff (a b c d : Fin 18) : ts18_sc a b = ts18_sc c d ↔ s(a, b) = s(c, d) := by have := a.isLt; have := b.isLt; have := c.isLt; have := d.isLt rw [Sym2.eq_iff]; simp only [Fin.ext_iff]; unfold ts18_sc constructor <;> intro h <;> split_ifs at * <;> omegadef ts18_scS : Sym2 (Fin 18) → ℕ := Sym2.lift ⟨ts18_sc, ts18_sc_comm⟩theorem ts18_scS_mk (a b : Fin 18) : ts18_scS s(a, b) = ts18_sc a b := rfldef ts18_msk (x : T18) : ℕ := 2 ^ ts18_sc x.1 x.2.1 ||| 2 ^ ts18_sc x.1 x.2.2 ||| 2 ^ ts18_sc x.2.1 x.2.2theorem ts18_tb_msk (x : T18) (k : ℕ) : (ts18_msk x).testBit k = true ↔ (ts18_sc x.1 x.2.1 = k ∨ ts18_sc x.1 x.2.2 = k ∨ ts18_sc x.2.1 x.2.2 = k) := by simp [ts18_msk, Nat.testBit_or, Nat.testBit_two_pow, or_assoc]theorem ts18_mem_enc (x : T18) (e : Sym2 (Fin 18)) : e ∈ ts18_enc x ↔ (ts18_msk x).testBit (ts18_scS e) = true := by induction e using Sym2.ind with | _ a b => rw [ts18_tb_msk, ts18_scS_mk, ts18_sc_eq_iff, ts18_sc_eq_iff, ts18_sc_eq_iff] simp only [ts18_enc, Finset.mem_insert, Finset.mem_singleton] constructor <;> rintro (h | h | h) <;> simp [h]theorem ts18_mem_enc_of_tb (x : T18) (i : ℕ) (h : (ts18_msk x).testBit i = true) : ∃ e ∈ ts18_enc x, ts18_scS e = i := by rw [ts18_tb_msk] at h rcases h with h | h | h · exact ⟨s(x.1, x.2.1), by simp [ts18_enc], h⟩ · exact ⟨s(x.1, x.2.2), by simp [ts18_enc], h⟩ · exact ⟨s(x.2.1, x.2.2), by simp [ts18_enc], h⟩theorem ts18_not_disj (x y : T18) (h : ts18_msk x &&& ts18_msk y ≠ 0) : ¬ Disjoint (ts18_enc x) (ts18_enc y) := by obtain ⟨k, hk⟩ := Nat.exists_testBit_of_ne_zero h rw [Nat.testBit_land, Bool.and_eq_true] at hk obtain ⟨e, he, rfl⟩ := ts18_mem_enc_of_tb x k hk.1 rw [Finset.not_disjoint_iff] exact ⟨e, he, (ts18_mem_enc y e).mpr hk.2⟩theorem ts18_disj (x y : T18) (h : ts18_msk x &&& ts18_msk y = 0) : Disjoint (ts18_enc x) (ts18_enc y) := by rw [Finset.disjoint_left] intro e h1 h2 rw [ts18_mem_enc] at h1 h2 have : (ts18_msk x &&& ts18_msk y).testBit (ts18_scS e) = true := by rw [Nat.testBit_land, h1, h2]; rfl rw [h, Nat.zero_testBit] at this exact absurd this (by decide)theorem ts18_land_of_disj (x y : T18) (h : Disjoint (ts18_enc x) (ts18_enc y)) : ts18_msk x &&& ts18_msk y = 0 := by by_contra h' exact ts18_not_disj x y h' htheorem ts18_enc_msk (x y : T18) (h : ts18_enc x = ts18_enc y) : ts18_msk x = ts18_msk y := by apply Nat.eq_of_testBit_eq intro i apply Bool.eq_iff_iff.mpr constructor · intro hi obtain ⟨e, he, rfl⟩ := ts18_mem_enc_of_tb x i hi rw [h] at he; exact (ts18_mem_enc y e).mp he · intro hi obtain ⟨e, he, rfl⟩ := ts18_mem_enc_of_tb y i hi rw [← h] at he; exact (ts18_mem_enc x e).mp hetheorem ts18_msk_ne (x : T18) : ts18_msk x ≠ 0 := by intro h have := (ts18_tb_msk x (ts18_sc x.1 x.2.1)).mpr (Or.inl rfl) rw [h, Nat.zero_testBit] at this exact absurd this (by decide)theorem ts18_enc_mem (x : T18) : s(x.1, x.2.1) ∈ ts18_enc x := by simp [ts18_enc]def ts18_um : List T18 → ℕ | [] => 0 | x :: S => ts18_msk x ||| ts18_um Sdef ts18_pk (S : List T18) : Finset (Finset (Sym2 (Fin 18))) := (S.map ts18_enc).toFinsettheorem ts18_mem_U (S : List T18) (e : Sym2 (Fin 18)) : e ∈ (ts18_pk S).biUnion id ↔ (ts18_um S).testBit (ts18_scS e) = true := by induction S with | nil => simp [ts18_pk, ts18_um] | cons x S ih => simp only [ts18_pk] at ih ⊢ simp only [List.map_cons, List.toFinset_cons, Finset.biUnion_insert, Finset.mem_union, id, ih, ts18_mem_enc, ts18_um, Nat.testBit_or, Bool.or_eq_true]theorem ts18_tb_um (S : List T18) (y : T18) (hy : y ∈ S) (i : ℕ) (h : (ts18_msk y).testBit i = true) : (ts18_um S).testBit i = true := by induction S with | nil => simp at hy | cons z S ih => simp only [ts18_um, Nat.testBit_or, Bool.or_eq_true] rcases List.mem_cons.mp hy with rfl | hy · exact Or.inl h · exact Or.inr (ih hy)theorem ts18_land_um (x : T18) (S : List T18) (h : ts18_msk x &&& ts18_um S = 0) (y : T18) (hy : y ∈ S) : ts18_msk x &&& ts18_msk y = 0 := by apply Nat.eq_of_testBit_eq intro i rw [Nat.testBit_land, Nat.zero_testBit] cases h1 : (ts18_msk x).testBit i · rfl cases h2 : (ts18_msk y).testBit i · rfl have := congrArg (fun m => m.testBit i) h simp only [Nat.testBit_land, h1, ts18_tb_um S y hy i h2, Nat.zero_testBit] at this exact absurd this (by decide)def ts18_pd : List T18 → Bool | [] => true | x :: S => (ts18_msk x &&& ts18_um S == 0) && ts18_pd Stheorem ts18_pd_forall (S : List T18) (h : ts18_pd S = true) : ∀ x ∈ S, ∀ y ∈ S, x ≠ y → ts18_msk x &&& ts18_msk y = 0 := by induction S with | nil => simp | cons z S ih => simp only [ts18_pd, Bool.and_eq_true, beq_iff_eq] at h intro x hx y hy hxy rcases List.mem_cons.mp hx with hx' | hx' <;> rcases List.mem_cons.mp hy with hy' | hy' · exact absurd (hx'.trans hy'.symm) hxy · rw [hx']; exact ts18_land_um z S h.1 y hy' · rw [hy', Nat.land_comm]; exact ts18_land_um z S h.1 x hx' · exact ih h.2 x hx' y hy' hxytheorem ts18_pd_nodup (S : List T18) (h : ts18_pd S = true) : S.Nodup := by induction S with | nil => exact List.nodup_nil | cons z S ih => simp only [ts18_pd, Bool.and_eq_true, beq_iff_eq] at h refine List.nodup_cons.mpr ⟨fun hz => ?_, ih h.2⟩ have := ts18_land_um z S h.1 z hz rw [Nat.and_self] at this exact ts18_msk_ne z thistheorem ts18_pd_inj (S : List T18) (h : ts18_pd S = true) : ∀ x ∈ S, ∀ y ∈ S, ts18_enc x = ts18_enc y → x = y := by intro x hx y hy he by_contra hne have hd := ts18_disj x y (ts18_pd_forall S h x hx y hy hne) rw [he] at hd exact Finset.disjoint_left.mp hd (ts18_enc_mem y) (ts18_enc_mem y)theorem ts18_pk_card (S : List T18) (h : ts18_pd S = true) : (ts18_pk S).card = S.length := by unfold ts18_pk rw [List.toFinset_card_of_nodup (List.Nodup.map_on (ts18_pd_inj S h) (ts18_pd_nodup S h)), List.length_map]theorem ts18_pk_disj (S : List T18) (h : ts18_pd S = true) : (ts18_pk S : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint := by intro t ht t' ht' hne simp only [ts18_pk, Finset.mem_coe, List.mem_toFinset, List.mem_map] at ht ht' obtain ⟨x, hx, rfl⟩ := ht obtain ⟨y, hy, rfl⟩ := ht' exact ts18_disj x y (ts18_pd_forall S h x hx y hy (fun e => hne (by rw [e])))theorem ts18_pk_sub (S : List T18) (h : ∀ x ∈ S, x ∈ ts18_L) : ts18_pk S ⊆ ts18_F := by intro t ht simp only [ts18_pk, ts18_F, List.mem_toFinset, List.mem_map] at ht ⊢ obtain ⟨x, hx, rfl⟩ := ht exact ⟨x, h x hx, rfl⟩theorem ts18_mem_F (t : Finset (Sym2 (Fin 18))) : t ∈ ts18_F ↔ ∃ x ∈ ts18_L, ts18_enc x = t := by simp [ts18_F]theorem ts18_card_inter (a b c : Fin 18) (hab : a < b) (hbc : b < c) (U : Finset (Sym2 (Fin 18))) : (ts18_enc (a, b, c) ∩ U).card = (if s(a, b) ∈ U then 1 else 0) + (if s(a, c) ∈ U then 1 else 0) + (if s(b, c) ∈ U then 1 else 0) := by have hab' := Fin.ne_of_lt hab have hbc' := Fin.ne_of_lt hbc have hac' := Fin.ne_of_lt (hab.trans hbc) have e12 : s(a, b) ≠ s(a, c) := by rw [Ne, Sym2.eq_iff]; rintro (⟨-, h⟩ | ⟨h, -⟩) · exact hbc' h · exact hac' h have e13 : s(a, b) ≠ s(b, c) := by rw [Ne, Sym2.eq_iff]; rintro (⟨h, -⟩ | ⟨h, -⟩) · exact hab' h · exact hac' h have e23 : s(a, c) ≠ s(b, c) := by rw [Ne, Sym2.eq_iff]; rintro (⟨h, -⟩ | ⟨-, h⟩) · exact hab' h · exact hbc' h.symm unfold ts18_enc dsimp only split_ifs with h1 h2 h3 h3 h2 h3 h3 <;> simp [Finset.insert_inter_of_mem, Finset.insert_inter_of_notMem, h1, h2, h3, Finset.card_insert_of_notMem, e12, e13, e23]-- class 0: 10-- class 1: 10-- class 2: 10-- class 3: 10-- class 5: 10-- class 6: 10-- class 7: 10def ts18_C : ℕ → List T18 | 0 => [(0, 4, 5), (0, 4, 6), (0, 4, 7), (0, 4, 8), (0, 5, 6), (0, 5, 7), (0, 5, 8), (0, 6, 7), (0, 6, 8), (0, 7, 8)] | 1 => [(1, 4, 5), (1, 4, 6), (1, 4, 7), (1, 4, 8), (1, 5, 6), (1, 5, 7), (1, 5, 8), (1, 6, 7), (1, 6, 8), (1, 7, 8)] | 2 => [(2, 4, 5), (2, 4, 6), (2, 4, 7), (2, 4, 8), (2, 5, 6), (2, 5, 7), (2, 5, 8), (2, 6, 7), (2, 6, 8), (2, 7, 8)] | 3 => [(3, 4, 5), (3, 4, 6), (3, 4, 7), (3, 4, 8), (3, 5, 6), (3, 5, 7), (3, 5, 8), (3, 6, 7), (3, 6, 8), (3, 7, 8)] | 5 => [(0, 7, 9), (0, 7, 10), (0, 7, 11), (0, 9, 10), (0, 9, 11), (0, 10, 11), (7, 9, 10), (7, 9, 11), (7, 10, 11), (9, 10, 11)] | 6 => [(0, 7, 12), (0, 7, 13), (0, 7, 14), (0, 12, 13), (0, 12, 14), (0, 13, 14), (7, 12, 13), (7, 12, 14), (7, 13, 14), (12, 13, 14)] | _ => [(0, 7, 15), (0, 7, 16), (0, 7, 17), (0, 15, 16), (0, 15, 17), (0, 16, 17), (7, 15, 16), (7, 15, 17), (7, 16, 17), (15, 16, 17)]def ts18_Wm : List (List T18 × ℕ) := [ ([(0, 4, 6), (0, 7, 14), (0, 10, 11), (0, 15, 16), (1, 4, 7), (1, 5, 6), (2, 4, 5), (2, 6, 8), (3, 4, 8), (3, 6, 7), (5, 7, 8), (7, 9, 10), (7, 15, 17), (12, 13, 14)], 372992427307792297053274832548088931377569810965452365287073959378595480519683575237840), ([(0, 4, 7), (0, 5, 8), (0, 9, 11), (0, 12, 13), (0, 16, 17), (1, 4, 6), (1, 7, 8), (2, 4, 8), (2, 5, 7), (3, 4, 5), (3, 6, 8), (7, 10, 11), (7, 13, 14), (7, 15, 16)], 65185275573512657659564512176221878191217443560781717301228091349604214767223660630327376816), ([(0, 5, 8), (0, 6, 7), (0, 9, 10), (0, 12, 14), (0, 15, 17), (1, 5, 7), (1, 6, 8), (2, 4, 5), (2, 7, 8), (3, 4, 7), (3, 5, 6), (7, 9, 11), (7, 12, 13), (7, 16, 17)], 65185399904321759653913927875104221025505285790971245179059777766614548289996987077283207136), ([(0, 4, 6), (0, 5, 8), (0, 9, 11), (0, 13, 14), (0, 15, 17), (1, 4, 5), (1, 6, 7), (2, 4, 7), (2, 6, 8), (3, 4, 8), (3, 5, 7), (7, 10, 11), (7, 12, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310193818614785231718065720377834125155036016), ([(0, 4, 6), (0, 5, 7), (0, 9, 10), (0, 13, 14), (0, 16, 17), (1, 4, 8), (1, 5, 6), (2, 4, 5), (2, 6, 8), (3, 5, 8), (3, 6, 7), (7, 9, 11), (7, 12, 13), (7, 15, 16)], 65185275573512657659564512176221875052672562178146732080082250549796904830976174291144632048), ([(0, 4, 6), (0, 5, 8), (0, 7, 12), (0, 10, 11), (0, 16, 17), (1, 4, 5), (1, 7, 8), (2, 4, 8), (2, 6, 7), (3, 4, 7), (3, 5, 6), (7, 9, 10), (7, 13, 14), (7, 15, 16)], 65185275573512657659563649457928529370738027905592643075366863614428062995806088572382158320), ([(0, 4, 8), (0, 5, 6), (0, 7, 13), (0, 9, 10), (0, 12, 14), (0, 15, 16), (1, 4, 6), (1, 7, 8), (2, 5, 7), (2, 6, 8), (3, 4, 7), (3, 5, 8), (7, 9, 11), (7, 15, 17)], 372992427307339983341973272807756594892963213063825116005370900851652720569420932577264), ([(0, 5, 8), (0, 6, 7), (0, 9, 11), (0, 12, 13), (0, 15, 16), (1, 4, 5), (1, 6, 8), (2, 4, 6), (2, 7, 8), (3, 4, 8), (3, 5, 6), (7, 10, 11), (7, 12, 14), (7, 15, 17)], 372992427307339984204691566159715613203690330811896454996289775358149877248620520127456), ([(0, 4, 5), (0, 6, 8), (0, 10, 11), (0, 12, 13), (0, 15, 17), (1, 5, 8), (1, 6, 7), (2, 4, 6), (2, 5, 7), (3, 5, 6), (3, 7, 8), (7, 9, 10), (7, 13, 14), (7, 16, 17)], 65185399904321760106225051021783914896421482364121141370866578969926365868933151459889036656), ([(0, 4, 7), (0, 5, 6), (0, 9, 11), (0, 12, 14), (0, 15, 17), (1, 4, 8), (1, 5, 7), (2, 4, 5), (2, 6, 8), (3, 4, 6), (3, 7, 8), (7, 10, 11), (7, 12, 13), (7, 16, 17)], 65185399904321759653913927875104224164050167173605163274702954265716856241100094685659192048), ([(0, 4, 7), (0, 6, 8), (0, 9, 11), (0, 13, 14), (0, 16, 17), (1, 5, 8), (1, 6, 7), (2, 5, 6), (2, 7, 8), (3, 4, 6), (3, 5, 7), (7, 10, 11), (7, 12, 14), (7, 15, 16)], 65185275573512657659565374894515227011690872905264153480307459151334230661384721210888383440), ([(0, 4, 8), (0, 5, 7), (0, 9, 10), (0, 13, 14), (0, 15, 16), (1, 4, 7), (1, 5, 6), (2, 4, 5), (2, 6, 7), (3, 4, 6), (3, 7, 8), (7, 9, 11), (7, 12, 13), (7, 15, 17)], 372992427307792295327838245847309445623808917767697872514931643592567348673510371354544), ([(0, 4, 6), (0, 7, 8), (0, 10, 11), (0, 12, 14), (0, 15, 17), (1, 4, 8), (1, 6, 7), (2, 4, 7), (2, 5, 6), (3, 4, 5), (3, 6, 8), (7, 9, 10), (7, 12, 13), (7, 16, 17)], 65185399904321759653913927875104224164044180862898525227962632548684034000772507917520920016), ([(0, 4, 7), (0, 5, 8), (0, 10, 11), (0, 12, 14), (0, 16, 17), (1, 4, 8), (1, 5, 6), (2, 5, 7), (2, 6, 8), (3, 4, 5), (3, 6, 7), (7, 9, 10), (7, 13, 14), (7, 15, 17)], 65185399904321760106225913740077263716894911708601116627826836090595044699444669233901034928), ([(0, 4, 8), (0, 6, 7), (0, 9, 10), (0, 12, 13), (0, 15, 16), (1, 4, 7), (1, 5, 8), (2, 4, 5), (2, 7, 8), (3, 5, 7), (3, 6, 8), (7, 9, 11), (7, 12, 14), (7, 15, 17)], 372992427307339984204691566156577068322307696893800770281178122097429735137506760964048), ([(0, 4, 8), (0, 5, 6), (0, 7, 15), (0, 10, 11), (0, 12, 13), (1, 4, 6), (1, 5, 7), (2, 4, 7), (2, 5, 8), (3, 4, 5), (3, 7, 8), (7, 9, 10), (7, 12, 14), (7, 16, 17)], 65185151242703554760592850183980150753624130634826611045416568077325591600658331305368403440), ([(0, 5, 8), (0, 10, 11), (0, 12, 14), (0, 16, 17), (1, 5, 7), (1, 6, 8), (2, 4, 8), (2, 5, 6), (3, 4, 5), (3, 7, 8), (4, 6, 7), (7, 9, 11), (7, 12, 13), (7, 15, 16)], 65185275573512657207253389029542187458840142059559057602222717977702162422432980742938254624), ([(0, 4, 8), (0, 5, 6), (0, 9, 10), (0, 12, 13), (0, 15, 16), (1, 5, 8), (1, 6, 7), (2, 4, 6), (2, 7, 8), (3, 4, 7), (3, 6, 8), (7, 9, 11), (7, 13, 14), (7, 15, 17)], 372992427307792295327838245847309445623808918813045386772962796083209000430595251222384), ([(0, 5, 8), (0, 6, 7), (0, 9, 10), (0, 13, 14), (0, 15, 17), (1, 4, 5), (1, 7, 8), (2, 4, 7), (2, 5, 6), (3, 5, 7), (4, 6, 8), (7, 10, 11), (7, 12, 14), (7, 15, 16)], 372992427307792296190556539199268457948225323084755456722710909029793563840264387356640), ([(0, 4, 7), (0, 5, 6), (0, 9, 11), (0, 12, 14), (0, 16, 17), (1, 4, 5), (1, 6, 7), (2, 4, 6), (2, 7, 8), (3, 5, 7), (3, 6, 8), (7, 9, 10), (7, 13, 14), (7, 15, 16)], 65185275573512657659565374894515223873145991522630496721480538924279946128197822007394654960), ([(0, 4, 8), (0, 5, 6), (0, 7, 16), (0, 9, 10), (0, 13, 14), (1, 4, 6), (1, 7, 8), (2, 5, 8), (2, 6, 7), (3, 6, 8), (4, 5, 7), (7, 9, 11), (7, 12, 14), (15, 16, 17)], 65185524235130862552886452585639297283566041750702846465331647864549619851458401972311386096), ([(0, 5, 8), (0, 6, 7), (0, 9, 11), (0, 12, 13), (0, 15, 16), (1, 4, 8), (1, 5, 7), (2, 4, 7), (2, 5, 6), (3, 4, 5), (3, 7, 8), (7, 10, 11), (7, 13, 14), (7, 16, 17)], 65185275573512657659564512176221878191217443560790080080636002037641872324510002041967459296), ([(0, 4, 8), (0, 6, 7), (0, 10, 11), (0, 12, 13), (0, 15, 17), (1, 4, 6), (1, 5, 7), (2, 5, 6), (2, 7, 8), (3, 4, 7), (3, 5, 8), (7, 9, 10), (7, 13, 14), (7, 16, 17)], 65185399904321760106225051021783914896421482364121141370783502220191470899013958997893103056), ([(0, 4, 8), (0, 5, 7), (0, 10, 11), (0, 12, 14), (0, 15, 17), (1, 4, 5), (1, 6, 8), (2, 5, 8), (2, 6, 7), (3, 4, 6), (3, 7, 8), (7, 9, 10), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716894911708603925999048135279320933578519609927541120432), ([(0, 4, 7), (0, 5, 6), (0, 9, 11), (0, 12, 13), (0, 15, 16), (1, 5, 7), (1, 6, 8), (2, 4, 5), (2, 6, 7), (3, 4, 6), (3, 5, 8), (7, 10, 11), (7, 12, 14), (7, 15, 17)], 372992427307339984204691566159715613203690330790118383513508169417059521225466721712880), ([(0, 4, 8), (0, 5, 6), (0, 7, 11), (0, 9, 10), (0, 12, 13), (0, 15, 16), (1, 4, 6), (1, 7, 8), (2, 5, 7), (2, 6, 8), (3, 4, 5), (3, 6, 7), (7, 12, 14), (7, 16, 17)], 65185275573512657207253389029542184320283288055521184427568980949408819526179345435749105648), ([(0, 4, 8), (0, 5, 6), (0, 7, 9), (0, 13, 14), (0, 16, 17), (1, 5, 8), (1, 6, 7), (2, 4, 5), (2, 7, 8), (3, 4, 7), (3, 6, 8), (7, 12, 14), (7, 15, 16), (9, 10, 11)], 65185275573512657659565374894515227011696859215970443077945591885337152782483185159958127600), ([(0, 4, 5), (0, 7, 17), (0, 10, 11), (0, 13, 14), (0, 15, 16), (1, 4, 7), (1, 5, 8), (2, 4, 8), (2, 5, 6), (3, 4, 6), (3, 5, 7), (6, 7, 8), (7, 9, 11), (7, 12, 14)], 124330809102898975112865415125858043884307956937496957815219764757763339335153104448688), ([(0, 4, 6), (0, 5, 8), (0, 10, 11), (0, 13, 14), (0, 16, 17), (1, 4, 8), (1, 5, 7), (2, 4, 7), (2, 6, 8), (3, 5, 6), (3, 7, 8), (7, 9, 11), (7, 12, 13), (7, 15, 16)], 65185275573512657659564512176221878191217443560780628397653944425749143369034379569024691568), ([(0, 4, 5), (0, 6, 8), (0, 7, 10), (0, 12, 13), (0, 15, 16), (1, 4, 6), (1, 5, 8), (2, 4, 8), (2, 5, 7), (3, 4, 7), (3, 5, 6), (7, 9, 11), (7, 13, 14), (7, 16, 17)], 65185275573512657659564512176221875052666575867449719940854311748738906778331551751345386992), ([(0, 4, 8), (0, 5, 6), (0, 7, 12), (0, 9, 11), (0, 16, 17), (1, 4, 7), (1, 6, 8), (2, 4, 6), (3, 4, 5), (3, 6, 7), (5, 7, 8), (7, 10, 11), (7, 15, 16), (12, 13, 14)], 65185275573512657659566237612808575832164302249745544311914107376010766018859114973848869872), ([(0, 5, 8), (0, 6, 7), (0, 10, 11), (0, 12, 13), (0, 16, 17), (1, 4, 6), (1, 5, 7), (2, 5, 6), (3, 4, 5), (3, 6, 8), (4, 7, 8), (7, 9, 10), (7, 12, 14), (7, 15, 16)], 65185275573512657207253389029542187458834155748853160009871278006353882893328047575509712352), ([(0, 5, 6), (0, 10, 11), (0, 12, 13), (0, 15, 17), (1, 4, 6), (1, 5, 8), (2, 5, 7), (2, 6, 8), (3, 4, 5), (3, 6, 7), (4, 7, 8), (7, 9, 11), (7, 13, 14), (7, 15, 16)], 372992427307792295327838245850447990505191547112398628889776225577575582382886289063008), ([(0, 4, 8), (0, 5, 7), (0, 10, 11), (0, 12, 14), (0, 15, 17), (1, 4, 7), (1, 6, 8), (2, 4, 6), (2, 7, 8), (3, 5, 8), (3, 6, 7), (7, 9, 11), (7, 12, 13), (7, 16, 17)], 65185399904321759653913927875104224164050167173605119718601526998146147977532385315176766896), ([(0, 5, 7), (0, 6, 8), (0, 9, 10), (0, 12, 13), (0, 15, 16), (1, 4, 8), (1, 6, 7), (2, 4, 7), (2, 5, 6), (3, 4, 6), (3, 5, 8), (7, 9, 11), (7, 13, 14), (7, 16, 17)], 65185275573512657659564512176221875052672562178156140206962880656435193557287181875465533408), ([(0, 4, 6), (0, 5, 8), (0, 7, 14), (0, 9, 10), (0, 15, 17), (1, 4, 5), (2, 4, 7), (2, 5, 6), (3, 4, 8), (3, 5, 7), (6, 7, 8), (7, 10, 11), (7, 12, 13), (7, 15, 16)], 372992427307339982479254979462074660358690653856973726742804102228212209194073724209136), ([(0, 4, 8), (0, 5, 6), (0, 7, 10), (0, 12, 13), (0, 16, 17), (1, 4, 5), (1, 7, 8), (2, 5, 7), (2, 6, 8), (3, 4, 6), (3, 5, 8), (7, 12, 14), (7, 15, 16), (9, 10, 11)], 65185275573512657207253389029542187458846128370266131210392698337511288287937292811678987760), ([(0, 4, 6), (0, 5, 8), (0, 7, 9), (0, 10, 11), (0, 12, 14), (0, 15, 16), (1, 4, 5), (1, 6, 7), (2, 4, 8), (2, 5, 6), (3, 4, 7), (3, 6, 8), (7, 13, 14), (7, 15, 17)], 372992427307792296190556539199268451961914622261453760807615471591084705580576732733424), ([(0, 5, 6), (0, 7, 8), (0, 9, 11), (0, 13, 14), (0, 16, 17), (1, 4, 8), (1, 5, 7), (2, 4, 6), (2, 5, 8), (3, 4, 7), (3, 6, 8), (7, 10, 11), (7, 12, 14), (7, 15, 16)], 65185275573512657659565374894515227011690872905264153480265920776467160970211309438959315936), ([(0, 4, 6), (0, 5, 8), (0, 7, 16), (0, 9, 11), (0, 12, 14), (0, 15, 17), (1, 5, 6), (2, 5, 7), (2, 6, 8), (3, 4, 5), (3, 6, 7), (4, 7, 8), (7, 10, 11), (7, 13, 14)], 248661618205345635651710977162563253909421989453652874235601083506931193195289544743920), ([(0, 4, 5), (0, 6, 8), (0, 7, 15), (0, 9, 10), (0, 12, 14), (1, 5, 6), (1, 7, 8), (2, 4, 6), (2, 5, 7), (3, 4, 7), (3, 5, 8), (7, 10, 11), (7, 13, 14), (15, 16, 17)], 65185524235130862552886452585639300422104936822627818038615773100580946410072520697311188976), ([(0, 4, 6), (0, 5, 8), (0, 10, 11), (0, 13, 14), (0, 16, 17), (1, 4, 5), (1, 6, 7), (2, 4, 8), (2, 5, 7), (3, 5, 6), (3, 7, 8), (7, 9, 11), (7, 12, 13), (7, 15, 17)], 65185399904321760106225051021783914896427468674823902920841398822660018620266193137097207152), ([(0, 4, 8), (0, 6, 7), (0, 9, 11), (0, 13, 14), (0, 16, 17), (1, 4, 5), (1, 6, 8), (2, 4, 6), (2, 5, 7), (3, 4, 7), (3, 5, 6), (7, 10, 11), (7, 12, 14), (7, 15, 17)], 65185399904321760106225913740077263716900898019307406225464968666140886209341960392385194960), ([(0, 4, 7), (0, 5, 6), (0, 9, 11), (0, 13, 14), (0, 16, 17), (1, 4, 6), (1, 7, 8), (2, 4, 8), (2, 5, 7), (3, 5, 8), (3, 6, 7), (7, 10, 11), (7, 12, 14), (7, 15, 17)], 65185399904321760106225913740077263716900898019307428003453375173378489568913715466252544752), ([(0, 5, 7), (0, 6, 8), (0, 10, 11), (0, 12, 14), (0, 16, 17), (1, 4, 7), (1, 5, 6), (2, 4, 5), (2, 7, 8), (3, 4, 8), (3, 6, 7), (7, 9, 11), (7, 13, 14), (7, 15, 17)], 65185399904321760106225913740077263716900898019307732896537212767065508821545429692804455904), ([(0, 4, 5), (0, 6, 7), (0, 9, 10), (0, 12, 14), (0, 16, 17), (1, 4, 6), (1, 7, 8), (2, 4, 8), (2, 5, 6), (3, 4, 7), (3, 5, 8), (7, 10, 11), (7, 13, 14), (7, 15, 17)], 65185399904321760106225913740077263716894911708601269074244139762834096255597296012262332144), ([(0, 4, 8), (0, 6, 7), (0, 10, 11), (0, 12, 14), (0, 16, 17), (1, 5, 7), (1, 6, 8), (2, 7, 8), (3, 4, 7), (3, 5, 8), (4, 5, 6), (7, 9, 11), (7, 13, 14), (7, 15, 17)], 65185399904321760106225913740077263716900898019307732896537213083978461109481219673498541520), ([(0, 6, 8), (0, 9, 10), (0, 12, 14), (0, 16, 17), (1, 4, 6), (1, 7, 8), (2, 5, 8), (2, 6, 7), (3, 4, 8), (3, 5, 6), (4, 5, 7), (7, 9, 11), (7, 13, 14), (7, 15, 17)], 65185399904321760106225913740077260578356016636673858356995463773220058952399093233636038464), ([(0, 4, 5), (0, 6, 8), (0, 7, 11), (0, 12, 14), (0, 15, 16), (1, 4, 8), (2, 4, 6), (2, 7, 8), (3, 4, 7), (3, 5, 8), (5, 6, 7), (7, 9, 10), (7, 12, 13), (7, 16, 17)], 65185275573512657207253389029542184320283288055520618197710424824718870994258500076466985456), ([(0, 4, 6), (0, 5, 8), (0, 7, 17), (0, 9, 11), (0, 13, 14), (1, 4, 8), (1, 5, 7), (2, 4, 5), (3, 4, 7), (3, 5, 6), (6, 7, 8), (7, 10, 11), (7, 12, 14), (7, 15, 16)], 124330809102898975112865415125858043884307965343832550230083566156969641307564767603696), ([(0, 4, 7), (0, 5, 6), (0, 10, 11), (0, 13, 14), (0, 15, 17), (1, 5, 7), (1, 6, 8), (2, 4, 8), (2, 6, 7), (3, 4, 5), (3, 7, 8), (7, 9, 11), (7, 12, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310172040543302053971614290155042054126890224), ([(0, 4, 7), (0, 5, 8), (0, 10, 11), (0, 13, 14), (0, 15, 17), (1, 5, 7), (1, 6, 8), (2, 4, 5), (2, 6, 7), (3, 4, 6), (3, 7, 8), (7, 9, 11), (7, 12, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310172040543302291655195139159789222018346416), ([(0, 5, 8), (0, 6, 7), (0, 10, 11), (0, 12, 14), (0, 15, 17), (1, 7, 8), (2, 4, 8), (2, 5, 7), (3, 4, 7), (3, 6, 8), (4, 5, 6), (7, 9, 11), (7, 12, 13), (7, 16, 17)], 65185399904321759653913927875104224164050167173605119718601527077374461607235942162171616736), ([(0, 4, 8), (0, 6, 7), (0, 10, 11), (0, 13, 14), (0, 15, 17), (1, 4, 6), (1, 5, 8), (2, 5, 7), (2, 6, 8), (3, 5, 6), (3, 7, 8), (7, 9, 11), (7, 12, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310172040543302370883811000894729170299579856), ([(0, 4, 6), (0, 5, 8), (0, 7, 12), (0, 10, 11), (0, 13, 14), (0, 15, 17), (1, 4, 8), (1, 5, 7), (2, 4, 5), (2, 6, 7), (3, 4, 7), (3, 5, 6), (7, 9, 11), (7, 16, 17)], 65185399904321760106224188303490566075954039330343187209450721739896959098146321450517331440), ([(0, 4, 6), (0, 5, 8), (0, 7, 13), (0, 10, 11), (0, 15, 17), (1, 4, 7), (1, 6, 8), (2, 4, 5), (2, 7, 8), (3, 4, 8), (5, 6, 7), (7, 9, 11), (7, 16, 17), (12, 13, 14)], 65185399904321760106226776458370612537374327363791911321293677636546328387310355048634166768), ([(0, 4, 5), (0, 6, 7), (0, 9, 10), (0, 12, 13), (0, 15, 17), (1, 4, 7), (1, 6, 8), (2, 4, 6), (2, 5, 8), (3, 5, 6), (3, 7, 8), (7, 10, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225051021783914896421482364121272039295476451840615239163546182470514416), ([(0, 4, 6), (0, 7, 8), (0, 9, 10), (0, 12, 13), (0, 15, 17), (1, 4, 7), (1, 5, 8), (2, 4, 5), (2, 6, 8), (3, 4, 8), (3, 5, 6), (7, 9, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225051021783911757882587292193861321922185179166625969306852108984825808), ([(0, 4, 8), (0, 5, 6), (0, 10, 11), (0, 12, 14), (0, 15, 17), (1, 4, 5), (1, 6, 7), (2, 5, 7), (2, 6, 8), (3, 4, 6), (3, 7, 8), (7, 9, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310520489687029094957898554874610379233877360), ([(0, 4, 8), (0, 6, 7), (0, 10, 11), (0, 12, 13), (0, 15, 17), (1, 4, 7), (1, 5, 6), (2, 5, 7), (2, 6, 8), (3, 4, 6), (3, 7, 8), (7, 9, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225051021783914896427468674827735861505472706336830603737570549646409168), ([(0, 4, 5), (0, 6, 7), (0, 9, 10), (0, 12, 13), (0, 15, 17), (1, 4, 8), (1, 5, 7), (2, 4, 7), (2, 6, 8), (3, 4, 6), (3, 7, 8), (7, 10, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225051021783914896421482364121272039295476214157336621901924251923035888), ([(0, 4, 5), (0, 7, 8), (0, 10, 11), (0, 12, 14), (0, 15, 17), (1, 4, 7), (1, 6, 8), (2, 5, 8), (2, 6, 7), (3, 4, 8), (3, 5, 6), (7, 9, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310520489687029253414525813128806966763904432), ([(0, 5, 7), (0, 6, 8), (0, 10, 11), (0, 12, 13), (0, 15, 17), (1, 4, 7), (1, 5, 8), (2, 4, 6), (2, 7, 8), (3, 4, 5), (3, 6, 7), (7, 9, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225051021783914896427468674827735861505472944020260332403194164165131744), ([(0, 4, 8), (0, 6, 7), (0, 9, 10), (0, 12, 14), (0, 15, 17), (1, 4, 7), (1, 6, 8), (2, 4, 6), (2, 5, 8), (3, 4, 5), (3, 7, 8), (7, 9, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077260578356016636676645950145279863428263375543075306217854928), ([(0, 4, 5), (0, 7, 8), (0, 9, 11), (0, 12, 14), (0, 15, 17), (1, 5, 8), (1, 6, 7), (2, 4, 6), (2, 5, 7), (3, 4, 8), (3, 5, 6), (7, 10, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310564045746918542257314680095825328951450544), ([(0, 5, 6), (0, 7, 8), (0, 10, 11), (0, 12, 14), (0, 15, 17), (1, 4, 6), (1, 5, 8), (2, 4, 5), (2, 6, 7), (3, 4, 8), (3, 5, 7), (7, 9, 10), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716894911708603925998965058608812538850150982334839709152), ([(0, 4, 7), (0, 6, 8), (0, 9, 10), (0, 12, 13), (0, 15, 17), (1, 4, 8), (1, 5, 6), (2, 4, 5), (2, 6, 7), (3, 4, 6), (5, 7, 8), (7, 10, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225051021783914896421482364121272039295476610298149186306067798822139856), ([(0, 5, 6), (0, 7, 8), (0, 9, 11), (0, 12, 14), (0, 15, 17), (1, 5, 8), (1, 6, 7), (2, 4, 5), (2, 6, 8), (3, 4, 8), (3, 5, 7), (7, 9, 10), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077260578356016636676558837859348340865197600071874582310738912), ([(0, 4, 8), (0, 5, 6), (0, 9, 11), (0, 12, 14), (0, 15, 17), (1, 5, 7), (1, 6, 8), (2, 4, 7), (2, 5, 8), (3, 4, 5), (3, 7, 8), (7, 10, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310564045788456917125895533731907655625268080), ([(0, 4, 8), (0, 6, 7), (0, 9, 11), (0, 12, 14), (0, 15, 17), (1, 5, 6), (1, 7, 8), (2, 4, 7), (2, 5, 8), (3, 5, 7), (3, 6, 8), (7, 10, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310564045829995291994023039897390926067325904), ([(0, 5, 6), (0, 7, 8), (0, 9, 11), (0, 12, 14), (0, 15, 17), (1, 4, 6), (1, 5, 8), (2, 4, 7), (2, 6, 8), (3, 4, 5), (3, 6, 7), (7, 10, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310564045829995133536942428408003152463453152), ([(0, 4, 8), (0, 6, 7), (0, 10, 11), (0, 12, 14), (0, 15, 17), (1, 4, 6), (2, 4, 7), (2, 5, 6), (3, 4, 5), (3, 6, 8), (5, 7, 8), (7, 9, 10), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716894911708603925999048135358549700553964356086012239312), ([(0, 5, 6), (0, 7, 8), (0, 10, 11), (0, 12, 14), (0, 15, 17), (1, 4, 7), (1, 5, 8), (2, 4, 5), (2, 6, 7), (3, 4, 6), (3, 5, 7), (7, 9, 10), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716894911708603925998965058608811934383782410506448592352), ([(0, 7, 8), (0, 9, 10), (0, 12, 14), (0, 15, 17), (1, 5, 8), (1, 6, 7), (2, 4, 7), (2, 6, 8), (3, 4, 8), (3, 5, 7), (4, 5, 6), (7, 10, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716894911708604056667477032998919670490966546782879930240), ([(0, 4, 8), (0, 5, 7), (0, 9, 11), (0, 12, 14), (0, 15, 17), (1, 4, 6), (1, 7, 8), (2, 4, 5), (2, 6, 7), (3, 4, 7), (3, 5, 8), (7, 10, 11), (7, 13, 14), (7, 16, 17)], 65185399904321760106225913740077263716900898019310564045746918463029756629894216554597505968)]def ts18_EC : List ℕ := [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 22, 23, 24, 25, 26, 40, 41, 42, 43, 44, 58, 59, 60, 61, 62, 77, 78, 79, 80, 96, 97, 98, 115, 116, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 172, 173, 191, 229, 230, 248, 286, 287, 305]def ts18_CH : List (T18 × T18 × T18) := [((0, 4, 5), (0, 4, 5), (0, 4, 5)), ((0, 4, 6), (0, 4, 6), (0, 4, 6)), ((0, 4, 7), (0, 4, 7), (0, 4, 7)), ((0, 4, 8), (0, 4, 8), (0, 4, 8)), ((0, 5, 6), (0, 4, 5), (0, 4, 5)), ((0, 5, 7), (0, 5, 7), (0, 5, 7)), ((0, 5, 8), (0, 4, 5), (0, 4, 5)), ((0, 6, 7), (0, 6, 7), (0, 6, 7)), ((0, 6, 8), (0, 4, 6), (0, 4, 6)), ((0, 7, 8), (0, 7, 8), (0, 7, 8)), ((0, 7, 9), (0, 7, 9), (0, 7, 9)), ((0, 7, 10), (0, 7, 10), (0, 7, 10)), ((0, 7, 11), (0, 7, 11), (0, 7, 11)), ((0, 7, 12), (0, 7, 12), (0, 7, 12)), ((0, 7, 13), (0, 7, 13), (0, 7, 13)), ((0, 7, 14), (0, 7, 14), (0, 7, 14)), ((0, 7, 15), (0, 7, 15), (0, 7, 15)), ((0, 7, 16), (0, 7, 16), (0, 7, 16)), ((0, 7, 17), (0, 7, 17), (0, 7, 17)), ((0, 9, 10), (0, 7, 9), (0, 7, 9)), ((0, 9, 11), (0, 7, 9), (0, 7, 9)), ((0, 10, 11), (0, 7, 10), (0, 7, 10)), ((0, 12, 13), (0, 7, 12), (0, 7, 12)), ((0, 12, 14), (0, 7, 12), (0, 7, 12)), ((0, 13, 14), (0, 7, 13), (0, 7, 13)), ((0, 15, 16), (0, 7, 15), (0, 7, 15)), ((0, 15, 17), (0, 7, 15), (0, 7, 15)), ((0, 16, 17), (0, 7, 16), (0, 7, 16)), ((1, 4, 5), (0, 4, 5), (0, 4, 5)), ((1, 4, 6), (0, 4, 6), (0, 4, 6)), ((1, 4, 7), (1, 4, 7), (1, 4, 7)), ((1, 4, 8), (0, 4, 8), (0, 4, 8)), ((1, 5, 6), (0, 5, 6), (0, 4, 5)), ((1, 5, 7), (0, 5, 7), (0, 5, 7)), ((1, 5, 8), (0, 5, 8), (0, 4, 5)), ((1, 6, 7), (0, 6, 7), (0, 6, 7)), ((1, 6, 8), (0, 6, 8), (0, 4, 6)), ((1, 7, 8), (0, 7, 8), (0, 7, 8)), ((2, 4, 5), (0, 4, 5), (0, 4, 5)), ((2, 4, 6), (0, 4, 6), (0, 4, 6)), ((2, 4, 7), (2, 4, 7), (2, 4, 7)), ((2, 4, 8), (0, 4, 8), (0, 4, 8)), ((2, 5, 6), (0, 5, 6), (0, 4, 5)), ((2, 5, 7), (0, 5, 7), (0, 5, 7)), ((2, 5, 8), (0, 5, 8), (0, 4, 5)), ((2, 6, 7), (0, 6, 7), (0, 6, 7)), ((2, 6, 8), (0, 6, 8), (0, 4, 6)), ((2, 7, 8), (0, 7, 8), (0, 7, 8)), ((3, 4, 5), (0, 4, 5), (0, 4, 5)), ((3, 4, 6), (0, 4, 6), (0, 4, 6)), ((3, 4, 7), (3, 4, 7), (3, 4, 7)), ((3, 4, 8), (0, 4, 8), (0, 4, 8)), ((3, 5, 6), (0, 5, 6), (0, 4, 5)), ((3, 5, 7), (0, 5, 7), (0, 5, 7)), ((3, 5, 8), (0, 5, 8), (0, 4, 5)), ((3, 6, 7), (0, 6, 7), (0, 6, 7)), ((3, 6, 8), (0, 6, 8), (0, 4, 6)), ((3, 7, 8), (0, 7, 8), (0, 7, 8)), ((4, 5, 6), (0, 4, 5), (0, 4, 5)), ((4, 5, 7), (4, 5, 7), (4, 5, 7)), ((4, 5, 8), (0, 4, 5), (0, 4, 5)), ((4, 6, 7), (4, 6, 7), (4, 6, 7)), ((4, 6, 8), (0, 4, 6), (0, 4, 6)), ((4, 7, 8), (4, 7, 8), (4, 7, 8)), ((5, 6, 7), (0, 5, 7), (0, 5, 7)), ((5, 6, 8), (0, 5, 6), (0, 4, 5)), ((5, 7, 8), (0, 5, 7), (0, 5, 7)), ((6, 7, 8), (0, 6, 7), (0, 6, 7)), ((7, 9, 10), (0, 7, 9), (0, 7, 9)), ((7, 9, 11), (0, 7, 9), (0, 7, 9)), ((7, 10, 11), (0, 7, 10), (0, 7, 10)), ((7, 12, 13), (0, 7, 12), (0, 7, 12)), ((7, 12, 14), (0, 7, 12), (0, 7, 12)), ((7, 13, 14), (0, 7, 13), (0, 7, 13)), ((7, 15, 16), (0, 7, 15), (0, 7, 15)), ((7, 15, 17), (0, 7, 15), (0, 7, 15)), ((7, 16, 17), (0, 7, 16), (0, 7, 16)), ((9, 10, 11), (0, 9, 10), (0, 7, 9)), ((12, 13, 14), (0, 12, 13), (0, 7, 12)), ((15, 16, 17), (0, 15, 16), (0, 7, 15))]def ts18_cnt (y : T18) (m : ℕ) : ℕ := (if m.testBit (ts18_sc y.1 y.2.1) = true then 1 else 0) + (if m.testBit (ts18_sc y.1 y.2.2) = true then 1 else 0) + (if m.testBit (ts18_sc y.2.1 y.2.2) = true then 1 else 0)theorem ts18_card_inter_U (S : List T18) (y : T18) (hy : y ∈ ts18_L) : (ts18_enc y ∩ (ts18_pk S).biUnion id).card = ts18_cnt y (ts18_um S) := by obtain ⟨l1, l2, -⟩ := ts18_L_tri y hy rcases y with ⟨a, b, c⟩ rw [ts18_card_inter a b c l1 l2] simp only [ts18_mem_U, ts18_scS_mk, ts18_cnt]def ts18_frc (S : List T18) (x : T18) : Bool := [ts18_sc x.1 x.2.1, ts18_sc x.1 x.2.2, ts18_sc x.2.1 x.2.2].all (fun k => ts18_L.any (fun y => (ts18_msk y).testBit k && ts18_cnt y (ts18_um S) == 1))set_option maxRecDepth 100000 intheorem ts18_frc_spec (S : List T18) (x : T18) (h : ts18_frc S x = true) : ts18_enc x ⊆ ((ts18_F.filter (fun t => (t ∩ (ts18_pk S).biUnion id).card = 1)).biUnion id) := by intro e he rw [ts18_mem_enc, ts18_tb_msk] at he have hk : ts18_scS e ∈ [ts18_sc x.1 x.2.1, ts18_sc x.1 x.2.2, ts18_sc x.2.1 x.2.2] := by rcases he with h | h | h <;> simp [h] unfold ts18_frc at h rw [List.all_eq_true] at h have h' := h _ hk rw [List.any_eq_true] at h' obtain ⟨y, hy, h''⟩ := h' rw [Bool.and_eq_true, beq_iff_eq] at h'' obtain ⟨h1, h2⟩ := h'' rw [Finset.mem_biUnion] refine ⟨ts18_enc y, ?_, (ts18_mem_enc y e).mpr h1⟩ rw [Finset.mem_filter, ts18_mem_F, ts18_card_inter_U S y hy] exact ⟨⟨y, hy, rfl⟩, h2⟩set_option maxRecDepth 100000 intheorem ts18_adj7 : ∀ w : Fin 18, w ≠ 7 → ts18_G.Adj 7 w := by decide +kerneltheorem ts18_connected : ts18_G.Connected := by have hr : ∀ w : Fin 18, ts18_G.Reachable 7 w := by intro w by_cases h : w = 7 · subst h; rfl · exact (ts18_adj7 w h).reachable exact ⟨fun u v => (hr u).symm.trans (hr v)⟩theorem ts18_deg : ∃ v : Fin 18, ∃ N : Finset (Fin 18), N.card = 17 ∧ ∀ w ∈ N, ts18_G.Adj v w := ⟨7, Finset.univ.erase 7, by simp, fun w hw => ts18_adj7 w (Finset.ne_of_mem_erase hw)⟩set_option maxRecDepth 100000 intheorem ts18_deg_sum : ∑ v, ts18_G.degree v = 114 := by decide +kerneltheorem ts18_E_card : ts18_G.edgeFinset.card = 57 := by have h := ts18_G.sum_degrees_eq_twice_card_edges rw [ts18_deg_sum] at h omegaset_option maxRecDepth 100000 intheorem ts18_LM_nodup : (ts18_L.map ts18_msk).Nodup := by decide +kernelset_option maxRecDepth 100000 intheorem ts18_codeg_chk : ∀ a b : Fin 18, ts18_G.Adj a b → 3 ≤ (ts18_L.filter (fun y => (ts18_msk y).testBit (ts18_sc a b))).length := by decide +kerneltheorem ts18_codeg : ∀ e ∈ ts18_G.edgeSet, 3 ≤ (ts18_F.filter (fun t => e ∈ t)).card := by intro e he induction e using Sym2.ind with | _ a b => have hc := ts18_codeg_chk a b he have hinj : ∀ x ∈ ts18_L.filter (fun y => (ts18_msk y).testBit (ts18_sc a b)), ∀ y ∈ ts18_L.filter (fun y => (ts18_msk y).testBit (ts18_sc a b)), ts18_enc x = ts18_enc y → x = y := by intro x hx y hy h exact List.inj_on_of_nodup_map ts18_LM_nodup (List.mem_of_mem_filter hx) (List.mem_of_mem_filter hy) (ts18_enc_msk x y h) have hnd := (List.Nodup.of_map _ ts18_LM_nodup).filter (fun y => (ts18_msk y).testBit (ts18_sc a b)) have hcard := List.toFinset_card_of_nodup (List.Nodup.map_on hinj hnd) rw [List.length_map] at hcard refine hc.trans (hcard.symm.le.trans (Finset.card_le_card ?_)) intro t ht simp only [List.mem_toFinset, List.mem_map, List.mem_filter] at ht obtain ⟨y, ⟨hy1, hy2⟩, rfl⟩ := ht rw [Finset.mem_filter, ts18_mem_F] exact ⟨⟨y, hy1, rfl⟩, (ts18_mem_enc y _).mpr (by rw [ts18_scS_mk]; exact hy2)⟩set_option maxRecDepth 100000 intheorem ts18_Wm_ok : ts18_Wm.all (fun p => ts18_um p.1 == p.2 && ts18_pd p.1 && p.1.length == 14 && p.1.all (fun x => decide (x ∈ ts18_L))) = true := by decide +kernelset_option maxRecDepth 100000 intheorem ts18_EC_spec : ∀ a b : Fin 18, ts18_G.Adj a b → ts18_sc a b ∈ ts18_EC := by decide +kernelset_option maxRecDepth 100000 intheorem ts18_EC_pairs : ts18_EC.all (fun k1 => ts18_EC.all (fun k2 => k1 == k2 || ts18_Wm.any (fun p => !p.2.testBit k1 && !p.2.testBit k2))) = true := by decide +kerneltheorem ts18_pair_stable : ∀ e ∈ ts18_G.edgeSet, ∀ f ∈ ts18_G.edgeSet, e ≠ f → ∃ Q : Finset (Finset (Sym2 (Fin 18))), Q ⊆ ts18_F ∧ Q.card = 14 ∧ (Q : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint ∧ e ∉ Q.biUnion id ∧ f ∉ Q.biUnion id := by intro e he f hf hef induction e using Sym2.ind with | _ a b => induction f using Sym2.ind with | _ c d => have h1 := ts18_EC_spec a b he have h2 := ts18_EC_spec c d hf have hne : ts18_sc a b ≠ ts18_sc c d := fun h => hef ((ts18_sc_eq_iff a b c d).mp h) have h3 := List.all_eq_true.mp (List.all_eq_true.mp ts18_EC_pairs _ h1) _ h2 simp only [Bool.or_eq_true, beq_iff_eq, hne, false_or, List.any_eq_true, Bool.and_eq_true, Bool.not_eq_true'] at h3 obtain ⟨p, hp, hp1, hp2⟩ := h3 have h4 := List.all_eq_true.mp ts18_Wm_ok p hp simp only [Bool.and_eq_true, beq_iff_eq, List.all_eq_true, decide_eq_true_eq] at h4 obtain ⟨⟨⟨hum, hpd⟩, hlen⟩, hsub⟩ := h4 refine ⟨ts18_pk p.1, ts18_pk_sub _ hsub, by rw [ts18_pk_card _ hpd, hlen], ts18_pk_disj _ hpd, ?_, ?_⟩ · rw [ts18_mem_U, ts18_scS_mk, hum, hp1]; decide · rw [ts18_mem_U, ts18_scS_mk, hum, hp2]; decidedef ts18_PL : List T18 := [(0, 4, 5), (3, 4, 8), (3, 6, 7), (0, 6, 8), (1, 4, 6), (5, 7, 8), (2, 4, 7), (2, 5, 6), (0, 9, 10), (7, 10, 11), (0, 12, 13), (7, 13, 14), (0, 15, 16), (7, 16, 17)]def ts18_P : Finset (Finset (Sym2 (Fin 18))) := ts18_pk ts18_PLset_option maxRecDepth 100000 intheorem ts18_PL_ok : (ts18_pd ts18_PL && ts18_PL.length == 14 && ts18_PL.all (fun x => decide (x ∈ ts18_L)) && ts18_PL.any (ts18_frc ts18_PL)) = true := by decide +kerneltheorem ts18_PL_facts : ts18_pd ts18_PL = true ∧ ts18_PL.length = 14 ∧ (∀ x ∈ ts18_PL, x ∈ ts18_L) ∧ ∃ x ∈ ts18_PL, ts18_frc ts18_PL x = true := by have h := ts18_PL_ok simp only [Bool.and_eq_true, beq_iff_eq, List.all_eq_true, decide_eq_true_eq, List.any_eq_true] at h exact ⟨h.1.1.1, h.1.1.2, h.1.2, h.2⟩theorem ts18_P_forced : ∃ p ∈ ts18_P, p ⊆ ((ts18_F.filter (fun t => (t ∩ ts18_P.biUnion id).card = 1)).biUnion id) := by obtain ⟨x, hx, hf⟩ := ts18_PL_facts.2.2.2 refine ⟨ts18_enc x, ?_, ts18_frc_spec _ x hf⟩ simp only [ts18_P, ts18_pk, List.mem_toFinset, List.mem_map] exact ⟨x, hx, rfl⟩def ts18_rest (x : T18) : List T18 := ts18_PL.filter (fun z => z != x)set_option maxRecDepth 100000 intheorem ts18_trap_chk : ts18_PL.all (fun x => ts18_L.all (fun y => !(ts18_rest x).all (fun z => ts18_msk y &&& ts18_msk z == 0) || (y :: ts18_rest x).any (ts18_frc (y :: ts18_rest x)))) = true := by decide +kerneltheorem ts18_trap (Q : Finset (Finset (Sym2 (Fin 18)))) (hQF : Q ⊆ ts18_F) (hQc : Q.card = 14) (hQd : (Q : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint) (hPQ : (ts18_P \ Q).card = 1) : ∃ q ∈ Q, q ⊆ ((ts18_F.filter (fun t => (t ∩ Q.biUnion id).card = 1)).biUnion id) := by obtain ⟨hPLpd, hPLlen, -, -⟩ := ts18_PL_facts obtain ⟨p, hp⟩ := Finset.card_eq_one.mp hPQ have hpPQ : p ∈ ts18_P \ Q := by rw [hp]; exact Finset.mem_singleton_self p have hpP : p ∈ ts18_P := (Finset.mem_sdiff.mp hpPQ).1 have hsub : ts18_P.erase p ⊆ Q := by intro t ht by_contra htQ have : t ∈ ts18_P \ Q := Finset.mem_sdiff.mpr ⟨Finset.mem_of_mem_erase ht, htQ⟩ rw [hp, Finset.mem_singleton] at this exact Finset.ne_of_mem_erase ht this have hPc : ts18_P.card = 14 := by rw [ts18_P, ts18_pk_card _ hPLpd, hPLlen] have hEc : (ts18_P.erase p).card = 13 := by rw [Finset.card_erase_of_mem hpP, hPc] obtain ⟨q, hqQ, hqn⟩ : ∃ q ∈ Q, q ∉ ts18_P.erase p := by by_contra hcon push Not at hcon have := Finset.card_le_card (show Q ⊆ ts18_P.erase p from hcon) omega have hQeq : Q = insert q (ts18_P.erase p) := by symm apply Finset.eq_of_subset_of_card_le (Finset.insert_subset hqQ hsub) rw [Finset.card_insert_of_notMem hqn, hEc, hQc] obtain ⟨x, hx, rfl⟩ : ∃ x ∈ ts18_PL, ts18_enc x = p := by simpa [ts18_P, ts18_pk] using hpP obtain ⟨y, hy, rfl⟩ := (ts18_mem_F q).mp (hQF hqQ) have herase : ts18_P.erase (ts18_enc x) = ts18_pk (ts18_rest x) := by ext t simp only [Finset.mem_erase, ts18_P, ts18_pk, ts18_rest, List.mem_toFinset, List.mem_map, List.mem_filter, bne_iff_ne, ne_eq] constructor · rintro ⟨hne, z, hz, rfl⟩ exact ⟨z, ⟨hz, fun h => hne (by rw [h])⟩, rfl⟩ · rintro ⟨z, ⟨hz, hzx⟩, rfl⟩ exact ⟨fun h => hzx (ts18_pd_inj _ hPLpd z hz x hx h), z, hz, rfl⟩ have hmr : ∀ z ∈ ts18_rest x, ts18_enc z ∈ ts18_P.erase (ts18_enc x) := by intro z hz rw [herase] simp only [ts18_pk, List.mem_toFinset, List.mem_map] exact ⟨z, hz, rfl⟩ have hQS : Q = ts18_pk (y :: ts18_rest x) := by rw [hQeq, herase] simp only [ts18_pk, List.map_cons, List.toFinset_cons] have hdisj : (ts18_rest x).all (fun z => ts18_msk y &&& ts18_msk z == 0) = true := by rw [List.all_eq_true] intro z hz have hne : ts18_enc y ≠ ts18_enc z := by intro h apply hqn rw [h] exact hmr z hz simpa using ts18_land_of_disj y z (hQd hqQ (hsub (hmr z hz)) hne) have hc := List.all_eq_true.mp (List.all_eq_true.mp ts18_trap_chk x hx) y hy simp only [hdisj, Bool.not_true, Bool.false_or, List.any_eq_true] at hc obtain ⟨z, hz, hfz⟩ := hc refine ⟨ts18_enc z, ?_, ?_⟩ · rw [hQS] simp only [ts18_pk, List.mem_toFinset, List.mem_map] exact ⟨z, hz, rfl⟩ · rw [hQS] exact ts18_frc_spec _ z hfzdef ts18_hub : T18 := (0, 4, 7)set_option maxRecDepth 100000 intheorem ts18_CH_ok : (ts18_CH.all (fun c => decide (c.2.1 ∈ ts18_L) && decide (c.2.2 ∈ ts18_L) && ts18_msk c.1 &&& ts18_msk c.2.1 != 0 && ts18_msk c.2.1 &&& ts18_msk c.2.2 != 0 && ts18_msk c.2.2 &&& ts18_msk ts18_hub != 0) && ts18_L.all (fun x => ts18_CH.any (fun c => c.1 == x)) && decide (ts18_hub ∈ ts18_L)) = true := by decide +kerneldef ts18_R (x y : Finset (Sym2 (Fin 18))) : Prop := x ∈ ts18_F ∧ y ∈ ts18_F ∧ ¬ Disjoint x ytheorem ts18_family_conn : ∀ a ∈ ts18_F, ∀ b ∈ ts18_F, Relation.ReflTransGen (fun x y : Finset (Sym2 (Fin 18)) => x ∈ ts18_F ∧ y ∈ ts18_F ∧ ¬ Disjoint x y) a b := by have h := ts18_CH_ok simp only [Bool.and_eq_true, List.all_eq_true, decide_eq_true_eq, bne_iff_ne, ne_eq, List.any_eq_true, beq_iff_eq] at h obtain ⟨⟨hc, hcov⟩, hhub⟩ := h have hF : ∀ x ∈ ts18_L, ts18_enc x ∈ ts18_F := fun x hx => (ts18_mem_F _).mpr ⟨x, hx, rfl⟩ have step : ∀ x ∈ ts18_L, ∀ y ∈ ts18_L, ts18_msk x &&& ts18_msk y ≠ 0 → ts18_R (ts18_enc x) (ts18_enc y) := fun x hx y hy h => ⟨hF x hx, hF y hy, ts18_not_disj x y h⟩ have tohub : ∀ x ∈ ts18_L, Relation.ReflTransGen ts18_R (ts18_enc x) (ts18_enc ts18_hub) := by intro x hx obtain ⟨c, hcm, rfl⟩ := hcov x hx obtain ⟨⟨⟨⟨h1, h2⟩, h3⟩, h4⟩, h5⟩ := hc c hcm exact ((Relation.ReflTransGen.single (step _ hx _ h1 h3)).tail (step _ h1 _ h2 h4)).tail (step _ h2 _ hhub h5) have rev : ∀ a b, Relation.ReflTransGen ts18_R a b → Relation.ReflTransGen ts18_R b a := by intro a b hab induction hab with | refl => exact .refl | tail _ hbc ih => exact .head ⟨hbc.2.1, hbc.1, fun hd => hbc.2.2 hd.symm⟩ ih intro a ha b hb obtain ⟨x, hx, rfl⟩ := (ts18_mem_F a).mp ha obtain ⟨y, hy, rfl⟩ := (ts18_mem_F b).mp hb exact (tohub x hx).trans (rev _ _ (tohub y hy))def ts18_ty (x : T18) : ℕ := if x.2.2.val < 9 then (if x.1.val < 4 then x.1.val else 4) else 5 + (x.2.2.val - 9) / 3def ts18_w (k : ℕ) : ℕ := (if k < 4 then 1 else 0) + (if k = 4 then 3 else 0)def ts18_SKT : List T18 := [(4, 5, 6), (4, 7, 8), (5, 6, 7), (5, 6, 8)]def ts18_SK : Finset (Sym2 (Fin 18)) := (ts18_pk ts18_SKT).biUnion idset_option maxRecDepth 100000 intheorem ts18_SK_card : ts18_SK.card = 10 := by decide +kernelset_option maxRecDepth 100000 intheorem ts18_L_cls : ts18_L.all (fun x => decide (ts18_ty x < 8) && (ts18_ty x == 4 || decide (x ∈ ts18_C (ts18_ty x))) && decide (ts18_w (ts18_ty x) ≤ ts18_cnt x (ts18_um ts18_SKT))) = true := by decide +kernelset_option maxRecDepth 100000 intheorem ts18_no_three : [0, 1, 2, 3, 5, 6, 7].all (fun k => (ts18_C k).all (fun x1 => (ts18_C k).all (fun x2 => (ts18_C k).all (fun x3 => ts18_msk x1 &&& ts18_msk x2 != 0 || ts18_msk x1 &&& ts18_msk x3 != 0 || ts18_msk x2 &&& ts18_msk x3 != 0)))) = true := by decide +kerneltheorem ts18_sum_inter_le (Q : Finset (Finset (Sym2 (Fin 18)))) (hQ : (Q : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint) (S : Finset (Sym2 (Fin 18))) : ∑ t ∈ Q, (t ∩ S).card ≤ S.card := by rw [← Finset.card_biUnion] · exact Finset.card_le_card (Finset.biUnion_subset.mpr (fun t _ => Finset.inter_subset_right)) · intro t ht t' ht' hne exact Disjoint.mono Finset.inter_subset_left Finset.inter_subset_left (hQ ht ht' hne)theorem ts18_nu_le (Q : Finset (Finset (Sym2 (Fin 18)))) (hQF : Q ⊆ ts18_F) (hQ : (Q : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint) : Q.card ≤ 14 := by have hmem : ∀ t ∈ Q, ∃ x ∈ ts18_L, ts18_enc x = t := fun t ht => (ts18_mem_F t).mp (hQF ht) choose! rep hrepL hrep using hmem have hcls : ∀ x ∈ ts18_L, ts18_ty x < 8 ∧ (ts18_ty x = 4 ∨ x ∈ ts18_C (ts18_ty x)) ∧ ts18_w (ts18_ty x) ≤ ts18_cnt x (ts18_um ts18_SKT) := by intro x hx have := List.all_eq_true.mp ts18_L_cls x hx simp only [Bool.and_eq_true, decide_eq_true_eq, Bool.or_eq_true, beq_iff_eq] at this exact ⟨this.1.1, this.1.2, this.2⟩ have hg8 : ∀ t ∈ Q, ts18_ty (rep t) ∈ Finset.range 8 := fun t ht => Finset.mem_range.mpr (hcls _ (hrepL t ht)).1 have hcard := Finset.card_eq_sum_card_fiberwise hg8 have hfib : ∀ k ∈ [0, 1, 2, 3, 5, 6, 7], (Q.filter (fun t => ts18_ty (rep t) = k)).card ≤ 2 := by intro k hk by_contra hc push Not at hc obtain ⟨t1, t2, t3, h1, h2, h3, h12, h13, h23⟩ := Finset.two_lt_card_iff.mp hc simp only [Finset.mem_filter] at h1 h2 h3 have hk4 : k ≠ 4 := by rintro rfl; simp at hk have mC : ∀ t, t ∈ Q ∧ ts18_ty (rep t) = k → rep t ∈ ts18_C k := by intro t ht rcases (hcls _ (hrepL t ht.1)).2.1 with h | h · exact absurd (ht.2 ▸ h) hk4 · rwa [ht.2] at h have H := List.all_eq_true.mp (List.all_eq_true.mp (List.all_eq_true.mp (List.all_eq_true.mp ts18_no_three k hk) _ (mC t1 h1)) _ (mC t2 h2)) _ (mC t3 h3) simp only [Bool.or_eq_true, bne_iff_ne, ne_eq] at H rcases H with (H | H) | H · exact ts18_not_disj _ _ H (by rw [hrep t1 h1.1, hrep t2 h2.1]; exact hQ h1.1 h2.1 h12) · exact ts18_not_disj _ _ H (by rw [hrep t1 h1.1, hrep t3 h3.1]; exact hQ h1.1 h3.1 h13) · exact ts18_not_disj _ _ H (by rw [hrep t2 h2.1, hrep t3 h3.1]; exact hQ h2.1 h3.1 h23) have hw : ∑ t ∈ Q, ts18_w (ts18_ty (rep t)) ≤ ∑ t ∈ Q, (t ∩ ts18_SK).card := by apply Finset.sum_le_sum intro t ht have := (hcls _ (hrepL t ht)).2.2 rw [← ts18_card_inter_U ts18_SKT _ (hrepL t ht), hrep t ht] at this exact this have hS := ts18_sum_inter_le Q hQ ts18_SK rw [ts18_SK_card] at hS rw [← Finset.sum_fiberwise_of_maps_to hg8] at hw have hw' : ∀ k ∈ Finset.range 8, ∑ t ∈ Q.filter (fun t => ts18_ty (rep t) = k), ts18_w (ts18_ty (rep t)) = ts18_w k * (Q.filter (fun t => ts18_ty (rep t) = k)).card := by intro k _ rw [Finset.sum_congr rfl (fun t ht => by rw [(Finset.mem_filter.mp ht).2]), Finset.sum_const, smul_eq_mul, mul_comm] rw [Finset.sum_congr rfl hw'] at hw simp only [Finset.sum_range_succ, Finset.sum_range_zero, ts18_w] at hw hcard have f0 := hfib 0 (by simp) have f1 := hfib 1 (by simp) have f2 := hfib 2 (by simp) have f3 := hfib 3 (by simp) have f5 := hfib 5 (by simp) have f6 := hfib 6 (by simp) have f7 := hfib 7 (by simp) norm_num at hw omegatheorem simple_graph_two_edge_stable_connected_family_exchange_trap_counterexample : ∃ (G : SimpleGraph (Fin 18)) (E : Finset (Sym2 (Fin 18))) (P : Finset (Finset (Sym2 (Fin 18)))), let F := simple_graph_triangle_edge_family G (↑E : Set (Sym2 (Fin 18))) = G.edgeSet ∧ E.card = 57 ∧ G.Connected ∧ (∀ a ∈ F, ∀ b ∈ F, Relation.ReflTransGen (fun x y : Finset (Sym2 (Fin 18)) => x ∈ F ∧ y ∈ F ∧ ¬ Disjoint x y) a b) ∧ (∀ Q : Finset (Finset (Sym2 (Fin 18))), Q ⊆ F → (Q : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint → Q.card ≤ 14) ∧ P ⊆ F ∧ P.card = 14 ∧ (P : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint ∧ (∀ e ∈ G.edgeSet, ∀ f ∈ G.edgeSet, e ≠ f → ∃ Q : Finset (Finset (Sym2 (Fin 18))), Q ⊆ F ∧ Q.card = 14 ∧ (Q : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint ∧ e ∉ Q.biUnion id ∧ f ∉ Q.biUnion id) ∧ (∀ e ∈ G.edgeSet, 3 ≤ (F.filter (fun t => e ∈ t)).card) ∧ (∃ v : Fin 18, ∃ N : Finset (Fin 18), N.card = 17 ∧ ∀ w ∈ N, G.Adj v w) ∧ (∃ p ∈ P, p ⊆ ((F.filter (fun t => (t ∩ P.biUnion id).card = 1)).biUnion id)) ∧ ∀ Q : Finset (Finset (Sym2 (Fin 18))), Q ⊆ F → Q.card = 14 → (Q : Set (Finset (Sym2 (Fin 18)))).Pairwise Disjoint → (P \ Q).card = 1 → ∃ q ∈ Q, q ⊆ ((F.filter (fun t => (t ∩ Q.biUnion id).card = 1)).biUnion id) := by obtain ⟨hPLpd, hPLlen, hPLsub, -⟩ := ts18_PL_facts refine ⟨ts18_G, ts18_G.edgeFinset, ts18_P, ?_⟩ dsimp only rw [ts18_F_eq] exact ⟨SimpleGraph.coe_edgeFinset _, ts18_E_card, ts18_connected, ts18_family_conn, fun Q hQ hd => ts18_nu_le Q hQ hd, ts18_pk_sub _ hPLsub, by rw [ts18_P, ts18_pk_card _ hPLpd, hPLlen], ts18_pk_disj _ hPLpd, ts18_pair_stable, ts18_codeg, ts18_deg, ts18_P_forced, fun Q hQ hc hd hpq => ts18_trap Q hQ hc hd hpq⟩