AFTD Auto-Formalizing Theoretical Domains

simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity

theoremverified

A graph on the nine vertices of the local-exchange seed that contains all seed edges and has triangle packing number at most seven adds no edge other than possibly 07.

Statement

open scoped Sym2

theorem simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity :
    let E₀ : Finset (Sym2 (Fin 9)) := {s(0,1), s(0,2), s(0,3), s(0,5), s(1,2), s(1,3), s(1,4), s(1,5), s(1,6), s(1,7), s(2,3), s(2,4), s(2,5), s(2,6), s(2,8), s(3,4), s(3,5), s(3,6), s(3,7), s(3,8), s(4,5), s(4,6), s(5,6), s(5,7), s(6,7), s(6,8)}
    ∀ G : SimpleGraph (Fin 9),
      (↑E₀ : Set (Sym2 (Fin 9))) ⊆ G.edgeSet →
      (∀ P : Finset (Finset (Sym2 (Fin 9))), P ⊆ simple_graph_triangle_edge_family G →
        (P : Set (Finset (Sym2 (Fin 9)))).Pairwise Disjoint → P.card ≤ 7) →
      G.edgeSet ⊆ (↑(insert s(0,7) E₀) : Set (Sym2 (Fin 9)))
Source
Finite seed rigidity for the local-exchange obstruction, experiments 17062–17064.
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

To show that any supergraph G of the 26-edge seed graph with triangle packing number at most 7 contains no edge other than possibly s(0,7), the proof argues by contradiction. An exhaustive finite check over all 36 vertex pairs on nine vertices establishes that any non-loop edge other than s(0,7) and the seed edges must be one of nine candidate edges. For each of these nine candidate edges, an explicit family of 8 vertex triples is exhibited whose edges lie entirely within the seed edges and the candidate edge. By a combinatorial bridge theorem, these triples encode 8 pairwise edge-disjoint triangles in G, contradicting the assumption that the maximum triangle packing number is at most 7.

  1. Any pair of vertices connected by a seed edge or by the edge e is adjacent in G.

    We split on whether the unordered pair s(a, b) is in the seed edges or equals e. In the first case, s(a, b) is an edge of G because the seed edges are a subset of G's edge set. In the second case, s(a, b) = e, which is in G's edge set by assumption. In both cases, membership in G.edgeSet is rewritten to adjacency G.Adj a b using SimpleGraph.mem_edgeSet.

    lines 13–15

    uses SimpleGraph.mem_edgeSet

      rcases h with h | h
      · rw [← SimpleGraph.mem_edgeSet]; exact hsub h
      · rw [← SimpleGraph.mem_edgeSet, h]; exact he
  2. The candidate family x of 8 vertex triples satisfies the size hypothesis of the edge-encoding bridge, which equates pairwise edge-disjointness with triples sharing at most one vertex. automation

    Each triple t in x has cardinality 3, so its cardinality is at least 2. Applying finite_vertex_family_edge_packing_cover_bridge with an empty cover set shows that edge encoding preserves family cardinality and that the encoded edge sets are pairwise disjoint if and only if any two distinct triples intersect in at most one vertex.

    lines 28–31

    uses finite_vertex_family_edge_packing_cover_bridge

      have hsize : ∀ t ∈ x, 2 ≤ t.card := by
        intro t ht; have := (hxtri t ht).1; omega
      obtain ⟨hcard_eq, hdisj_iff, -⟩ :=
        finite_vertex_family_edge_packing_cover_bridge (V := Fin 9) x (∅ : Finset (Sym2 (Fin 9))) hsize (by simp)
  3. Every vertex triple in x encodes a triangle in G, so the encoded family is a subfamily of the triangle edge family of G.

    Given any encoded triple t' coming from t ∈ x, the triple t has cardinality 3 and every pair of distinct vertices in t is connected by a seed edge or by e. By simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_adj_of_mem, every such pair is adjacent in G, making t a 3-clique in G. Thus, by simple_graph_triangle_edge_family_mem, its edge encoding belongs to the triangle edge family of G.

    lines 32–39

    uses Finset.mem_image, simple_graph_triangle_edge_family_mem, simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_adj_of_mem

      have hPsub : x.image finite_vertex_set_edge_encoding ⊆ simple_graph_triangle_edge_family G := by
        intro t' ht'
        rw [Finset.mem_image] at ht'
        obtain ⟨t, ht, rfl⟩ := ht'
        rw [simple_graph_triangle_edge_family_mem]
        exact ⟨t, ⟨fun a ha b hb hab =>
            simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_adj_of_mem hsub he
              ((hxtri t ht).2 a ha b hb hab), (hxtri t ht).1⟩, rfl⟩
  4. The existence of 8 pairwise almost-disjoint vertex triangles in G contradicts the maximum triangle packing size bound of 7. automation

    Because the vertex triples in x pairwise share at most one vertex, the bridge equivalence implies their edge encodings are pairwise disjoint. This produces a packing of 8 edge-disjoint triangles in G. But by hypothesis, every edge-disjoint triangle packing in G has size at most 7, yielding 8 ≤ 7, a contradiction closed by linear arithmetic.

    lines 40–44

      have hPdisj : (x.image finite_vertex_set_edge_encoding : Set (Finset (Sym2 (Fin 9)))).Pairwise Disjoint :=
        hdisj_iff.mpr hxdisj
      have h7 := hle _ hPsub hPdisj
      rw [hcard_eq, hxcard] at h7
      omega
  5. Any non-loop edge on nine vertices not in the seed set and not equal to s(0,7) must be one of nine candidate edges: s(0,4), s(0,6), s(0,8), s(1,8), s(2,7), s(4,7), s(4,8), s(5,8), or s(7,8). automation

    There are 36 possible non-loop edges on nine vertices. Subtracting the 26 seed edges and the edge s(0,7) leaves exactly 9 candidate edges. This exhaustive case analysis is verified by boolean evaluation over all finite cases using decide +revert.

    lines 46–50

    private lemma simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_cases (e : Sym2 (Fin 9)) :
        ¬ e.IsDiag → e ∉ simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_edges → e ≠ s(0,7) →
        (e = s(0,4) ∨ e = s(0,6) ∨ e = s(0,8) ∨ e = s(1,8) ∨ e = s(2,7) ∨
         e = s(4,7) ∨ e = s(4,8) ∨ e = s(5,8) ∨ e = s(7,8)) := by
      decide +revert
  6. Assuming for contradiction that G contains an edge other than s(0,7) and the seed edges, that edge must be one of the nine candidate edges.

    Suppose for contradiction that G contains an edge e that is neither s(0,7) nor in the seed edge set E₀. Since G is a simple graph, e cannot be a self-loop by SimpleGraph.not_isDiag_of_mem_edgeSet. Applying the case analysis lemma simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_cases shows that e must be one of the nine candidate edges: s(0,4), s(0,6), s(0,8), s(1,8), s(2,7), s(4,7), s(4,8), s(5,8), or s(7,8).

    lines 61–67

    uses Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe, not_or, SimpleGraph.not_isDiag_of_mem_edgeSet, simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_cases

      intro E₀ G hsub hle e he
      by_contra hnot
      simp only [Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe, not_or] at hnot
      obtain ⟨h07, hE⟩ := hnot
      have hdiag : ¬ e.IsDiag := SimpleGraph.not_isDiag_of_mem_edgeSet G he
      have hcases := simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_cases e hdiag hE h07
      rcases hcases with h | h | h | h | h | h | h | h | h
  7. Each of the nine candidate edges leads to a contradiction by exhibiting an explicit packing of 8 edge-disjoint triangles in G. automation

    For each of the nine candidate edges, an explicit collection of 8 vertex triples on {0, ..., 8} is provided. In each case, decide verifies by finite computation that the collection consists of 8 triples of size 3, that any two triples intersect in at most one vertex, and that every edge of every triple is either a seed edge or the candidate edge. Invoking the packing contradiction lemma simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra on each case produces an 8-triangle packing in G, contradicting the packing number bound of at most 7.

    lines 68–103

    uses simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra

      · rw [h] at he
        exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(0,4)) he
          {{0,1,2}, {0,3,4}, {1,3,7}, {1,4,5}, {2,3,5}, {2,4,6}, {3,6,8}, {5,6,7}}
          (by decide) (by decide) (by decide)
      · rw [h] at he
        exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(0,6)) he
          {{0,1,3}, {0,2,6}, {1,2,5}, {1,6,7}, {2,3,4}, {3,5,7}, {3,6,8}, {4,5,6}}
          (by decide) (by decide) (by decide)
      · rw [h] at he
        exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(0,8)) he
          {{0,1,2}, {0,3,8}, {1,3,4}, {1,5,7}, {2,3,5}, {2,6,8}, {3,6,7}, {4,5,6}}
          (by decide) (by decide) (by decide)
      · rw [h] at he
        exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(1,8)) he
          {{0,1,2}, {0,3,5}, {1,3,4}, {1,5,7}, {1,6,8}, {2,3,8}, {2,4,5}, {3,6,7}}
          (by decide) (by decide) (by decide)
      · rw [h] at he
        exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(2,7)) he
          {{0,1,2}, {0,3,5}, {1,3,4}, {1,5,6}, {2,3,8}, {2,4,6}, {2,5,7}, {3,6,7}}
          (by decide) (by decide) (by decide)
      · rw [h] at he
        exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(4,7)) he
          {{0,1,2}, {0,3,5}, {1,3,4}, {1,5,6}, {2,3,8}, {2,4,6}, {3,6,7}, {4,5,7}}
          (by decide) (by decide) (by decide)
      · rw [h] at he
        exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(4,8)) he
          {{0,1,2}, {0,3,5}, {1,3,4}, {1,5,6}, {2,3,8}, {2,4,5}, {3,6,7}, {4,6,8}}
          (by decide) (by decide) (by decide)
      · rw [h] at he
        exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(5,8)) he
          {{0,1,2}, {0,3,5}, {1,3,4}, {1,5,7}, {2,3,8}, {2,4,5}, {3,6,7}, {5,6,8}}
          (by decide) (by decide) (by decide)
      · rw [h] at he
        exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(7,8)) he
          {{0,1,2}, {0,3,5}, {1,3,6}, {1,4,5}, {2,3,4}, {2,6,8}, {3,7,8}, {5,6,7}}
          (by decide) (by decide) (by decide)
SimpleGraph.mem_edgeSet
An unordered pair of vertices forms an edge of a simple graph if and only if those vertices are adjacent.
finite_vertex_family_edge_packing_cover_bridge
For a family of vertex subsets of size at least 2, their edge encodings have the same cardinality as the family, and the encoded edge sets are pairwise disjoint if and only if any two distinct vertex subsets intersect in at most one vertex.
Finset.mem_image
An element belongs to the image of a finite set under a function if and only if it is the image of some element in the set.
simple_graph_triangle_edge_family_mem
A set of edges belongs to the triangle edge family of a graph if and only if it is the edge encoding of a 3-clique in the graph.
simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_adj_of_mem
In a graph containing the seed edges and an edge e, any pair of vertices connected by a seed edge or by e is adjacent in the graph.
Finset.coe_insert
The set coercion of inserting an element into a finite set is the insertion of that element into the coerced set.
Set.mem_insert_iff
An element belongs to the insertion of an element into a set if and only if it equals the inserted element or belongs to the set.
Finset.mem_coe
An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
not_or
The negation of a disjunction is equivalent to the conjunction of the negations.
SimpleGraph.not_isDiag_of_mem_edgeSet
An edge in a simple graph connects two distinct vertices; it is never a self-loop.
simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_cases
Any non-loop edge on nine vertices that is not in the 26 seed edges and not equal to s(0,7) must be one of nine specific edges: s(0,4), s(0,6), s(0,8), s(1,8), s(2,7), s(4,7), s(4,8), s(5,8), or s(7,8).
simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra
In a graph containing the seed edges and an edge e whose triangle packing number is at most 7, there cannot exist 8 pairwise almost-disjoint triples of vertices whose edges all lie in the seed edges or equal e.

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 Sym2private def simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_edges : Finset (Sym2 (Fin 9)) :=  {s(0,1), s(0,2), s(0,3), s(0,5), s(1,2), s(1,3), s(1,4), s(1,5), s(1,6), s(1,7),   s(2,3), s(2,4), s(2,5), s(2,6), s(2,8), s(3,4), s(3,5), s(3,6), s(3,7), s(3,8),   s(4,5), s(4,6), s(5,6), s(5,7), s(6,7), s(6,8)}private lemma simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_adj_of_mem    {G : SimpleGraph (Fin 9)}    (hsub : (↑simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_edges : Set (Sym2 (Fin 9))) ⊆ G.edgeSet)    {e : Sym2 (Fin 9)} (he : e ∈ G.edgeSet)    {a b : Fin 9} (h : s(a,b) ∈ simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_edges ∨ s(a,b) = e) : G.Adj a b := by  rcases h with h | h  · rw [← SimpleGraph.mem_edgeSet]; exact hsub h  · rw [← SimpleGraph.mem_edgeSet, h]; exact heprivate lemma simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra    (G : SimpleGraph (Fin 9))    (hsub : (↑simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_edges : Set (Sym2 (Fin 9))) ⊆ G.edgeSet)    (hle : ∀ P : Finset (Finset (Sym2 (Fin 9))), P ⊆ simple_graph_triangle_edge_family G →        (P : Set (Finset (Sym2 (Fin 9)))).Pairwise Disjoint → P.card ≤ 7)    (e : Sym2 (Fin 9)) (he : e ∈ G.edgeSet)    (x : Finset (Finset (Fin 9))) (hxcard : x.card = 8)    (hxtri : ∀ t ∈ x, t.card = 3 ∧ ∀ a ∈ t, ∀ b ∈ t, a ≠ b →      s(a,b) ∈ simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_edges ∨ s(a,b) = e)    (hxdisj : (x : Set (Finset (Fin 9))).Pairwise (fun s t => (s ∩ t).card ≤ 1)) :    False := by  have hsize : ∀ t ∈ x, 2 ≤ t.card := by    intro t ht; have := (hxtri t ht).1; omega  obtain ⟨hcard_eq, hdisj_iff, -⟩ :=    finite_vertex_family_edge_packing_cover_bridge (V := Fin 9) x (∅ : Finset (Sym2 (Fin 9))) hsize (by simp)  have hPsub : x.image finite_vertex_set_edge_encoding ⊆ simple_graph_triangle_edge_family G := by    intro t' ht'    rw [Finset.mem_image] at ht'    obtain ⟨t, ht, rfl⟩ := ht'    rw [simple_graph_triangle_edge_family_mem]    exact ⟨t, ⟨fun a ha b hb hab =>        simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_adj_of_mem hsub he          ((hxtri t ht).2 a ha b hb hab), (hxtri t ht).1⟩, rfl⟩  have hPdisj : (x.image finite_vertex_set_edge_encoding : Set (Finset (Sym2 (Fin 9)))).Pairwise Disjoint :=    hdisj_iff.mpr hxdisj  have h7 := hle _ hPsub hPdisj  rw [hcard_eq, hxcard] at h7  omegaprivate lemma simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_cases (e : Sym2 (Fin 9)) :    ¬ e.IsDiag → e ∉ simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_edges → e ≠ s(0,7) →    (e = s(0,4) ∨ e = s(0,6) ∨ e = s(0,8) ∨ e = s(1,8) ∨ e = s(2,7) ∨     e = s(4,7) ∨ e = s(4,8) ∨ e = s(5,8) ∨ e = s(7,8)) := by  decide +revertopen scoped Sym2theorem simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity :    let E₀ : Finset (Sym2 (Fin 9)) := {s(0,1), s(0,2), s(0,3), s(0,5), s(1,2), s(1,3), s(1,4), s(1,5), s(1,6), s(1,7), s(2,3), s(2,4), s(2,5), s(2,6), s(2,8), s(3,4), s(3,5), s(3,6), s(3,7), s(3,8), s(4,5), s(4,6), s(5,6), s(5,7), s(6,7), s(6,8)}    ∀ G : SimpleGraph (Fin 9),      (↑E₀ : Set (Sym2 (Fin 9))) ⊆ G.edgeSet →      (∀ P : Finset (Finset (Sym2 (Fin 9))), P ⊆ simple_graph_triangle_edge_family G →        (P : Set (Finset (Sym2 (Fin 9)))).Pairwise Disjoint → P.card ≤ 7) →      G.edgeSet ⊆ (↑(insert s(0,7) E₀) : Set (Sym2 (Fin 9))) := by  intro E₀ G hsub hle e he  by_contra hnot  simp only [Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe, not_or] at hnot  obtain ⟨h07, hE⟩ := hnot  have hdiag : ¬ e.IsDiag := SimpleGraph.not_isDiag_of_mem_edgeSet G he  have hcases := simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_cases e hdiag hE h07  rcases hcases with h | h | h | h | h | h | h | h | h  · rw [h] at he    exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(0,4)) he      {{0,1,2}, {0,3,4}, {1,3,7}, {1,4,5}, {2,3,5}, {2,4,6}, {3,6,8}, {5,6,7}}      (by decide) (by decide) (by decide)  · rw [h] at he    exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(0,6)) he      {{0,1,3}, {0,2,6}, {1,2,5}, {1,6,7}, {2,3,4}, {3,5,7}, {3,6,8}, {4,5,6}}      (by decide) (by decide) (by decide)  · rw [h] at he    exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(0,8)) he      {{0,1,2}, {0,3,8}, {1,3,4}, {1,5,7}, {2,3,5}, {2,6,8}, {3,6,7}, {4,5,6}}      (by decide) (by decide) (by decide)  · rw [h] at he    exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(1,8)) he      {{0,1,2}, {0,3,5}, {1,3,4}, {1,5,7}, {1,6,8}, {2,3,8}, {2,4,5}, {3,6,7}}      (by decide) (by decide) (by decide)  · rw [h] at he    exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(2,7)) he      {{0,1,2}, {0,3,5}, {1,3,4}, {1,5,6}, {2,3,8}, {2,4,6}, {2,5,7}, {3,6,7}}      (by decide) (by decide) (by decide)  · rw [h] at he    exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(4,7)) he      {{0,1,2}, {0,3,5}, {1,3,4}, {1,5,6}, {2,3,8}, {2,4,6}, {3,6,7}, {4,5,7}}      (by decide) (by decide) (by decide)  · rw [h] at he    exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(4,8)) he      {{0,1,2}, {0,3,5}, {1,3,4}, {1,5,6}, {2,3,8}, {2,4,5}, {3,6,7}, {4,6,8}}      (by decide) (by decide) (by decide)  · rw [h] at he    exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(5,8)) he      {{0,1,2}, {0,3,5}, {1,3,4}, {1,5,7}, {2,3,8}, {2,4,5}, {3,6,7}, {5,6,8}}      (by decide) (by decide) (by decide)  · rw [h] at he    exact simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_packing_contra G hsub hle (s(7,8)) he      {{0,1,2}, {0,3,5}, {1,3,6}, {1,4,5}, {2,3,4}, {2,6,8}, {3,7,8}, {5,6,7}}      (by decide) (by decide) (by decide)
See it in the graphDiscuss this resultChallenge it