AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_packing_number_eq_zero_of_clique_free

theoremverified

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
Used by 3

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.

  1. 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.

    line 3

      unfold simple_graph_triangle_packing_number
  2. The 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.

    lines 4–8

    uses Set.mem_ofPred_eq, Set.mem_singleton_iff

      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
  3. 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.

    lines 9–11

    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)
  4. 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.

    lines 12–13

        · rintro rfl
          exact ⟨∅, by simp, by simp, rfl⟩
  5. 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`.

    line 14

    uses csSup_singleton

      rw [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

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]
See it in the graphDiscuss this resultChallenge it