simple_graph_triangle_packing_number_eq_zero_of_clique_free
A triangle-free graph has triangle packing number 0.
Statement
theorem simple_graph_triangle_packing_number_eq_zero_of_clique_free {V : Type*} [DecidableEq V] (G : SimpleGraph V) (h : G.CliqueFree 3) : simple_graph_triangle_packing_number G = 0
- Source
- Sanity lemma for the triangle packing number, arXiv:2610.15539 (Tuza's conjecture under an edge-count condition).
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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).
- Used by 3
- simple_graph_triangle_packing_number_le_delete_edge_add_oneDeleting an edge e from G decreases the triangle packing number by at most 1: ν(G) ≤ ν(G \ {e}) + 1.
- simple_graph_triangle_packing_number_monoTriangle packing number is monotone under subgraph inclusion: if H ≤ G, then ν(H) ≤ ν(G).
- simple_graph_triangle_free_pair_stable_nonbipartite_exampleA triangle-free two-edge-stable graph can fail to be bipartite; its empty packing is maximum and support-maximal.
The proof, explained
The triangle packing number of a graph is the supremum of the cardinalities of collections of pairwise edge-disjoint triangles. Because the graph is assumed to be triangle-free (3-clique-free), it cannot contain any triangles, so any valid triangle packing must be empty. Consequently, the only achievable packing cardinality is 0 (witnessed by the empty packing), and the packing number is the supremum of {0}, which is 0.
The triangle packing number of G is, by definition, the supremum of the cardinalities of all families of pairwise almost-disjoint triangles in G.
We unfold the definition of `simple_graph_triangle_packing_number`, transforming the goal into showing that the supremum of the set of integers n for which there exists a triangle packing of size n is 0.
unfold simple_graph_triangle_packing_numberThe set of sizes of valid triangle packings in G is the singleton {0}, which reduces to showing that an integer n is an achievable packing size if and only if n = 0.
We assert that the set of achievable packing sizes is {0}. By set extensionality (`ext`) and unfolding set membership (`Set.mem_ofPred_eq`, `Set.mem_singleton_iff`), this equality is equivalent to proving that a packing of size n exists if and only if n = 0.
uses
Set.mem_ofPred_eq,Set.mem_singleton_iffhave : {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} = {0} := by ext n simp only [Set.mem_ofPred_eq, Set.mem_singleton_iff] constructor
Any valid triangle packing in G must be empty, so its cardinality is 0.
Suppose T is a triangle packing in G of size n. A finite set has cardinality 0 if and only if it is empty, which in turn means it contains no elements (`Finset.card_eq_zero`, `Finset.eq_empty_iff_forall_notMem`). If T contained any element t, then t would be a 3-clique in G, contradicting the hypothesis h that G has no 3-cliques. Hence T must be empty and n = |T| = 0.
uses
Finset.card_eq_zero,Finset.eq_empty_iff_forall_notMem· rintro ⟨T, hT, -, rfl⟩ rw [Finset.card_eq_zero, Finset.eq_empty_iff_forall_notMem] exact fun t ht => h t (hT t ht)
The packing size 0 is achievable by taking the empty collection of triangles.
Conversely, for n = 0, the empty set ∅ provides the required witness: vacuously, every element of ∅ is a 3-clique and any two elements meet in at most one vertex, and |∅| = 0.
· rintro rfl exact ⟨∅, by simp, by simp, rfl⟩
The supremum of the set of packing sizes is 0, concluding the proof.
Substituting the established equality that the set of packing sizes is {0}, the goal simplifies to sSup {0} = 0, which holds by `csSup_singleton`.
uses
csSup_singletonrw [this, csSup_singleton]
Set.mem_ofPred_eq- An element belongs to the set defined by a predicate if and only if the predicate holds for that element.
Set.mem_singleton_iff- An element belongs to the singleton set {b} if and only if it equals b.
Finset.card_eq_zero- A finite set has cardinality 0 if and only if it is the empty set.
Finset.eq_empty_iff_forall_notMem- A finite set is empty if and only if it contains no elements.
csSup_singleton- The supremum of a singleton set {a} in a conditionally complete order is a.
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.
theorem simple_graph_triangle_packing_number_eq_zero_of_clique_free {V : Type*} [DecidableEq V] (G : SimpleGraph V) (h : G.CliqueFree 3) : simple_graph_triangle_packing_number G = 0 := by unfold simple_graph_triangle_packing_number have : {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} = {0} := by ext n simp only [Set.mem_ofPred_eq, Set.mem_singleton_iff] constructor · rintro ⟨T, hT, -, rfl⟩ rw [Finset.card_eq_zero, Finset.eq_empty_iff_forall_notMem] exact fun t ht => h t (hT t ht) · rintro rfl exact ⟨∅, by simp, by simp, rfl⟩ rw [this, csSup_singleton]