simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity
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
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- finite_vertex_family_edge_packing_cover_bridgeEncoding each member of a finite vertex-set family of size at least two by its non-diagonal pairs preserves the family size, converts…
- simple_graph_triangle_edge_family_memA set of three edges belongs to the triangle edge family of G iff it is the set of non-diagonal pairs spanned by some three vertices…
- VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
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.
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.
uses
SimpleGraph.mem_edgeSetrcases h with h | h · rw [← SimpleGraph.mem_edgeSet]; exact hsub h · rw [← SimpleGraph.mem_edgeSet, h]; exact he
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.
uses
finite_vertex_family_edge_packing_cover_bridgehave 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)
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.
uses
Finset.mem_image,simple_graph_triangle_edge_family_mem,simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_adj_of_memhave 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⟩
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.
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
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.
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
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).
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_casesintro 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
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.
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.
- The lemma simple_graph_seven_packing_local_minimum_seed_supergraph_rigidity_cases is established by finite exhaustive enumeration over all 36 possible vertex pairs using `decide +revert`.
- In each of the nine cases of the main theorem, verifying the cardinality, edge membership, and almost-disjointness conditions for the candidate family of 8 vertex triples is discharged entirely by `decide`.
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 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)