ten_vertex_exchange_family_eq
The 52 explicit triangle edge sets are exactly the triangle family of the ten-vertex graph.
Statement
theorem ten_vertex_exchange_family_eq : simple_graph_triangle_edge_family ten_vertex_exchange_graph = ten_vertex_exchange_family- Source
- Explicit ten-vertex witness for simple_graph_stable_point_irreducible_forced_exchange_barrier_counterexample.
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- ten_vertex_exchange_graphThe simple graph built from the explicit ten-vertex edge set.
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- ten_vertex_exchange_familyThe explicit list of 52 triangle edge sets for the ten-vertex witness.
- simple_graph_triangle_edge_family_memA set of three edges belongs to the triangle edge family of G iff it is the set of non-diagonal pairs spanned by some three vertices…
- simple_graph_two_edge_stable_connected_family_exchange_trap_counterexampleThere is a connected 18-vertex graph with 57 edges, packing number 14, all edge pairs avoidable by maximum packings, at least three…
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - ten_vertex_exchange_edgesThe 35 unordered edges of the explicit ten-vertex witness.
- Used by 5
- ten_vertex_exchange_packing_upperThe witness has no packing of eleven edge-disjoint triangles.
- ten_vertex_exchange_edge_avoidableFor each of the 35 edges, a ten-triangle packing avoids that edge.
- ten_vertex_exchange_six_connectedDeleting any at most five vertices leaves the ten-vertex witness graph connected.
- ten_vertex_exchange_triangle_connectedAfter excluding each graph edge, the triangle family is connected under sharing any other edge.
- ten_vertex_exchange_codegreeEach edge of the witness lies in at least three triangles.
The proof, explained
The proof establishes that the triangle edge family of the ten-vertex exchange graph equals the explicit 52-element family by introducing an intermediate list of sorted triples. First, helper lemmas verify by finite exhaustion that every triangle in the graph sorts into the list, that edge encoding is invariant under sorting, and that every list element is a genuine triangle. Finally, the main theorem rewrites the goal via this intermediate list and shows two-way inclusion between cliques of size 3 and elements of the list.
Every triangle in the graph, when sorted, appears in the list in732_tris
We exhaustively check all vertices a and decide whether adjacent pairs b and c form a triple in in732_tris.
theorem in732_sort_mem (a : Fin 10) : ∀ b c : Fin 10, ten_vertex_exchange_graph.Adj a b → ten_vertex_exchange_graph.Adj a c → ten_vertex_exchange_graph.Adj b c → in732_sort3 a b c ∈ in732_tris := by fin_cases a <;> decide
Encoding a sorted triple yields the same 3-edge set as encoding the unsorted vertices
Unfolding definitions and casing on the permutations shows symmetry under edge reversal.
theorem in732_enc_sort3 (a b c : Fin 10) : in732_enc (in732_sort3 a b c) = {s(a,b),s(a,c),s(b,c)} := by unfold in732_sort3 in732_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 triple in in732_tris is strictly sorted and forms a triangle in the graph
We case split on the list of 52 triangles and check each one by computation.
uses
List.mem_cons,List.mem_singleton,List.not_mem_nil,or_falsetheorem in732_list_tri : ∀ x ∈ in732_tris, x.1 < x.2.1 ∧ x.2.1 < x.2.2 ∧ ten_vertex_exchange_graph.Adj x.1 x.2.1 ∧ ten_vertex_exchange_graph.Adj x.1 x.2.2 ∧ ten_vertex_exchange_graph.Adj x.2.1 x.2.2 := by intro x hx simp only [in732_tris, List.mem_cons, List.mem_singleton, List.not_mem_nil, or_false] at hx rcases hx with h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h <;> subst x <;> decide
The encoded list of triangles coincides with the defined family
Decided by computation.
theorem in732_list_family : (in732_tris.map in732_enc).toFinset = ten_vertex_exchange_family := by decide
Main theorem test
Main theorem steps.
classical rw [← in732_list_family] ext t rw [simple_graph_triangle_edge_family_mem] simp only [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 ⟨_, in732_sort_mem a b c h1 h2 h3, by rw [in732_enc_sort3, ts18_fvsee_triple a b c hab hac hbc]⟩ · rintro ⟨x,hx,rfl⟩ obtain ⟨l1,l2,h1,h2,h3⟩ := in732_list_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
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option maxRecDepth 8192set_option maxHeartbeats 3000000open scoped Sym2namespace In732Familyinstance in732_G_dec : DecidableRel ten_vertex_exchange_graph.Adj := fun a b => inferInstanceAs (Decidable (s(a,b) ∈ ten_vertex_exchange_edges ∧ a ≠ b))def in732_tris : List (Fin 10 × Fin 10 × Fin 10) := [(0, 1, 2), (0, 1, 3), (0, 1, 7), (0, 2, 3), (0, 2, 7), (0, 2, 8), (0, 2, 9), (0, 3, 6), (0, 3, 7), (0, 3, 9), (0, 6, 7), (0, 6, 8), (0, 6, 9), (0, 7, 8), (0, 8, 9), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 7), (1, 3, 4), (1, 3, 5), (1, 3, 7), (1, 4, 5), (1, 4, 7), (2, 3, 4), (2, 3, 5), (2, 3, 7), (2, 3, 9), (2, 4, 5), (2, 4, 7), (2, 4, 8), (2, 5, 8), (2, 5, 9), (2, 7, 8), (2, 8, 9), (3, 4, 5), (3, 4, 6), (3, 4, 7), (3, 5, 6), (3, 5, 9), (3, 6, 7), (3, 6, 9), (4, 5, 6), (4, 5, 8), (4, 6, 7), (4, 6, 8), (4, 7, 8), (5, 6, 8), (5, 6, 9), (5, 8, 9), (6, 7, 8), (6, 8, 9)]def in732_enc (x : Fin 10 × Fin 10 × Fin 10) : Finset (Sym2 (Fin 10)) := {s(x.1,x.2.1),s(x.1,x.2.2),s(x.2.1,x.2.2)}def in732_sort3 (a b c : Fin 10) : Fin 10 × Fin 10 × Fin 10 := 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 in732_sort_mem (a : Fin 10) : ∀ b c : Fin 10, ten_vertex_exchange_graph.Adj a b → ten_vertex_exchange_graph.Adj a c → ten_vertex_exchange_graph.Adj b c → in732_sort3 a b c ∈ in732_tris := by fin_cases a <;> decidetheorem in732_enc_sort3 (a b c : Fin 10) : in732_enc (in732_sort3 a b c) = {s(a,b),s(a,c),s(b,c)} := by unfold in732_sort3 in732_enc split_ifs <;> ext e <;> simp only [Finset.mem_insert, Finset.mem_singleton] <;> constructor <;> rintro (h | h | h) <;> subst h <;> simp [Sym2.eq_swap]theorem in732_list_tri : ∀ x ∈ in732_tris, x.1 < x.2.1 ∧ x.2.1 < x.2.2 ∧ ten_vertex_exchange_graph.Adj x.1 x.2.1 ∧ ten_vertex_exchange_graph.Adj x.1 x.2.2 ∧ ten_vertex_exchange_graph.Adj x.2.1 x.2.2 := by intro x hx simp only [in732_tris, List.mem_cons, List.mem_singleton, List.not_mem_nil, or_false] at hx rcases hx with h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h <;> subst x <;> decidetheorem in732_list_family : (in732_tris.map in732_enc).toFinset = ten_vertex_exchange_family := by decideend In732Familyopen In732Familytheorem ten_vertex_exchange_family_eq : simple_graph_triangle_edge_family ten_vertex_exchange_graph = ten_vertex_exchange_family := by classical rw [← in732_list_family] ext t rw [simple_graph_triangle_edge_family_mem] simp only [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 ⟨_, in732_sort_mem a b c h1 h2 h3, by rw [in732_enc_sort3, ts18_fvsee_triple a b c hab hac hbc]⟩ · rintro ⟨x,hx,rfl⟩ obtain ⟨l1,l2,h1,h2,h3⟩ := in732_list_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