simple_graph_in693_ten_seed_pair_stable
Deleting any two distinct edges of the ten-vertex seed leaves its triangle packing number equal to eight.
Statement
theorem simple_graph_in693_ten_seed_pair_stable : ∀ e f : Sym2 (Fin 10), e ∈ sharp_G.edgeSet → f ∈ sharp_G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (sharp_G.deleteEdges {e,f}) = simple_graph_triangle_packing_number sharp_G- Source
- Fifty-four finite packing witnesses in experiment 20303; the Lean kernel checks their coverage and disjointness.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 16
- simple_graph_in693_ten_seed_packing_numberThe concrete ten-vertex five-link seed has triangle packing number eight.
- 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).
- in715_sharp_witness_countFinite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wok0Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wok1Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wok2Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wok3Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wok4Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wok5Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wcover0Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wcover1Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wcover2Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wcover3Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wcover4Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wcover5Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wcover6Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- Used by 1
- simple_graph_stable_unforced_anchor_ten_exampleA two-edge-stable graph has a full-support maximum packing with a fully forced K4 face whose internal anchor lies only in unforced packed…
The proof, explained
The theorem states that deleting any two distinct edges e, f from the ten-vertex seed graph sharp_G preserves its triangle packing number ν(G) = 8. To establish this, a precomputed certificate table sharp_W provides families of eight edge-disjoint triangles alongside the edges they avoid. For any given pair of edges e and f, a covering lemma finds a certificate packing avoiding both, certifying that ν(G \\ {e, f}) ≥ 8, while subgraph monotonicity and the upper bound ν(G) ≤ 8 ensure the packing number cannot exceed 8.
Every candidate certificate packing in sharp_W consists of 8 valid, pairwise edge-disjoint triangles in sharp_G that avoid its specified edge set
The list sharp_W is the concatenation of six smaller certificate lists (in715_W0 through in715_W5). Unpacking membership across concatenations via List.mem_append.mp yields six subcases, each closed by the corresponding computational verification lemma in715_Wok0 through in715_Wok5.
uses
List.mem_append.mp,in715_Wok0,in715_Wok1,in715_Wok2,in715_Wok3,in715_Wok4,in715_Wok5intro q h change q ∈ in715_W0 ++ in715_W1 ++ in715_W2 ++ in715_W3 ++ in715_W4 ++ in715_W5 at h rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · exact in715_Wok0 q h · exact in715_Wok1 q h · exact in715_Wok2 q h · exact in715_Wok3 q h · exact in715_Wok4 q h · exact in715_Wok5 q h
For any two edges e, f in sharp_EL, there exists a certificate packing q in sharp_W avoiding both e and f automation
The 35 edges in sharp_EL are partitioned into seven blocks of size five (verified by kernel computation via decide +kernel). Case analysis on which block contains e dispatches the goal via precomputed block-coverage lemmas in715_Wcover0 through in715_Wcover6.
uses
List.mem_append.mp,in715_Wcover0,in715_Wcover1,in715_Wcover2,in715_Wcover3,in715_Wcover4,in715_Wcover5,in715_Wcover6intro e he f hf have hsplit : sharp_EL = (sharp_EL.drop 0).take 5 ++ (sharp_EL.drop 5).take 5 ++ (sharp_EL.drop 10).take 5 ++ (sharp_EL.drop 15).take 5 ++ (sharp_EL.drop 20).take 5 ++ (sharp_EL.drop 25).take 5 ++ (sharp_EL.drop 30).take 5 := by decide +kernel have h : e ∈ (sharp_EL.drop 0).take 5 ++ (sharp_EL.drop 5).take 5 ++ (sharp_EL.drop 10).take 5 ++ (sharp_EL.drop 15).take 5 ++ (sharp_EL.drop 20).take 5 ++ (sharp_EL.drop 25).take 5 ++ (sharp_EL.drop 30).take 5 := hsplit ▸ he rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · exact in715_Wcover0 e h f hf · exact in715_Wcover1 e h f hf · exact in715_Wcover2 e h f hf · exact in715_Wcover3 e h f hf · exact in715_Wcover4 e h f hf · exact in715_Wcover5 e h f hf · exact in715_Wcover6 e h f hf
Every edge in the edge set of sharp_G belongs to the list sharp_EL
By induction on unordered pairs via Sym2.ind, any edge is of the form s(a, b). By definition of sharp_G.edgeSet, the pair belongs to sharp_E, which translates to membership in the list sharp_EL via List.mem_toFinset.mp.
uses
Sym2.ind,SimpleGraph.mem_edgeSet,List.mem_toFinset.mpinduction g using Sym2.ind with | _ a b => have h1 := ((SimpleGraph.mem_edgeSet sharp_G).mp h).1 exact List.mem_toFinset.mp h1
A 3-clique in sharp_G remains a 3-clique in G \\ {e, f} if neither e nor f is an edge of the clique
The triangle retains 3 vertices. For any two distinct vertices in the triangle, their joining edge was present in sharp_G. If it were e or f, both endpoints of that edge would belong to the triangle, directly contradicting the hypothesis that neither e nor f has all its vertices in the triangle.
uses
SimpleGraph.deleteEdges_adj,Set.mem_insert_iff,Set.mem_singleton_iff,Sym2.mem_iff.mprefine ⟨?_, h.card_eq⟩ intro a ha b hb hab refine (SimpleGraph.deleteEdges_adj).mpr ⟨h.isClique ha hb hab, ?_⟩ intro hmem simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hmem rcases hmem with hmem | hmem · apply he rw [← hmem] intro x hx rcases Sym2.mem_iff.mp hx with rfl | rfl <;> assumption · apply hf rw [← hmem] intro x hx rcases Sym2.mem_iff.mp hx with rfl | rfl <;> assumption
To show ν(G \\ {e, f}) = ν(G), it suffices to exhibit a packing of size 8 in G \\ {e, f} and bound all packings by 8
We rewrite ν(G) = 8 via sharp_pack_eq. Using sharp_W_cover, we obtain a certificate q avoiding both e and f, which has 8 triangles by sharp_W_ok. Characterizing the packing number as the supremum of sizes of edge-disjoint triangle packings via IsGreatest.csSup_eq, it suffices to show that the 8 triangles remain cliques in G \\ {e, f}, remain edge-disjoint, and that no packing can exceed 8.
uses
sharp_pack_eq,sharp_W_cover,sharp_edge_mem,sharp_W_ok,IsGreatest.csSup_eqintro e f he hf hne rw [sharp_pack_eq] obtain ⟨q, hq, hqe, hqf⟩ := sharp_W_cover e (sharp_edge_mem he) f (sharp_edge_mem hf) obtain ⟨hc, ht, hp, hav⟩ := sharp_W_ok q hq unfold simple_graph_triangle_packing_number refine IsGreatest.csSup_eq ⟨⟨q.2.toFinset, ?_, ?_, hc⟩, ?_⟩
Every triangle in the chosen certificate packing remains a 3-clique in G \\ {e, f}
Each triangle t in q.2 is a 3-clique in sharp_G by sharp_T_clique. Since q avoids e and f (from sharp_W_ok), neither e nor f is an edge of t, so sharp_del_clique applies.
uses
List.mem_toFinset.mp,sharp_del_clique,sharp_T_clique,Finset.mem_sym2_iff.mpr· intro t ht' have ht'' := List.mem_toFinset.mp ht' apply sharp_del_clique (sharp_T_clique t (ht t ht'')) · intro h; exact hav e hqe t ht'' (Finset.mem_sym2_iff.mpr h) · intro h; exact hav f hqf t ht'' (Finset.mem_sym2_iff.mpr h)
The triangles in the chosen certificate packing remain pairwise edge-disjoint
Any two distinct triangles in q.2 share at most one vertex, which directly transfers from the edge-disjointness property guaranteed by sharp_W_ok.
uses
List.mem_toFinset.mp,Finset.mem_coe.mp· intro a ha b hb hab exact hp a (List.mem_toFinset.mp (Finset.mem_coe.mp ha)) b (List.mem_toFinset.mp (Finset.mem_coe.mp hb)) hab
No triangle packing in G \\ {e, f} can have size greater than 8
Since G \\ {e, f} is a subgraph of sharp_G (by SimpleGraph.deleteEdges_le), any 3-clique in G \\ {e, f} is also a 3-clique in sharp_G. Therefore, any packing in the edge-deleted graph is a valid packing in sharp_G, and sharp_nu_le bounds its size by 8.
uses
sharp_nu_le,SimpleGraph.deleteEdges_le· rintro k ⟨T, hT, hP, rfl⟩ exact sharp_nu_le T (fun t ht' => (hT t ht').mono (SimpleGraph.deleteEdges_le _)) hP
Deleting any two distinct edges from the seed graph leaves its triangle packing number unchanged
This is immediate from the theorem sharp_stable established directly above.
uses
sharp_stabletheorem simple_graph_in693_ten_seed_pair_stable : ∀ e f : Sym2 (Fin 10), e ∈ sharp_G.edgeSet → f ∈ sharp_G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (sharp_G.deleteEdges {e,f}) = simple_graph_triangle_packing_number sharp_G := by exact sharp_stable
List.mem_append.mp- An element belonging to the concatenation of two lists belongs to the first list or the second list.
in715_Wok0- Every candidate in chunk 0 of certificate packings consists of 8 edge-disjoint triangles in sharp_T avoiding its associated edge set.
in715_Wok1- Every candidate in chunk 1 of certificate packings consists of 8 edge-disjoint triangles in sharp_T avoiding its associated edge set.
in715_Wok2- Every candidate in chunk 2 of certificate packings consists of 8 edge-disjoint triangles in sharp_T avoiding its associated edge set.
in715_Wok3- Every candidate in chunk 3 of certificate packings consists of 8 edge-disjoint triangles in sharp_T avoiding its associated edge set.
in715_Wok4- Every candidate in chunk 4 of certificate packings consists of 8 edge-disjoint triangles in sharp_T avoiding its associated edge set.
in715_Wok5- Every candidate in chunk 5 of certificate packings consists of 8 edge-disjoint triangles in sharp_T avoiding its associated edge set.
in715_Wcover0- For any edge in the first 5 elements of sharp_EL and any edge in sharp_EL, there is a certificate packing avoiding both.
in715_Wcover1- For any edge in elements 5 through 9 of sharp_EL and any edge in sharp_EL, there is a certificate packing avoiding both.
in715_Wcover2- For any edge in elements 10 through 14 of sharp_EL and any edge in sharp_EL, there is a certificate packing avoiding both.
in715_Wcover3- For any edge in elements 15 through 19 of sharp_EL and any edge in sharp_EL, there is a certificate packing avoiding both.
in715_Wcover4- For any edge in elements 20 through 24 of sharp_EL and any edge in sharp_EL, there is a certificate packing avoiding both.
in715_Wcover5- For any edge in elements 25 through 29 of sharp_EL and any edge in sharp_EL, there is a certificate packing avoiding both.
in715_Wcover6- For any edge in elements 30 through 34 of sharp_EL and any edge in sharp_EL, there is a certificate packing avoiding both.
Sym2.ind- Principle of induction for unordered pairs: any property that holds for all pairs s(x, y) holds for all elements of Sym2.
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) belongs to the edge set of a graph if and only if v and w are adjacent.
List.mem_toFinset.mp- If an element belongs to the finset of a list, then it belongs to the list.
SimpleGraph.deleteEdges_adj- Two vertices are adjacent in G \\ s if and only if they are adjacent in G and their connecting edge is not in s.
Set.mem_insert_iff- An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff- An element belongs to {b} if and only if it equals b.
Sym2.mem_iff.mp- If an element belongs to the unordered pair s(a, b), it equals a or b.
sharp_pack_eq- The triangle packing number of sharp_G is equal to 8.
sharp_W_cover- For any two edges e, f in sharp_EL, there is a certificate packing q in sharp_W whose edge set contains both e and f.
sharp_edge_mem- Every edge in the edge set of sharp_G belongs to the edge list sharp_EL.
sharp_W_ok- Every certificate q in sharp_W provides 8 pairwise edge-disjoint triangles in sharp_G that avoid all edges in q.1.
IsGreatest.csSup_eq- If an element is the greatest element of a set, then the supremum of that set is equal to that element.
sharp_del_clique- A triangle in sharp_G remains a triangle in G \\ {e, f} provided neither e nor f has both endpoints in the triangle.
sharp_T_clique- Every triangle in the list sharp_T is a 3-clique in sharp_G.
Finset.mem_sym2_iff.mpr- If both endpoints of an unordered pair belong to a finset, then the unordered pair belongs to the symmetric square of that finset.
Finset.mem_coe.mp- Membership in the coercion of a finset to a set is equivalent to membership in the finset.
sharp_nu_le- Any pairwise edge-disjoint collection of triangles in sharp_G has cardinality at most 8.
SimpleGraph.deleteEdges_le- Deleting a set of edges produces a subgraph of the original graph.
sharp_stable- Deleting any two distinct edges from sharp_G preserves its triangle packing number.
- The verification that the edge list sharp_EL splits into seven chunks and that the precomputed certificate packings cover all pairs of edges relies on finite computational reflection (decide +kernel), structured in chunks to stay within Lean's heartbeat and recursion depth limits.
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 Sym2set_option maxRecDepth 100000set_option maxHeartbeats 30000000theorem sharp_W_ok : ∀ q ∈ sharp_W, q.2.toFinset.card = 8 ∧ (∀ t ∈ q.2, t ∈ sharp_T) ∧ (∀ a ∈ q.2, ∀ b ∈ q.2, a ≠ b → (a ∩ b).card ≤ 1) ∧ (∀ e ∈ q.1, ∀ t ∈ q.2, e ∉ t.sym2) := by intro q h change q ∈ in715_W0 ++ in715_W1 ++ in715_W2 ++ in715_W3 ++ in715_W4 ++ in715_W5 at h rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · exact in715_Wok0 q h · exact in715_Wok1 q h · exact in715_Wok2 q h · exact in715_Wok3 q h · exact in715_Wok4 q h · exact in715_Wok5 q htheorem sharp_W_cover : ∀ e ∈ sharp_EL, ∀ f ∈ sharp_EL, ∃ q ∈ sharp_W, e ∈ q.1 ∧ f ∈ q.1 := by intro e he f hf have hsplit : sharp_EL = (sharp_EL.drop 0).take 5 ++ (sharp_EL.drop 5).take 5 ++ (sharp_EL.drop 10).take 5 ++ (sharp_EL.drop 15).take 5 ++ (sharp_EL.drop 20).take 5 ++ (sharp_EL.drop 25).take 5 ++ (sharp_EL.drop 30).take 5 := by decide +kernel have h : e ∈ (sharp_EL.drop 0).take 5 ++ (sharp_EL.drop 5).take 5 ++ (sharp_EL.drop 10).take 5 ++ (sharp_EL.drop 15).take 5 ++ (sharp_EL.drop 20).take 5 ++ (sharp_EL.drop 25).take 5 ++ (sharp_EL.drop 30).take 5 := hsplit ▸ he rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · rcases List.mem_append.mp h with h | h · exact in715_Wcover0 e h f hf · exact in715_Wcover1 e h f hf · exact in715_Wcover2 e h f hf · exact in715_Wcover3 e h f hf · exact in715_Wcover4 e h f hf · exact in715_Wcover5 e h f hf · exact in715_Wcover6 e h f hflemma sharp_edge_mem {g : Sym2 (Fin 10)} (h : g ∈ sharp_G.edgeSet) : g ∈ sharp_EL := by induction g using Sym2.ind with | _ a b => have h1 := ((SimpleGraph.mem_edgeSet sharp_G).mp h).1 exact List.mem_toFinset.mp h1lemma sharp_del_clique {t : Finset (Fin 10)} {e f : Sym2 (Fin 10)} (h : sharp_G.IsNClique 3 t) (he : ¬ ∀ x ∈ e, x ∈ t) (hf : ¬ ∀ x ∈ f, x ∈ t) : (sharp_G.deleteEdges {e,f}).IsNClique 3 t := by refine ⟨?_, h.card_eq⟩ intro a ha b hb hab refine (SimpleGraph.deleteEdges_adj).mpr ⟨h.isClique ha hb hab, ?_⟩ intro hmem simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hmem rcases hmem with hmem | hmem · apply he rw [← hmem] intro x hx rcases Sym2.mem_iff.mp hx with rfl | rfl <;> assumption · apply hf rw [← hmem] intro x hx rcases Sym2.mem_iff.mp hx with rfl | rfl <;> assumptiontheorem sharp_stable : ∀ e f : Sym2 (Fin 10), e ∈ sharp_G.edgeSet → f ∈ sharp_G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (sharp_G.deleteEdges {e,f}) = simple_graph_triangle_packing_number sharp_G := by intro e f he hf hne rw [sharp_pack_eq] obtain ⟨q, hq, hqe, hqf⟩ := sharp_W_cover e (sharp_edge_mem he) f (sharp_edge_mem hf) obtain ⟨hc, ht, hp, hav⟩ := sharp_W_ok q hq unfold simple_graph_triangle_packing_number refine IsGreatest.csSup_eq ⟨⟨q.2.toFinset, ?_, ?_, hc⟩, ?_⟩ · intro t ht' have ht'' := List.mem_toFinset.mp ht' apply sharp_del_clique (sharp_T_clique t (ht t ht'')) · intro h; exact hav e hqe t ht'' (Finset.mem_sym2_iff.mpr h) · intro h; exact hav f hqf t ht'' (Finset.mem_sym2_iff.mpr h) · intro a ha b hb hab exact hp a (List.mem_toFinset.mp (Finset.mem_coe.mp ha)) b (List.mem_toFinset.mp (Finset.mem_coe.mp hb)) hab · rintro k ⟨T, hT, hP, rfl⟩ exact sharp_nu_le T (fun t ht' => (hT t ht').mono (SimpleGraph.deleteEdges_le _)) hPtheorem simple_graph_in693_ten_seed_pair_stable : ∀ e f : Sym2 (Fin 10), e ∈ sharp_G.edgeSet → f ∈ sharp_G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (sharp_G.deleteEdges {e,f}) = simple_graph_triangle_packing_number sharp_G := by exact sharp_stable