AFTD Auto-Formalizing Theoretical Domains

simple_graph_in693_ten_seed_pair_stable

theoremverified

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

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.

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

    lines 5–17

    uses List.mem_append.mp, in715_Wok0, in715_Wok1, in715_Wok2, in715_Wok3, in715_Wok4, in715_Wok5

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

    lines 19–34

    uses List.mem_append.mp, in715_Wcover0, in715_Wcover1, in715_Wcover2, in715_Wcover3, in715_Wcover4, in715_Wcover5, in715_Wcover6

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

    lines 36–39

    uses Sym2.ind, SimpleGraph.mem_edgeSet, List.mem_toFinset.mp

      induction g using Sym2.ind with
      | _ a b =>
        have h1 := ((SimpleGraph.mem_edgeSet sharp_G).mp h).1
        exact List.mem_toFinset.mp h1
  4. 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.

    lines 44–57

    uses SimpleGraph.deleteEdges_adj, Set.mem_insert_iff, Set.mem_singleton_iff, Sym2.mem_iff.mp

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

    lines 62–67

    uses sharp_pack_eq, sharp_W_cover, sharp_edge_mem, sharp_W_ok, IsGreatest.csSup_eq

      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⟩, ?_⟩
  6. 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.

    lines 68–72

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

    lines 73–75

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

    lines 76–77

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

    line 79

    uses sharp_stable

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

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