AFTD Auto-Formalizing Theoretical Domains

simple_graph_stable_unforced_anchor_ten_example

theoremverified

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

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.

  1. 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.

    lines 4–11

    uses Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, List.mem_toFinset, sharp_clique_mem, sharp_T_clique

      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⟩
  2. 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.

    line 17

    theorem sharp_bad_cliques : ∀ t ∈ sharp_bad_P, sharp_G.IsNClique 3 t := by decide +kernel
  3. 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.

    line 20

    theorem sharp_bad_disjoint : (sharp_bad_P : Set (Finset (Fin 10))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kernel
  4. 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.

    line 22

    theorem sharp_bad_support : sharp_bad_P.biUnion id = Finset.univ := by decide +kernel
  5. The collection sharp_bad_P consists of exactly 8 triangles automation

    Verified by kernel evaluation of the cardinality of the explicit finset.

    line 24

    theorem sharp_bad_card : sharp_bad_P.card = 8 := by decide +kernel
  6. 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.

    lines 30–31

    uses sharp_family

      rw [sharp_family]
      decide +kernel
  7. 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.

    lines 38–39

    uses sharp_family

      rw [sharp_family]
      decide +kernel
  8. 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.

    line 42

    theorem sharp_bad_k4 : sharp_G.IsNClique 4 ({1,2,8,9} : Finset (Fin 10)) := by decide +kernel
  9. 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.

    lines 45–48

    uses sharp_G, sharp_bad_cliques, sharp_bad_disjoint, sharp_bad_support, sharp_stable, sharp_bad_k4, sharp_bad_forced, sharp_bad_anchor_unforced

      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⟩
  10. 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.

    lines 49–50

    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]
  11. 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.

    line 51

      · decide +kernel
  12. There 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.

    line 52

      · 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

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⟩
See it in the graphDiscuss this resultChallenge it