simple_graph_in693_ten_seed_packing_number
The concrete ten-vertex five-link seed has triangle packing number eight.
Statement
theorem simple_graph_in693_ten_seed_packing_number : simple_graph_triangle_packing_number sharp_G = 8- Source
- Ten-vertex graph in experiment 20303. Kernel-checked finite maximum-packing computation; no novelty claim.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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).
- 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.
- Used by 19
- 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_maximum_packing_fixed_two_budget_counterexampleA nine-vertex graph has a maximum triangle packing with at most one singleton-forced edge per packed triangle, but no triangle cover…
- in715_Wok3Finite 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_Wcover3Finite 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_sharp_witness_countFinite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wok5Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- simple_graph_pair_stable_support_max_incidence_two_bad_packing_counterexampleThere is an eight-vertex two-edge-stable graph with a maximum triangle packing covering every vertex, in which every vertex belongs to at…
- 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…
- in715_Wok2Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wcover6Finite 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_Wok4Finite 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_Wcover5Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- in715_Wcover1Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
- simple_graph_pair_stable_triangle_active_incidence_two_unpacked_nonbipartiteThere is a triangle-active two-edge-stable eight-vertex graph with a support-maximal maximum triangle packing in which every vertex is in…
- in715_Wcover4Finite verification of the explicit ten-vertex packing and edge-avoidance witnesses.
The proof, explained
The triangle packing number of a graph is the maximum size of a family of pairwise edge-disjoint triangles (3-cliques). To prove that this packing number is eight for the concrete ten-vertex graph sharp_G, the proof establishes matching lower and upper bounds. The lower bound is certified by an explicit collection sharp_P of eight edge-disjoint triangles verified by kernel computation. The upper bound is established by proving the correctness of a recursive branch-and-bound search algorithm (in693_maxC) by induction, then evaluating it via the kernel on the complete list of 36 triangles in sharp_G to confirm that no edge-disjoint subcollection can have size greater than eight.
When the length bound is zero, any compatible subset S drawn from the list has cardinality at most in693_maxC c 0 l = 0.
Since the length of l is at most 0, l must be the empty list by List.length_eq_zero_iff.mp. Every element of S must belong to l = [], so S has no elements, which means S = ∅ by Finset.eq_empty_of_forall_notMem. Thus |S| = 0, matching the definition in693_maxC c 0 [] = 0.
uses
List.length_eq_zero_iff.mp,Finset.eq_empty_of_forall_notMemintro n induction n with | zero => intro l hl S hS _ have hl0 : l = [] := List.length_eq_zero_iff.mp (by omega) subst hl0 have : S = ∅ := Finset.eq_empty_of_forall_notMem (fun a ha => by simpa using hS a ha) simp [this, in693_maxC]
In the inductive step, if the list of candidates is empty, any compatible subset S has cardinality at most in693_maxC c (n + 1) [] = 0.
When l = [], every element of S must belong to the empty list, which implies S = ∅ by Finset.eq_empty_of_forall_notMem. The cardinality |S| = 0 is bounded by in693_maxC c (n + 1) [] = 0.
uses
Finset.eq_empty_of_forall_notMem| succ n ih => intro l hl S hS hc match l, hl, hS with | [], _, hS => have : S = ∅ := Finset.eq_empty_of_forall_notMem (fun a ha => by simpa using hS a ha) simp [this, in693_maxC] | t :: l, hl, hS =>In the inductive step with list t :: l, if t ∈ S, then |S| is bounded by the branching step 1 + in693_maxC c n (l.filter (c t)).
Removing t from S gives S \ {t}. Since every element a ∈ S \ {t} belongs to t :: l and a ≠ t, a must belong to l by List.mem_cons.mp. Pairwise compatibility of S ensures that c t a = true, so a belongs to l.filter (c t) by List.mem_filter.mpr. The length of this filtered list is at most n (by List.length_filter_le and List.length_cons), so the induction hypothesis applies to S \ {t}. Finally, |S| = |S \ {t}| + 1 by Finset.card_erase_add_one, and the bound follows by le_max_right and transitivity (le_trans).
uses
le_trans,le_max_right,Finset.mem_erase.mp,List.mem_cons.mp,List.mem_filter.mpr,Ne.symm,List.length_filter_le,List.length_cons,Finset.card_erase_add_onerw [in693_maxC] by_cases ht : t ∈ S · refine le_trans ?_ (le_max_right _ _) have hsub : ∀ a ∈ S.erase t, a ∈ l.filter (c t) := by intro a ha have hne : a ≠ t := (Finset.mem_erase.mp ha).1 have haS : a ∈ S := (Finset.mem_erase.mp ha).2 have ha' : a ∈ t :: l := hS a haS have hal : a ∈ l := by rcases List.mem_cons.mp ha' with h | h · exact absurd h hne · exact h exact List.mem_filter.mpr ⟨hal, hc t ht a haS (Ne.symm hne)⟩ have hlen : (l.filter (c t)).length ≤ n := by have := List.length_filter_le (c t) l simp only [List.length_cons] at hl omega have := ih (l.filter (c t)) hlen (S.erase t) hsub (fun a ha b hb hab => hc a (Finset.mem_erase.mp ha).2 b (Finset.mem_erase.mp hb).2 hab) have hcard := Finset.card_erase_add_one ht omega
In the inductive step with list t :: l, if t ∉ S, then |S| is bounded by the branch in693_maxC c n l.
Since t ∉ S, every element a ∈ S in t :: l must satisfy a ∈ l by List.mem_cons.mp. Because l has length at most n, the induction hypothesis applies directly to S and l, giving |S| ≤ in693_maxC c n l, which is bounded by the maximum via le_max_left and transitivity (le_trans).
uses
le_trans,le_max_left,List.mem_cons.mp· refine le_trans ?_ (le_max_left _ _) have hlen : l.length ≤ n := by simpa using hl refine ih l hlen S ?_ hc intro a ha rcases List.mem_cons.mp (hS a ha) with h | h · exact absurd (h ▸ ha) ht · exact h
The concrete graph sharp_G on ten vertices has symmetric adjacency.
Two vertices u and v are adjacent if the unordered pair s(u, v) is in the edge set sharp_E and u ≠ v. Adjacency is symmetric because unordered pairs are invariant under swapping endpoints by Sym2.eq_swap.
uses
Sym2.eq_swapdef sharp_G : SimpleGraph (Fin 10) where Adj u v := s(u,v) ∈ sharp_E ∧ u ≠ v symm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩ loopless := ⟨fun u h => h.2 rfl⟩ instance : DecidableRel sharp_G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ∈ sharp_E ∧ _ ≠ _))
The list sharp_T contains all 3-cliques (triangles) of sharp_G, and every element of sharp_T is a 3-clique. automation
The Lean kernel exhaustively checks by decide +kernel that every 3-element subset of vertices forming a clique in sharp_G is listed in sharp_T (sharp_tri_complete), and that every entry of sharp_T forms a 3-clique (sharp_T_clique).
theorem sharp_tri_complete : ∀ t ∈ (Finset.univ : Finset (Fin 10)).powersetCard 3, sharp_G.IsNClique 3 t → t ∈ sharp_T := by decide +kernel set_option maxRecDepth 100000 in set_option maxHeartbeats 30000000 in theorem sharp_T_clique : ∀ t ∈ sharp_T, sharp_G.IsNClique 3 t := by decide +kernel lemma sharp_clique_mem {t : Finset (Fin 10)} (h : sharp_G.IsNClique 3 t) : t ∈ sharp_T := sharp_tri_complete t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _, h.card_eq⟩) h
The recursive branch-and-bound search evaluates to 8 on the list of triangles sharp_T and compatibility test sharp_compat. automation
Two triangles are edge-disjoint if and only if they share at most one vertex, which is tested by sharp_compat. The Lean kernel computes in693_maxC sharp_compat sharp_T.length sharp_T = 8 by decide +kernel, establishing the upper bound on the size of any pairwise compatible subcollection of sharp_T.
set_option maxRecDepth 100000 in set_option maxHeartbeats 30000000 in theorem sharp_maxC_eq : in693_maxC sharp_compat sharp_T.length sharp_T = 8 := by decide +kernel
The explicit family sharp_P consists of eight pairwise edge-disjoint triangles in sharp_G. automation
The Lean kernel verifies by computational reflection (decide +kernel) that all eight elements of sharp_P are 3-cliques in sharp_G (sharp_P_clique), that they are pairwise edge-disjoint (sharp_P_pw), and that sharp_P has cardinality 8 (sharp_P_card).
theorem sharp_P_clique : ∀ t ∈ sharp_P, sharp_G.IsNClique 3 t := by decide +kernel theorem sharp_P_pw : (sharp_P : Set (Finset (Fin 10))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kernel theorem sharp_P_card : sharp_P.card = 8 := by decide +kernel
The triangle packing number of sharp_G is 8.
Unfolding simple_graph_triangle_packing_number, the packing number is the supremum of the cardinalities of edge-disjoint triangle packings. By IsGreatest.csSup_eq, this supremum is 8 because sharp_P provides a witness of size 8 (using sharp_P_clique, sharp_P_pw, and sharp_P_card), and sharp_nu_le shows that every valid packing has cardinality at most 8.
uses
IsGreatest.csSup_eq,sharp_P_clique,sharp_P_pw,sharp_P_card,sharp_nu_letheorem sharp_pack_eq : simple_graph_triangle_packing_number sharp_G = 8 := by unfold simple_graph_triangle_packing_number refine IsGreatest.csSup_eq ⟨⟨sharp_P, sharp_P_clique, sharp_P_pw, sharp_P_card⟩, ?_⟩ rintro n ⟨T, h1, h2, rfl⟩ exact sharp_nu_le T h1 h2
The ten-vertex seed graph sharp_G has triangle packing number eight.
The theorem simple_graph_in693_ten_seed_packing_number is settled by the equality sharp_pack_eq proved in the previous step.
uses
sharp_pack_eqtheorem simple_graph_in693_ten_seed_packing_number : simple_graph_triangle_packing_number sharp_G = 8 := by exact sharp_pack_eq
Finset.card_erase_add_one- A finite set with an element a removed, plus one, has the same cardinality as the original set, provided a is in the set.
Finset.eq_empty_of_forall_notMem- A finite set whose elements all satisfy False is the empty set.
Finset.mem_erase.mp- An element is in s.erase b if and only if it is not equal to b and belongs to s.
IsGreatest.csSup_eq- If a set has a greatest element, that element is the supremum of the set.
List.length_cons- The length of a list with an element prepended is one more than the length of the tail.
List.length_eq_zero_iff.mp- A list has length zero if and only if it is the empty list (forward implication).
List.length_filter_le- Filtering a list by any predicate produces a list of length at most the original length.
List.mem_cons.mp- An element of b :: l is either equal to b or an element of l.
List.mem_filter.mpr- An element belongs to a filtered list if and only if it belongs to the original list and satisfies the predicate.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
le_max_left- The first argument of max is at most the maximum: a ≤ max a b.
le_max_right- The second argument of max is at most the maximum: b ≤ max a b.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
sharp_P_card- The explicit packing candidate sharp_P contains exactly eight triangles.
sharp_P_clique- Every triangle in the candidate family sharp_P is a 3-clique in the graph sharp_G.
sharp_P_pw- The triangles in sharp_P are pairwise edge-disjoint, intersecting in at most one vertex.
sharp_nu_le- Any family of pairwise edge-disjoint triangles in sharp_G has cardinality at most eight.
sharp_pack_eq- The triangle packing number of sharp_G is eight.
Sym2.eq_swap- Unordered pairs in Sym2 are symmetric under swapping their endpoints: s(a, b) = s(b, a).
- The recursive branch-and-bound function in693_maxC and several graph properties (clique classification in sharp_tri_complete and sharp_T_clique, the upper bound evaluation sharp_maxC_eq, and the witness packing verification in sharp_P_clique, sharp_P_pw, sharp_P_card) are verified by exhaustive computation in the Lean kernel via decide +kernel rather than interactive deductive steps.
- The lemma sharp_nu_le (lines 79–84), which applies the general inductive bound to sharp_G, is written in term mode using a calc block without tactic states.
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 Sym2def in693_maxC {α : Type} (c : α → α → Bool) : ℕ → List α → ℕ | 0, _ => 0 | _ + 1, [] => 0 | n + 1, t :: l => max (in693_maxC c n l) (1 + in693_maxC c n (l.filter (c t)))theorem in693_maxC_bound {α : Type} [DecidableEq α] (c : α → α → Bool) : ∀ (n : ℕ) (l : List α), l.length ≤ n → ∀ S : Finset α, (∀ a ∈ S, a ∈ l) → (∀ a ∈ S, ∀ b ∈ S, a ≠ b → c a b = true) → S.card ≤ in693_maxC c n l := by intro n induction n with | zero => intro l hl S hS _ have hl0 : l = [] := List.length_eq_zero_iff.mp (by omega) subst hl0 have : S = ∅ := Finset.eq_empty_of_forall_notMem (fun a ha => by simpa using hS a ha) simp [this, in693_maxC] | succ n ih => intro l hl S hS hc match l, hl, hS with | [], _, hS => have : S = ∅ := Finset.eq_empty_of_forall_notMem (fun a ha => by simpa using hS a ha) simp [this, in693_maxC] | t :: l, hl, hS => rw [in693_maxC] by_cases ht : t ∈ S · refine le_trans ?_ (le_max_right _ _) have hsub : ∀ a ∈ S.erase t, a ∈ l.filter (c t) := by intro a ha have hne : a ≠ t := (Finset.mem_erase.mp ha).1 have haS : a ∈ S := (Finset.mem_erase.mp ha).2 have ha' : a ∈ t :: l := hS a haS have hal : a ∈ l := by rcases List.mem_cons.mp ha' with h | h · exact absurd h hne · exact h exact List.mem_filter.mpr ⟨hal, hc t ht a haS (Ne.symm hne)⟩ have hlen : (l.filter (c t)).length ≤ n := by have := List.length_filter_le (c t) l simp only [List.length_cons] at hl omega have := ih (l.filter (c t)) hlen (S.erase t) hsub (fun a ha b hb hab => hc a (Finset.mem_erase.mp ha).2 b (Finset.mem_erase.mp hb).2 hab) have hcard := Finset.card_erase_add_one ht omega · refine le_trans ?_ (le_max_left _ _) have hlen : l.length ≤ n := by simpa using hl refine ih l hlen S ?_ hc intro a ha rcases List.mem_cons.mp (hS a ha) with h | h · exact absurd (h ▸ ha) ht · exact hdef sharp_EL : List (Sym2 (Fin 10)) := [s(0,1), s(0,2), s(0,3), s(0,4), s(0,5), s(1,2), s(1,5), s(1,8), s(1,9), s(2,3), s(2,6), s(2,7), s(2,8), s(2,9), s(3,4), s(3,6), s(3,7), s(3,8), s(3,9), s(4,5), s(4,6), s(4,9), s(5,6), s(5,7), s(5,8), s(5,9), s(6,7), s(6,8), s(6,9), s(7,8), s(8,9)]def sharp_T : List (Finset (Fin 10)) := [{0,1,2}, {0,1,5}, {0,2,3}, {0,3,4}, {0,4,5}, {1,2,8}, {1,2,9}, {1,5,8}, {1,5,9}, {1,8,9}, {2,3,6}, {2,3,7}, {2,3,8}, {2,3,9}, {2,6,7}, {2,6,8}, {2,6,9}, {2,7,8}, {2,8,9}, {3,4,6}, {3,4,9}, {3,6,7}, {3,6,8}, {3,6,9}, {3,7,8}, {3,8,9}, {4,5,6}, {4,5,9}, {4,6,9}, {5,6,7}, {5,6,8}, {5,6,9}, {5,7,8}, {5,8,9}, {6,7,8}, {6,8,9}]def sharp_P : Finset (Finset (Fin 10)) := {{1,2,9}, {1,5,8}, {2,3,7}, {2,6,8}, {3,4,6}, {3,8,9}, {4,5,9}, {5,6,7}}def sharp_E : Finset (Sym2 (Fin 10)) := sharp_EL.toFinsetdef sharp_G : SimpleGraph (Fin 10) where Adj u v := s(u,v) ∈ sharp_E ∧ u ≠ v symm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩ loopless := ⟨fun u h => h.2 rfl⟩instance : DecidableRel sharp_G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ∈ sharp_E ∧ _ ≠ _))set_option maxRecDepth 100000 inset_option maxHeartbeats 30000000 intheorem sharp_tri_complete : ∀ t ∈ (Finset.univ : Finset (Fin 10)).powersetCard 3, sharp_G.IsNClique 3 t → t ∈ sharp_T := by decide +kernelset_option maxRecDepth 100000 inset_option maxHeartbeats 30000000 intheorem sharp_T_clique : ∀ t ∈ sharp_T, sharp_G.IsNClique 3 t := by decide +kernellemma sharp_clique_mem {t : Finset (Fin 10)} (h : sharp_G.IsNClique 3 t) : t ∈ sharp_T := sharp_tri_complete t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _, h.card_eq⟩) hdef sharp_compat (s t : Finset (Fin 10)) : Bool := decide ((s ∩ t).card ≤ 1)set_option maxRecDepth 100000 inset_option maxHeartbeats 30000000 intheorem sharp_maxC_eq : in693_maxC sharp_compat sharp_T.length sharp_T = 8 := by decide +kernellemma sharp_nu_le (T : Finset (Finset (Fin 10))) (hT : ∀ t ∈ T, sharp_G.IsNClique 3 t) (hP : (T : Set (Finset (Fin 10))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : T.card ≤ 8 := calc T.card ≤ in693_maxC sharp_compat sharp_T.length sharp_T := in693_maxC_bound sharp_compat _ sharp_T le_rfl T (fun a ha => sharp_clique_mem (hT a ha)) (fun a ha b hb hab => decide_eq_true (hP (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hb) hab)) _ = 8 := sharp_maxC_eqtheorem sharp_P_clique : ∀ t ∈ sharp_P, sharp_G.IsNClique 3 t := by decide +kerneltheorem sharp_P_pw : (sharp_P : Set (Finset (Fin 10))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kerneltheorem sharp_P_card : sharp_P.card = 8 := by decide +kerneltheorem sharp_pack_eq : simple_graph_triangle_packing_number sharp_G = 8 := by unfold simple_graph_triangle_packing_number refine IsGreatest.csSup_eq ⟨⟨sharp_P, sharp_P_clique, sharp_P_pw, sharp_P_card⟩, ?_⟩ rintro n ⟨T, h1, h2, rfl⟩ exact sharp_nu_le T h1 h2theorem simple_graph_in693_ten_seed_packing_number : simple_graph_triangle_packing_number sharp_G = 8 := by exact sharp_pack_eq