simple_graph_triangle_packing_number_le_delete_edge_add_one
Deleting an edge e from G decreases the triangle packing number by at most 1: ν(G) ≤ ν(G \ {e}) + 1.
Statement
theorem simple_graph_triangle_packing_number_le_delete_edge_add_one {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (e : Sym2 V) (he : e ∈ G.edgeSet) : simple_graph_triangle_packing_number G ≤ simple_graph_triangle_packing_number (G.deleteEdges {e}) + 1
- Source
- step towards simple_graph_triangle_cover_number_le_two_mul_packing_number
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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).
- simple_graph_triangle_packing_number_eq_zero_of_clique_freeA triangle-free graph has triangle packing number 0.
The proof, explained
Let T be a maximum triangle packing in G, so that |T| = ν(G). Because triangles in a packing pairwise share at most one vertex, at most one triangle in T can contain both endpoints of the edge e. Removing this triangle (if present) leaves a subcollection T' of size at least |T| - 1. Every triangle in T' avoids e and therefore remains a 3-clique in G \ {e}, making T' a valid triangle packing in G \ {e} and proving ν(G) ≤ |T'| + 1 ≤ ν(G \ {e}) + 1.
There exists an optimal triangle packing T in G whose size attains ν(G).
We define P as the set of sizes of all triangle packings in G (families of 3-cliques that pairwise intersect in at most one vertex). Because the vertex set V is finite, the collection of all subsets of V is finite, so P is bounded above by the cardinality of the universe. The empty packing shows that 0 ∈ P, so P is nonempty. By Nat.sSup_mem, the supremum of P belongs to P, giving a triangle packing T such that |T| = sSup P = ν(G).
uses
Finset.card_le_univ,Nat.sSup_memclassical set P : 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} with hP have hbdd : BddAbove P := by refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩ rintro n ⟨T, -, -, rfl⟩ exact Finset.card_le_univ T have hne : P.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ obtain ⟨T, hT, hTp, hTc⟩ := Nat.sSup_mem hne hbdd have hG_eq : simple_graph_triangle_packing_number G = T.card := by change sSup P = T.card exact hTc.symm
At most one triangle in T contains the edge e.
Let p(t) be the property that both endpoints of e lie in t. Since e is an edge of G, it is not a diagonal, so e = s(u, v) with u ≠ v. If two distinct triangles t₁, t₂ ∈ T both contained e, then {u, v} ⊆ t₁ ∩ t₂. Since u ≠ v, this would imply |t₁ ∩ t₂| ≥ |{u, v}| = 2. But distinct triangles in a packing pairwise share at most one vertex (|t₁ ∩ t₂| ≤ 1), a contradiction. Hence at most one triangle in T contains e.
uses
Sym2.inductionOn,Sym2.mk_isDiag_iff,Finset.card_le_one_iff,Finset.mem_filter,Finset.mem_insert,Finset.mem_singleton,Finset.card_pair,Finset.card_le_cardlet p : Finset V → Prop := fun t => ∀ x ∈ e, x ∈ t have hp_card : (T.filter p).card ≤ 1 := by obtain ⟨u, v, huv, rfl⟩ : ∃ u v, u ≠ v ∧ e = s(u, v) := by have hdiag := G.not_isDiag_of_mem_edgeSet he induction' e using Sym2.inductionOn with u v simp only [Sym2.mk_isDiag_iff] at hdiag exact ⟨u, v, hdiag, rfl⟩ rw [Finset.card_le_one_iff] intro t1 t2 ht1 ht2 rw [Finset.mem_filter] at ht1 ht2 by_contra hne_t have hpw := hTp ht1.1 ht2.1 hne_t have hu1 : u ∈ t1 := ht1.2 u (by simp) have hv1 : v ∈ t1 := ht1.2 v (by simp) have hu2 : u ∈ t2 := ht2.2 u (by simp) have hv2 : v ∈ t2 := ht2.2 v (by simp) have h2 : 2 ≤ (t1 ∩ t2).card := by have h_sub : {u, v} ⊆ t1 ∩ t2 := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl · simp [hu1, hu2] · simp [hv1, hv2] have h_card : ({u, v} : Finset V).card = 2 := Finset.card_pair huv rw [← h_card] exact Finset.card_le_card h_sub omega
The subcollection T' of triangles not containing e satisfies |T| ≤ |T'| + 1.
Let T' be the collection of triangles in T that do not satisfy p. Since T is partitioned into triangles satisfying p and those satisfying ¬p, |T| = |T.filter p| + |T'|. Because |T.filter p| ≤ 1, it follows that |T| ≤ |T'| + 1.
uses
Finset.card_filter_add_card_filter_notlet T' := T.filter (fun t => ¬ p t) have hT'_card : T.card ≤ T'.card + 1 := by have hsplit : (T.filter p).card + T'.card = T.card := Finset.card_filter_add_card_filter_not p omega
Every triangle in T' is a 3-clique in G \ {e}.
Each t ∈ T' is a 3-clique in G, so |t| = 3. For any two distinct vertices x, y ∈ t, the edge s(x, y) belongs to G. If s(x, y) were equal to e, then both endpoints of e would belong to t, contradicting t ∈ T'. Hence s(x, y) ≠ e, which means the edge survives in G \ {e} by SimpleGraph.deleteEdges_adj.
uses
Finset.mem_filter,SimpleGraph.deleteEdges_adj,Set.mem_singleton_iff,Sym2.mem_iffhave hT'_clique : ∀ t ∈ T', (G.deleteEdges {e}).IsNClique 3 t := by intro t ht rw [Finset.mem_filter] at ht obtain ⟨htT, hnot_p⟩ := ht have hclique := hT t htT refine ⟨?_, hclique.card_eq⟩ intro x hx y hy hxy rw [SimpleGraph.deleteEdges_adj] refine ⟨hclique.isClique hx hy hxy, ?_⟩ intro heq simp only [Set.mem_singleton_iff] at heq apply hnot_p intro z hz rw [← heq] at hz simp only [Sym2.mem_iff] at hz rcases hz with rfl | rfl · exact hx · exact hy
The triangles in T' are pairwise edge-disjoint.
Because T' is a subcollection of T, the property that any two distinct triangles share at most one vertex is directly inherited from T.
uses
Finset.mem_coe,Finset.mem_filterhave hT'_pw : (T' : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by refine hTp.mono ?_ intro t ht rw [Finset.mem_coe, Finset.mem_filter] at ht exact Finset.mem_coe.2 ht.1
The size of T' is at most ν(G \ {e}).
The triangle packing number ν(G \ {e}) is the supremum of cardinalities of all triangle packings in G \ {e}. Since T' is a valid packing in G \ {e}, its size belongs to this set, which is bounded above. Therefore |T'| ≤ ν(G \ {e}) by le_csSup.
uses
Finset.card_le_univ,le_csSuphave hT'_le : T'.card ≤ simple_graph_triangle_packing_number (G.deleteEdges {e}) := by unfold simple_graph_triangle_packing_number have hbdd' : BddAbove {n | ∃ T : Finset (Finset V), (∀ t ∈ T, (G.deleteEdges {e}).IsNClique 3 t) ∧ (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'' exact le_csSup hbdd' ⟨T', hT'_clique, hT'_pw, rfl⟩
ν(G) ≤ ν(G \ {e}) + 1.
Combining ν(G) = |T|, |T| ≤ |T'| + 1, and |T'| ≤ ν(G \ {e}) via linear arithmetic over ℕ establishes the desired inequality.
omega
Finset.card_le_univ- The cardinality of any finset in a finite type is at most the cardinality of the universe.
Nat.sSup_mem- A nonempty set of natural numbers bounded above contains its supremum.
Sym2.inductionOn- To prove a property for all unordered pairs, it suffices to prove it for pairs of the form s(x, y).
Sym2.mk_isDiag_iff- An unordered pair s(x, y) is a diagonal (a self-loop) if and only if x = y.
Finset.card_le_one_iff- A finset has cardinality at most 1 if and only if any two of its elements are equal.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Finset.card_pair- The pair {a, b} has cardinality 2 if a ≠ b.
Finset.card_le_card- If s ⊆ t for finsets s and t, then |s| ≤ |t|.
Finset.card_filter_add_card_filter_not- For any predicate p on a finset s, the number of elements satisfying p plus the number satisfying ¬p equals |s|.
SimpleGraph.deleteEdges_adj- Vertices v and w are adjacent in G.deleteEdges s if and only if they are adjacent in G and the edge s(v, w) is not in s.
Set.mem_singleton_iff- An element belongs to the singleton set {b} if and only if it equals b.
Sym2.mem_iff- An element a belongs to the unordered pair s(b, c) if and only if a = b or a = c.
Finset.mem_coe- Membership in a coerced finset is equivalent to membership in the finset itself.
le_csSup- In a conditionally complete lattice, any element of a set bounded above is at most the supremum of that set.
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.
/-- Deleting an edge e from G decreases the triangle packing number by at most 1: ν(G) ≤ ν(G \ {e}) + 1. -/theorem simple_graph_triangle_packing_number_le_delete_edge_add_one {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (e : Sym2 V) (he : e ∈ G.edgeSet) : simple_graph_triangle_packing_number G ≤ simple_graph_triangle_packing_number (G.deleteEdges {e}) + 1 := by classical set P : 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} with hP have hbdd : BddAbove P := by refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩ rintro n ⟨T, -, -, rfl⟩ exact Finset.card_le_univ T have hne : P.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ obtain ⟨T, hT, hTp, hTc⟩ := Nat.sSup_mem hne hbdd have hG_eq : simple_graph_triangle_packing_number G = T.card := by change sSup P = T.card exact hTc.symm let p : Finset V → Prop := fun t => ∀ x ∈ e, x ∈ t have hp_card : (T.filter p).card ≤ 1 := by obtain ⟨u, v, huv, rfl⟩ : ∃ u v, u ≠ v ∧ e = s(u, v) := by have hdiag := G.not_isDiag_of_mem_edgeSet he induction' e using Sym2.inductionOn with u v simp only [Sym2.mk_isDiag_iff] at hdiag exact ⟨u, v, hdiag, rfl⟩ rw [Finset.card_le_one_iff] intro t1 t2 ht1 ht2 rw [Finset.mem_filter] at ht1 ht2 by_contra hne_t have hpw := hTp ht1.1 ht2.1 hne_t have hu1 : u ∈ t1 := ht1.2 u (by simp) have hv1 : v ∈ t1 := ht1.2 v (by simp) have hu2 : u ∈ t2 := ht2.2 u (by simp) have hv2 : v ∈ t2 := ht2.2 v (by simp) have h2 : 2 ≤ (t1 ∩ t2).card := by have h_sub : {u, v} ⊆ t1 ∩ t2 := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl · simp [hu1, hu2] · simp [hv1, hv2] have h_card : ({u, v} : Finset V).card = 2 := Finset.card_pair huv rw [← h_card] exact Finset.card_le_card h_sub omega let T' := T.filter (fun t => ¬ p t) have hT'_card : T.card ≤ T'.card + 1 := by have hsplit : (T.filter p).card + T'.card = T.card := Finset.card_filter_add_card_filter_not p omega have hT'_clique : ∀ t ∈ T', (G.deleteEdges {e}).IsNClique 3 t := by intro t ht rw [Finset.mem_filter] at ht obtain ⟨htT, hnot_p⟩ := ht have hclique := hT t htT refine ⟨?_, hclique.card_eq⟩ intro x hx y hy hxy rw [SimpleGraph.deleteEdges_adj] refine ⟨hclique.isClique hx hy hxy, ?_⟩ intro heq simp only [Set.mem_singleton_iff] at heq apply hnot_p intro z hz rw [← heq] at hz simp only [Sym2.mem_iff] at hz rcases hz with rfl | rfl · exact hx · exact hy have hT'_pw : (T' : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by refine hTp.mono ?_ intro t ht rw [Finset.mem_coe, Finset.mem_filter] at ht exact Finset.mem_coe.2 ht.1 have hT'_le : T'.card ≤ simple_graph_triangle_packing_number (G.deleteEdges {e}) := by unfold simple_graph_triangle_packing_number have hbdd' : BddAbove {n | ∃ T : Finset (Finset V), (∀ t ∈ T, (G.deleteEdges {e}).IsNClique 3 t) ∧ (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'' exact le_csSup hbdd' ⟨T', hT'_clique, hT'_pw, rfl⟩ omega