simple_graph_stable_triangle_active_edge_in_maximum_packing
In a finite graph where deleting any edge preserves the maximum triangle packing number, every edge belonging to a triangle is used by some maximum triangle packing.
Statement
theorem simple_graph_stable_triangle_active_edge_in_maximum_packing {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hstable : ∀ e ∈ G.edgeSet, simple_graph_triangle_packing_number (G.deleteEdges {e}) = simple_graph_triangle_packing_number G) (e : Sym2 V) (he : e ∈ G.edgeSet) (hactive : ∃ t : Finset V, G.IsNClique 3 t ∧ ∀ x ∈ e, x ∈ t) : ∃ P : Finset (Finset V), (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G ∧ ∃ t ∈ P, ∀ x ∈ e, x ∈ t
- Source
- Elementary packing exchange in the triangle packing-cover campaign; the packing definition is from arXiv:2610.15539, Section 1.
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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).
- finite_three_set_stable_maximum_packings_cover_supportFor a finite family of three-element sets, suppose every packing has at most k members and, for each point occurring in the family, some…
- 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…
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
The proof, explained
The proof reduces the problem of finding a maximum triangle packing containing an active edge to covering an element in a 3-uniform hypergraph of triangle edge sets. It first verifies that deleting an edge preserves the maximum packing number of disjoint edge triples, then invokes a theorem that stable 3-uniform hypergraphs have maximum packings covering any active element, and finally lifts the resulting edge packing back to a triangle packing in the graph.
The edge encoding of {x, y, z} consists of {s(x, y), s(y, z), s(x, z)}. automation
We check element membership by cases on unordered pairs and simplify using the distinctness of the three vertices.
classical ext e induction' e using Sym2.inductionOn with u v simp only [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mem_sym2_iff, Finset.mem_insert, Finset.mem_singleton, Sym2.mk_isDiag_iff, Sym2.eq, Sym2.rel_iff', Prod.mk.injEq] aesop
The edge encoding of any 3-element set has size 3.
By expressing the set as {x, y, z} and applying the explicit encoding formula, the three resulting edges are mutually distinct, so the set has size 3.
classical rcases Finset.card_eq_three.mp ht with ⟨x, y, z, hxy, hxz, hyz, rfl⟩ rw [simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_encoding_explicit x y z hxy hxz hyz] have h1 : s(x, y) ≠ s(y, z) := by simp [Sym2.eq, Sym2.rel_iff']; aesop have h2 : s(x, y) ≠ s(x, z) := by simp [Sym2.eq, Sym2.rel_iff']; aesop have h3 : s(y, z) ≠ s(x, z) := by simp [Sym2.eq, Sym2.rel_iff']; aesop rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · simp [h3] · simp [h1, h2]
Any subset of the image of a finite set has an equicardinal preimage.
Using the axiom of choice on the finite subset Q, we choose a single preimage for each element of Q, yielding a subset P of S that maps bijectively onto Q.
classical have h_choice : ∀ b ∈ Q, ∃ a ∈ S, f a = b := by intro b hb have := hQ hb rw [Finset.mem_image] at this rcases this with ⟨a, ha, rfl⟩ exact ⟨a, ha, rfl⟩ choose! g hg1 hg2 using h_choice set P := Q.attach.image (fun ⟨b, hb⟩ => g b hb) have hP_sub : P ⊆ S := by intro a ha rw [Finset.mem_image] at ha rcases ha with ⟨⟨b, hb⟩, -, rfl⟩ exact hg1 b hb have hP_im : P.image f = Q := by ext b rw [Finset.mem_image] constructor · rintro ⟨a, ha, rfl⟩ rw [Finset.mem_image] at ha rcases ha with ⟨⟨b', hb'⟩, -, rfl⟩ rw [hg2 b' hb'] exact hb' · intro hb refine ⟨g b hb, ?_, hg2 b hb⟩ rw [Finset.mem_image] exact ⟨⟨b, hb⟩, Finset.mem_attach _ _, rfl⟩ have hP_card : P.card = Q.card := by apply le_antisymm · have := Finset.card_image_le (s := Q.attach) (f := fun ⟨b, hb⟩ => g b hb) simp only [Finset.card_attach] at this exact this · rw [← hP_im] exact Finset.card_image_le exact ⟨P, hP_sub, hP_im, hP_card⟩
Any edge belonging to the union of the triangle edge family is an edge of G.
An edge in the family belongs to the edge encoding of some 3-clique, so its endpoints form an edge in G.
classical rw [Finset.mem_biUnion] at hy rcases hy with ⟨t, ht, hy_in_t⟩ dsimp only [id] at hy_in_t unfold simple_graph_triangle_edge_family at ht rw [Finset.mem_image] at ht rcases ht with ⟨s, hs, rfl⟩ rw [Finset.mem_filter] at hs obtain ⟨-, hclique⟩ := hs rw [finite_vertex_set_edge_encoding, Finset.mem_filter] at hy_in_t obtain ⟨h_sym2, h_nondiag⟩ := hy_in_t induction' y using Sym2.inductionOn with u v simp only [Sym2.mk_isDiag_iff] at h_nondiag simp only [Finset.mem_sym2_iff, Sym2.mem_iff] at h_sym2 have hu : u ∈ s := h_sym2 u (Or.inl rfl) have hv : v ∈ s := h_sym2 v (Or.inr rfl) exact hclique.isClique hu hv h_nondiag
A triangle in G minus {y} does not contain y among its edges.
If y were in the encoding of a triangle in the edge-deleted graph, both its endpoints would be adjacent in that graph, contradicting the deletion of y.
classical intro hy rw [finite_vertex_set_edge_encoding, Finset.mem_filter] at hy obtain ⟨h_sym2, h_nondiag⟩ := hy induction' y using Sym2.inductionOn with u v simp only [Sym2.mk_isDiag_iff] at h_nondiag simp only [Finset.mem_sym2_iff, Sym2.mem_iff] at h_sym2 have hu : u ∈ t := h_sym2 u (Or.inl rfl) have hv : v ∈ t := h_sym2 v (Or.inr rfl) have hadj : (G.deleteEdges {s(u, v)}).Adj u v := ht.isClique hu hv h_nondiag rw [SimpleGraph.deleteEdges_adj] at hadj simp at hadj
An active edge belongs to the union of the triangle edge family.
The active edge is contained in some 3-clique, so it appears in the edge encoding of that clique in the triangle family.
classical rcases hactive with ⟨t, ht, he_in_t⟩ rw [Finset.mem_biUnion] refine ⟨finite_vertex_set_edge_encoding t, ?_, ?_⟩ · unfold simple_graph_triangle_edge_family rw [Finset.mem_image] refine ⟨t, ?_, rfl⟩ rw [Finset.mem_filter] exact ⟨Finset.mem_univ t, ht⟩ · dsimp only [id] rw [finite_vertex_set_edge_encoding, Finset.mem_filter] refine ⟨?_, G.not_isDiag_of_mem_edgeSet he⟩ induction' e using Sym2.inductionOn with u v simp only [Finset.mem_sym2_iff, Sym2.mem_iff] intro x hx exact he_in_t x (Sym2.mem_iff.mpr hx)
Every edge in the encoding of a vertex set is a subset of that vertex set.
By definition, the encoding contains only unordered pairs of vertices drawn from that set.
classical rw [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mem_sym2_iff] at he exact he.1
The main theorem holds.
We translate the triangle packing problem into packing disjoint 3-element edge sets in a 3-uniform hypergraph, verify the stability hypothesis from edge deletion, apply the hypergraph theorem, and pull back to triangles.
classical set k := simple_graph_triangle_packing_number G set F := simple_graph_triangle_edge_family G set T_all := (Finset.univ : Finset (Finset V)).filter (G.IsNClique 3) have hF_def : F = T_all.image finite_vertex_set_edge_encoding := rfl have hthree : ∀ t ∈ F, t.card = 3 := by intro t ht rw [hF_def, Finset.mem_image] at ht rcases ht with ⟨s, hs, rfl⟩ rw [Finset.mem_filter] at hs exact simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_encoding_card_three s hs.2.card_eq have hmax : ∀ P ⊆ F, (P : Set (Finset (Sym2 V))).Pairwise Disjoint → P.card ≤ k := by intro P hP hpw obtain ⟨T, hT_sub, hT_im, hT_card⟩ := simple_graph_stable_triangle_active_edge_in_maximum_packing_subset_image_has_preimage finite_vertex_set_edge_encoding T_all P (by rw [← hF_def]; exact hP) have hsize : ∀ t ∈ T, 2 ≤ t.card := by intro t ht have := hT_sub ht rw [Finset.mem_filter] at this rw [this.2.card_eq] omega have hbridge := finite_vertex_family_edge_packing_cover_bridge T ∅ hsize (by simp) rw [hT_im] at hbridge have hT_pw : (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := hbridge.2.1.mp hpw have hT_clique : ∀ t ∈ T, G.IsNClique 3 t := by intro t ht have := hT_sub ht rw [Finset.mem_filter] at this exact this.2 have hbdd : BddAbove {n | ∃ T : Finset (Finset V), (∀ a ∈ T, G.IsNClique 3 a) ∧ (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} := by refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩ rintro n ⟨T', -, -, rfl⟩ exact Finset.card_le_univ T' have hle : T.card ≤ k := by change T.card ≤ simple_graph_triangle_packing_number G unfold simple_graph_triangle_packing_number exact le_csSup hbdd ⟨T, hT_clique, hT_pw, rfl⟩ omega have hstab : ∀ y ∈ F.biUnion id, ∃ P ⊆ F, (P : Set (Finset (Sym2 V))).Pairwise Disjoint ∧ P.card = k ∧ ∀ s ∈ P, y ∉ s := by intro y hy have hye : y ∈ G.edgeSet := simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_of_mem_family G y hy have hstab_y := hstable y hye set G' := G.deleteEdges {y} set P_set : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ t ∈ T, G'.IsNClique 3 t) ∧ (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} have hbdd' : BddAbove P_set := by refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩ rintro n ⟨T', -, -, rfl⟩ exact Finset.card_le_univ T' have hne' : P_set.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ obtain ⟨T, hT_clique, hT_pw, hT_c⟩ := Nat.sSup_mem hne' hbdd' have hT_card_eq : T.card = k := by have hs : sSup P_set = simple_graph_triangle_packing_number G' := rfl rw [hT_c, hs, hstab_y] have hsize : ∀ t ∈ T, 2 ≤ t.card := by intro t ht rw [(hT_clique t ht).card_eq] omega set P' := T.image finite_vertex_set_edge_encoding have hbridge := finite_vertex_family_edge_packing_cover_bridge T ∅ hsize (by simp) refine ⟨P', ?_, ?_, ?_, ?_⟩ · intro F' hF' rw [Finset.mem_image] at hF' rcases hF' with ⟨t, ht, rfl⟩ rw [hF_def, Finset.mem_image] refine ⟨t, ?_, rfl⟩ rw [Finset.mem_filter] refine ⟨Finset.mem_univ t, ?_⟩ have ht_cl := hT_clique t ht exact ⟨ht_cl.1.mono (G.deleteEdges_le {y}), ht_cl.2⟩ · exact hbridge.2.1.mpr hT_pw · rw [hbridge.1, hT_card_eq] · intro s hs rw [Finset.mem_image] at hs rcases hs with ⟨t, ht, rfl⟩ exact simple_graph_stable_triangle_active_edge_in_maximum_packing_not_mem_encoding_of_clique_deleteEdges G y t (hT_clique t ht) have he_in : e ∈ F.biUnion id := simple_graph_stable_triangle_active_edge_in_maximum_packing_e_in_family_biUnion G e he hactive obtain ⟨Q, hQ_sub, hQ_pw, hQ_card, ⟨s, hs_in_Q, he_in_s⟩⟩ := finite_three_set_stable_maximum_packings_cover_support F k hthree hmax hstab e he_in obtain ⟨P, hP_sub, hP_im, hP_card⟩ := simple_graph_stable_triangle_active_edge_in_maximum_packing_subset_image_has_preimage finite_vertex_set_edge_encoding T_all Q (by rw [← hF_def]; exact hQ_sub) have hsize : ∀ t ∈ P, 2 ≤ t.card := by intro t ht have := hP_sub ht rw [Finset.mem_filter] at this rw [this.2.card_eq] omega have hbridge := finite_vertex_family_edge_packing_cover_bridge P ∅ hsize (by simp) rw [hP_im] at hbridge refine ⟨P, ?_, ?_, ?_, ?_⟩ · intro t ht have := hP_sub ht rw [Finset.mem_filter] at this exact this.2 · exact hbridge.2.1.mp hQ_pw · rw [hP_card, hQ_card] · rw [← hP_im, Finset.mem_image] at hs_in_Q rcases hs_in_Q with ⟨t, ht, rfl⟩ refine ⟨t, ht, ?_⟩ exact simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_subset_of_mem_encoding t e he_in_s
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.
lemma simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_encoding_explicit {V : Type*} [DecidableEq V] (x y z : V) (hxy : x ≠ y) (hxz : x ≠ z) (hyz : y ≠ z) : finite_vertex_set_edge_encoding ({x, y, z} : Finset V) = {s(x, y), s(y, z), s(x, z)} := by classical ext e induction' e using Sym2.inductionOn with u v simp only [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mem_sym2_iff, Finset.mem_insert, Finset.mem_singleton, Sym2.mk_isDiag_iff, Sym2.eq, Sym2.rel_iff', Prod.mk.injEq] aesoplemma simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_encoding_card_three {V : Type*} [DecidableEq V] (t : Finset V) (ht : t.card = 3) : (finite_vertex_set_edge_encoding t).card = 3 := by classical rcases Finset.card_eq_three.mp ht with ⟨x, y, z, hxy, hxz, hyz, rfl⟩ rw [simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_encoding_explicit x y z hxy hxz hyz] have h1 : s(x, y) ≠ s(y, z) := by simp [Sym2.eq, Sym2.rel_iff']; aesop have h2 : s(x, y) ≠ s(x, z) := by simp [Sym2.eq, Sym2.rel_iff']; aesop have h3 : s(y, z) ≠ s(x, z) := by simp [Sym2.eq, Sym2.rel_iff']; aesop rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · simp [h3] · simp [h1, h2]lemma simple_graph_stable_triangle_active_edge_in_maximum_packing_subset_image_has_preimage {α β : Type*} [DecidableEq α] [DecidableEq β] (f : α → β) (S : Finset α) (Q : Finset β) (hQ : Q ⊆ S.image f) : ∃ P : Finset α, P ⊆ S ∧ P.image f = Q ∧ P.card = Q.card := by classical have h_choice : ∀ b ∈ Q, ∃ a ∈ S, f a = b := by intro b hb have := hQ hb rw [Finset.mem_image] at this rcases this with ⟨a, ha, rfl⟩ exact ⟨a, ha, rfl⟩ choose! g hg1 hg2 using h_choice set P := Q.attach.image (fun ⟨b, hb⟩ => g b hb) have hP_sub : P ⊆ S := by intro a ha rw [Finset.mem_image] at ha rcases ha with ⟨⟨b, hb⟩, -, rfl⟩ exact hg1 b hb have hP_im : P.image f = Q := by ext b rw [Finset.mem_image] constructor · rintro ⟨a, ha, rfl⟩ rw [Finset.mem_image] at ha rcases ha with ⟨⟨b', hb'⟩, -, rfl⟩ rw [hg2 b' hb'] exact hb' · intro hb refine ⟨g b hb, ?_, hg2 b hb⟩ rw [Finset.mem_image] exact ⟨⟨b, hb⟩, Finset.mem_attach _ _, rfl⟩ have hP_card : P.card = Q.card := by apply le_antisymm · have := Finset.card_image_le (s := Q.attach) (f := fun ⟨b, hb⟩ => g b hb) simp only [Finset.card_attach] at this exact this · rw [← hP_im] exact Finset.card_image_le exact ⟨P, hP_sub, hP_im, hP_card⟩lemma simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_of_mem_family {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (y : Sym2 V) (hy : y ∈ (simple_graph_triangle_edge_family G).biUnion id) : y ∈ G.edgeSet := by classical rw [Finset.mem_biUnion] at hy rcases hy with ⟨t, ht, hy_in_t⟩ dsimp only [id] at hy_in_t unfold simple_graph_triangle_edge_family at ht rw [Finset.mem_image] at ht rcases ht with ⟨s, hs, rfl⟩ rw [Finset.mem_filter] at hs obtain ⟨-, hclique⟩ := hs rw [finite_vertex_set_edge_encoding, Finset.mem_filter] at hy_in_t obtain ⟨h_sym2, h_nondiag⟩ := hy_in_t induction' y using Sym2.inductionOn with u v simp only [Sym2.mk_isDiag_iff] at h_nondiag simp only [Finset.mem_sym2_iff, Sym2.mem_iff] at h_sym2 have hu : u ∈ s := h_sym2 u (Or.inl rfl) have hv : v ∈ s := h_sym2 v (Or.inr rfl) exact hclique.isClique hu hv h_nondiaglemma simple_graph_stable_triangle_active_edge_in_maximum_packing_not_mem_encoding_of_clique_deleteEdges {V : Type*} [DecidableEq V] (G : SimpleGraph V) (y : Sym2 V) (t : Finset V) (ht : (G.deleteEdges {y}).IsNClique 3 t) : y ∉ finite_vertex_set_edge_encoding t := by classical intro hy rw [finite_vertex_set_edge_encoding, Finset.mem_filter] at hy obtain ⟨h_sym2, h_nondiag⟩ := hy induction' y using Sym2.inductionOn with u v simp only [Sym2.mk_isDiag_iff] at h_nondiag simp only [Finset.mem_sym2_iff, Sym2.mem_iff] at h_sym2 have hu : u ∈ t := h_sym2 u (Or.inl rfl) have hv : v ∈ t := h_sym2 v (Or.inr rfl) have hadj : (G.deleteEdges {s(u, v)}).Adj u v := ht.isClique hu hv h_nondiag rw [SimpleGraph.deleteEdges_adj] at hadj simp at hadjlemma simple_graph_stable_triangle_active_edge_in_maximum_packing_e_in_family_biUnion {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (e : Sym2 V) (he : e ∈ G.edgeSet) (hactive : ∃ t : Finset V, G.IsNClique 3 t ∧ ∀ x ∈ e, x ∈ t) : e ∈ (simple_graph_triangle_edge_family G).biUnion id := by classical rcases hactive with ⟨t, ht, he_in_t⟩ rw [Finset.mem_biUnion] refine ⟨finite_vertex_set_edge_encoding t, ?_, ?_⟩ · unfold simple_graph_triangle_edge_family rw [Finset.mem_image] refine ⟨t, ?_, rfl⟩ rw [Finset.mem_filter] exact ⟨Finset.mem_univ t, ht⟩ · dsimp only [id] rw [finite_vertex_set_edge_encoding, Finset.mem_filter] refine ⟨?_, G.not_isDiag_of_mem_edgeSet he⟩ induction' e using Sym2.inductionOn with u v simp only [Finset.mem_sym2_iff, Sym2.mem_iff] intro x hx exact he_in_t x (Sym2.mem_iff.mpr hx)lemma simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_subset_of_mem_encoding {V : Type*} [DecidableEq V] (t : Finset V) (e : Sym2 V) (he : e ∈ finite_vertex_set_edge_encoding t) : ∀ x ∈ e, x ∈ t := by classical rw [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mem_sym2_iff] at he exact he.1theorem simple_graph_stable_triangle_active_edge_in_maximum_packing {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hstable : ∀ e ∈ G.edgeSet, simple_graph_triangle_packing_number (G.deleteEdges {e}) = simple_graph_triangle_packing_number G) (e : Sym2 V) (he : e ∈ G.edgeSet) (hactive : ∃ t : Finset V, G.IsNClique 3 t ∧ ∀ x ∈ e, x ∈ t) : ∃ P : Finset (Finset V), (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G ∧ ∃ t ∈ P, ∀ x ∈ e, x ∈ t := by classical set k := simple_graph_triangle_packing_number G set F := simple_graph_triangle_edge_family G set T_all := (Finset.univ : Finset (Finset V)).filter (G.IsNClique 3) have hF_def : F = T_all.image finite_vertex_set_edge_encoding := rfl have hthree : ∀ t ∈ F, t.card = 3 := by intro t ht rw [hF_def, Finset.mem_image] at ht rcases ht with ⟨s, hs, rfl⟩ rw [Finset.mem_filter] at hs exact simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_encoding_card_three s hs.2.card_eq have hmax : ∀ P ⊆ F, (P : Set (Finset (Sym2 V))).Pairwise Disjoint → P.card ≤ k := by intro P hP hpw obtain ⟨T, hT_sub, hT_im, hT_card⟩ := simple_graph_stable_triangle_active_edge_in_maximum_packing_subset_image_has_preimage finite_vertex_set_edge_encoding T_all P (by rw [← hF_def]; exact hP) have hsize : ∀ t ∈ T, 2 ≤ t.card := by intro t ht have := hT_sub ht rw [Finset.mem_filter] at this rw [this.2.card_eq] omega have hbridge := finite_vertex_family_edge_packing_cover_bridge T ∅ hsize (by simp) rw [hT_im] at hbridge have hT_pw : (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := hbridge.2.1.mp hpw have hT_clique : ∀ t ∈ T, G.IsNClique 3 t := by intro t ht have := hT_sub ht rw [Finset.mem_filter] at this exact this.2 have hbdd : BddAbove {n | ∃ T : Finset (Finset V), (∀ a ∈ T, G.IsNClique 3 a) ∧ (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} := by refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩ rintro n ⟨T', -, -, rfl⟩ exact Finset.card_le_univ T' have hle : T.card ≤ k := by change T.card ≤ simple_graph_triangle_packing_number G unfold simple_graph_triangle_packing_number exact le_csSup hbdd ⟨T, hT_clique, hT_pw, rfl⟩ omega have hstab : ∀ y ∈ F.biUnion id, ∃ P ⊆ F, (P : Set (Finset (Sym2 V))).Pairwise Disjoint ∧ P.card = k ∧ ∀ s ∈ P, y ∉ s := by intro y hy have hye : y ∈ G.edgeSet := simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_of_mem_family G y hy have hstab_y := hstable y hye set G' := G.deleteEdges {y} set P_set : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ t ∈ T, G'.IsNClique 3 t) ∧ (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} have hbdd' : BddAbove P_set := by refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩ rintro n ⟨T', -, -, rfl⟩ exact Finset.card_le_univ T' have hne' : P_set.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ obtain ⟨T, hT_clique, hT_pw, hT_c⟩ := Nat.sSup_mem hne' hbdd' have hT_card_eq : T.card = k := by have hs : sSup P_set = simple_graph_triangle_packing_number G' := rfl rw [hT_c, hs, hstab_y] have hsize : ∀ t ∈ T, 2 ≤ t.card := by intro t ht rw [(hT_clique t ht).card_eq] omega set P' := T.image finite_vertex_set_edge_encoding have hbridge := finite_vertex_family_edge_packing_cover_bridge T ∅ hsize (by simp) refine ⟨P', ?_, ?_, ?_, ?_⟩ · intro F' hF' rw [Finset.mem_image] at hF' rcases hF' with ⟨t, ht, rfl⟩ rw [hF_def, Finset.mem_image] refine ⟨t, ?_, rfl⟩ rw [Finset.mem_filter] refine ⟨Finset.mem_univ t, ?_⟩ have ht_cl := hT_clique t ht exact ⟨ht_cl.1.mono (G.deleteEdges_le {y}), ht_cl.2⟩ · exact hbridge.2.1.mpr hT_pw · rw [hbridge.1, hT_card_eq] · intro s hs rw [Finset.mem_image] at hs rcases hs with ⟨t, ht, rfl⟩ exact simple_graph_stable_triangle_active_edge_in_maximum_packing_not_mem_encoding_of_clique_deleteEdges G y t (hT_clique t ht) have he_in : e ∈ F.biUnion id := simple_graph_stable_triangle_active_edge_in_maximum_packing_e_in_family_biUnion G e he hactive obtain ⟨Q, hQ_sub, hQ_pw, hQ_card, ⟨s, hs_in_Q, he_in_s⟩⟩ := finite_three_set_stable_maximum_packings_cover_support F k hthree hmax hstab e he_in obtain ⟨P, hP_sub, hP_im, hP_card⟩ := simple_graph_stable_triangle_active_edge_in_maximum_packing_subset_image_has_preimage finite_vertex_set_edge_encoding T_all Q (by rw [← hF_def]; exact hQ_sub) have hsize : ∀ t ∈ P, 2 ≤ t.card := by intro t ht have := hP_sub ht rw [Finset.mem_filter] at this rw [this.2.card_eq] omega have hbridge := finite_vertex_family_edge_packing_cover_bridge P ∅ hsize (by simp) rw [hP_im] at hbridge refine ⟨P, ?_, ?_, ?_, ?_⟩ · intro t ht have := hP_sub ht rw [Finset.mem_filter] at this exact this.2 · exact hbridge.2.1.mp hQ_pw · rw [hP_card, hQ_card] · rw [← hP_im, Finset.mem_image] at hs_in_Q rcases hs_in_Q with ⟨t, ht, rfl⟩ refine ⟨t, ht, ?_⟩ exact simple_graph_stable_triangle_active_edge_in_maximum_packing_edge_subset_of_mem_encoding t e he_in_s