AFTD Auto-Formalizing Theoretical Domains

simple_graph_in693_ten_seed_packing_number

theoremverified

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
Used by 19

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.

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

    lines 11–18

    uses List.length_eq_zero_iff.mp, Finset.eq_empty_of_forall_notMem

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

    lines 19–25

    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 =>
  3. 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).

    lines 26–46

    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_one

          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
  4. 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).

    lines 47–54

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

    lines 60–64

    uses Sym2.eq_swap

    def 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 ∧ _ ≠ _))
  6. 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).

    lines 67–73

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

    lines 76–78

    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
  8. 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).

    lines 85–87

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

    lines 88–93

    uses IsGreatest.csSup_eq, sharp_P_clique, sharp_P_pw, sharp_P_card, sharp_nu_le

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

    lines 94–95

    uses sharp_pack_eq

    theorem 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).

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