simple_graph_stable_unforced_anchor_ten_example
A two-edge-stable graph has a full-support maximum packing with a fully forced K4 face whose internal anchor lies only in unforced packed triangles.
Statement
theorem simple_graph_stable_unforced_anchor_ten_example : let P : Finset (Finset (Fin 10)) := {{0,1,5},{0,2,3},{2,8,9},{2,6,7},{3,7,8},{5,6,8},{3,6,9},{4,5,9}}; ∃ G : SimpleGraph (Fin 10), (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin 10))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G ∧ P.biUnion id = Finset.univ ∧ (∀ e f : Sym2 (Fin 10), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) ∧ G.IsNClique 4 ({1,2,8,9} : Finset (Fin 10)) ∧ ({2,8,9} : Finset (Fin 10)) ∈ P ∧ finite_vertex_set_edge_encoding ({2,8,9} : Finset (Fin 10)) ⊆ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) ∧ (∃ q ∈ P, (1 : Fin 10) ∈ q) ∧ (∀ q ∈ P, (1 : Fin 10) ∈ q → Disjoint (finite_vertex_set_edge_encoding q) (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id))
- Source
- Concrete ten-vertex example from experiments 20301–20303, 20312 and 20378; see state/campaigns/triangle_reductions/private_k4_in694.md. Related forced-triangle structure is in https://arxiv.org/abs/2001.00257, Section 3. Literature checked 2026-11-10.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- simple_graph_in693_ten_seed_packing_numberThe concrete ten-vertex five-link seed has triangle packing number eight.
- simple_graph_in693_ten_seed_pair_stableDeleting any two distinct edges of the ten-vertex seed leaves its triangle packing number equal to eight.
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
The proof, explained
The theorem establishes the existence of a 2-edge-stable graph with a full-support maximum triangle packing containing a fully forced K4 face whose internal anchor vertex belongs only to unforced triangles. The proof proceeds by providing an explicit 10-vertex graph sharp_G and an 8-triangle packing sharp_bad_P. Auxiliary lemmas, largely verified by finite kernel computation after rewriting the triangle edge family to an explicit list, establish that sharp_bad_P is a pairwise edge-disjoint full-support packing of size 8, that sharp_G is 2-edge-stable with packing number 8, that {1, 2, 8, 9} is a K4 containing {2, 8, 9} as a fully forced face, and that every packed triangle containing the anchor vertex 1 is unforced.
The triangle edge family of sharp_G equals the edge encodings of the triangles listed in sharp_T
We apply extensionality to show that an edge set belongs to the triangle edge family of sharp_G if and only if it is the edge encoding of some triangle in the list sharp_T. Simplifying the set memberships reduces this to two inclusions: any 3-clique of sharp_G is in sharp_T by sharp_clique_mem, and any element of sharp_T is a 3-clique in sharp_G by sharp_T_clique.
uses
Finset.mem_image,Finset.mem_filter,Finset.mem_univ,true_and,List.mem_toFinset,sharp_clique_mem,sharp_T_cliqueclassical ext x simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, List.mem_toFinset] constructor · rintro ⟨t, ht, rfl⟩ exact ⟨t, sharp_clique_mem ht, rfl⟩ · rintro ⟨t, ht, rfl⟩ exact ⟨t, sharp_T_clique t ht, rfl⟩
All eight sets in sharp_bad_P are 3-cliques in sharp_G automation
Verified by exhaustive kernel computation for each of the eight 3-element sets in sharp_bad_P.
theorem sharp_bad_cliques : ∀ t ∈ sharp_bad_P, sharp_G.IsNClique 3 t := by decide +kernel
The triangles in sharp_bad_P are pairwise edge-disjoint automation
Verified by exhaustive kernel computation that any two distinct triangles in sharp_bad_P intersect in at most one vertex.
theorem sharp_bad_disjoint : (sharp_bad_P : Set (Finset (Fin 10))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kernel
The union of triangles in sharp_bad_P spans all 10 vertices automation
Verified by kernel computation that the union of vertices of the eight triangles equals Finset.univ for Fin 10.
theorem sharp_bad_support : sharp_bad_P.biUnion id = Finset.univ := by decide +kernel
The collection sharp_bad_P consists of exactly 8 triangles automation
Verified by kernel evaluation of the cardinality of the explicit finset.
theorem sharp_bad_card : sharp_bad_P.card = 8 := by decide +kernel
The triangle {2, 8, 9} in sharp_bad_P is fully forced automation
Rewriting the triangle edge family with sharp_family enables the kernel to verify by direct evaluation that every edge of {2, 8, 9} is covered by triangles in sharp_G that meet the packing sharp_bad_P in exactly one edge.
uses
sharp_familyrw [sharp_family] decide +kernel
Every triangle in sharp_bad_P containing vertex 1 is unforced automation
Rewriting with sharp_family allows the kernel to verify that any triangle in sharp_bad_P containing vertex 1 shares no edges with any triangle in sharp_G intersecting the packing in exactly one edge.
uses
sharp_familyrw [sharp_family] decide +kernel
The subset {1, 2, 8, 9} forms a 4-clique (K4) in sharp_G automation
Verified by exhaustive kernel computation that all pairs among {1, 2, 8, 9} are edges in sharp_G.
theorem sharp_bad_k4 : sharp_G.IsNClique 4 ({1,2,8,9} : Finset (Fin 10)) := by decide +kernel
Provide sharp_G as the witness graph and assemble the verified properties
We instantiate the existential quantifier with sharp_G. Using the previously established lemmas sharp_bad_cliques, sharp_bad_disjoint, sharp_bad_support, sharp_stable, sharp_bad_k4, sharp_bad_forced, and sharp_bad_anchor_unforced, we discharge all goals except the packing size equality, the membership of {2, 8, 9} in P, and the existence of a triangle containing vertex 1.
uses
sharp_G,sharp_bad_cliques,sharp_bad_disjoint,sharp_bad_support,sharp_stable,sharp_bad_k4,sharp_bad_forced,sharp_bad_anchor_unforcedclassical dsimp only refine ⟨sharp_G, sharp_bad_cliques, sharp_bad_disjoint, ?_, sharp_bad_support, sharp_stable, sharp_bad_k4, ?_, sharp_bad_forced, ?_, sharp_bad_anchor_unforced⟩
The packing sharp_bad_P is maximum, with cardinality equal to the packing number of sharp_G
Changing the goal to sharp_bad_P.card = simple_graph_triangle_packing_number sharp_G and rewriting with sharp_bad_card (which gives 8) and sharp_pack_eq (which shows the packing number of sharp_G is 8) reduces the goal to 8 = 8.
uses
sharp_bad_card,sharp_pack_eq· change sharp_bad_P.card = simple_graph_triangle_packing_number sharp_G rw [sharp_bad_card, sharp_pack_eq]
The triangle {2, 8, 9} belongs to P automation
Verified by kernel evaluation that {2, 8, 9} is an element of the explicit set P.
· decide +kernelThere is a triangle in P containing vertex 1 automation
Witnessed by the triangle {0, 1, 5}, whose membership in P and inclusion of 1 are both verified by the kernel.
· exact ⟨{0,1,5}, by decide +kernel, by decide +kernel⟩
true_and- A proposition p and True is logically equivalent to p
Finset.mem_image- Characterizes membership in the image of a finset under a function
Finset.mem_filter- Characterizes membership in a filtered finset by the predicate
Finset.mem_univ- Every element of a finite type belongs to its universal finset
List.mem_toFinset- Characterizes membership in the finset conversion of a list
sharp_clique_mem- Every triangle (3-clique) in the graph sharp_G belongs to the explicit list sharp_T
sharp_T_clique- Every element in the list sharp_T is a triangle (3-clique) in sharp_G
sharp_family- The edge family of triangles in sharp_G is the image of sharp_T under edge-encoding
sharp_bad_cliques- Every triangle in the packing sharp_bad_P is a 3-clique in sharp_G
sharp_bad_disjoint- The triangles in sharp_bad_P are pairwise edge-disjoint
sharp_bad_support- The union of the triangles in sharp_bad_P covers all 10 vertices
sharp_G- The graph sharp_G on 10 vertices
sharp_stable- The graph sharp_G is 2-edge-stable: deleting any two distinct edges does not reduce its triangle packing number
sharp_bad_k4- The vertex set {1, 2, 8, 9} forms a 4-clique (K4) in sharp_G
sharp_bad_forced- The triangle {2, 8, 9} is fully forced by triangles sharing exactly one edge with the packing sharp_bad_P
sharp_bad_anchor_unforced- Every triangle in sharp_bad_P containing vertex 1 is unforced
sharp_bad_card- The triangle packing sharp_bad_P contains exactly 8 triangles
sharp_pack_eq- The triangle packing number of sharp_G equals 8
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.
open scoped Sym2lemma sharp_family : simple_graph_triangle_edge_family sharp_G = sharp_T.toFinset.image finite_vertex_set_edge_encoding := by classical ext x simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, List.mem_toFinset] constructor · rintro ⟨t, ht, rfl⟩ exact ⟨t, sharp_clique_mem ht, rfl⟩ · rintro ⟨t, ht, rfl⟩ exact ⟨t, sharp_T_clique t ht, rfl⟩def sharp_bad_P : Finset (Finset (Fin 10)) := {{0,1,5},{0,2,3},{2,8,9},{2,6,7},{3,7,8},{5,6,8},{3,6,9},{4,5,9}}set_option maxRecDepth 100000 inset_option maxHeartbeats 30000000 intheorem sharp_bad_cliques : ∀ t ∈ sharp_bad_P, sharp_G.IsNClique 3 t := by decide +kernelset_option maxRecDepth 100000 inset_option maxHeartbeats 30000000 intheorem sharp_bad_disjoint : (sharp_bad_P : Set (Finset (Fin 10))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kernelset_option maxRecDepth 100000 intheorem sharp_bad_support : sharp_bad_P.biUnion id = Finset.univ := by decide +kernelset_option maxRecDepth 100000 intheorem sharp_bad_card : sharp_bad_P.card = 8 := by decide +kernelset_option maxRecDepth 100000 inset_option maxHeartbeats 30000000 intheorem sharp_bad_forced : finite_vertex_set_edge_encoding ({2,8,9} : Finset (Fin 10)) ⊆ (((simple_graph_triangle_edge_family sharp_G).filter (fun t => (t ∩ sharp_bad_P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) := by rw [sharp_family] decide +kernelset_option maxRecDepth 100000 inset_option maxHeartbeats 30000000 intheorem sharp_bad_anchor_unforced : ∀ q ∈ sharp_bad_P, (1 : Fin 10) ∈ q → Disjoint (finite_vertex_set_edge_encoding q) (((simple_graph_triangle_edge_family sharp_G).filter (fun t => (t ∩ sharp_bad_P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) := by rw [sharp_family] decide +kernelset_option maxRecDepth 100000 inset_option maxHeartbeats 30000000 intheorem sharp_bad_k4 : sharp_G.IsNClique 4 ({1,2,8,9} : Finset (Fin 10)) := by decide +kerneltheorem simple_graph_stable_unforced_anchor_ten_example : let P : Finset (Finset (Fin 10)) := {{0,1,5},{0,2,3},{2,8,9},{2,6,7},{3,7,8},{5,6,8},{3,6,9},{4,5,9}}; ∃ G : SimpleGraph (Fin 10), (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin 10))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G ∧ P.biUnion id = Finset.univ ∧ (∀ e f : Sym2 (Fin 10), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) ∧ G.IsNClique 4 ({1,2,8,9} : Finset (Fin 10)) ∧ ({2,8,9} : Finset (Fin 10)) ∈ P ∧ finite_vertex_set_edge_encoding ({2,8,9} : Finset (Fin 10)) ⊆ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) ∧ (∃ q ∈ P, (1 : Fin 10) ∈ q) ∧ (∀ q ∈ P, (1 : Fin 10) ∈ q → Disjoint (finite_vertex_set_edge_encoding q) (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)) := by classical dsimp only refine ⟨sharp_G, sharp_bad_cliques, sharp_bad_disjoint, ?_, sharp_bad_support, sharp_stable, sharp_bad_k4, ?_, sharp_bad_forced, ?_, sharp_bad_anchor_unforced⟩ · change sharp_bad_P.card = simple_graph_triangle_packing_number sharp_G rw [sharp_bad_card, sharp_pack_eq] · decide +kernel · exact ⟨{0,1,5}, by decide +kernel, by decide +kernel⟩