AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_packing_number_mono

theoremverified

Triangle packing number is monotone under subgraph inclusion: if H ≤ G, then ν(H) ≤ ν(G).

Statement

theorem simple_graph_triangle_packing_number_mono {V : Type*} [Fintype V] [DecidableEq V]
    (G H : SimpleGraph V) (hle : H ≤ G) :
    simple_graph_triangle_packing_number H ≤ simple_graph_triangle_packing_number G
Source
step towards simple_graph_triangle_cover_number_le_two_mul_packing_number
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 6

The proof, explained

The triangle packing number is defined as the supremum of sizes of pairwise edge-disjoint collections of triangles. Since any triangle in a subgraph H is also a triangle in G, any packing in H is also a packing in G. The result then follows by monotonicity of the supremum for bounded-above, nonempty sets.

  1. Expand the definition of the triangle packing number as the supremum of sizes of triangle packings.

    We unfold the definition of simple_graph_triangle_packing_number.

    line 5

      unfold simple_graph_triangle_packing_number
  2. To show the inequality between the suprema, it suffices to show that the target set is bounded above, the source set is nonempty, and the source set is a subset of the target set.

    We apply csSup_le_csSup.

    line 6

    uses csSup_le_csSup

      apply csSup_le_csSup
  3. The set of packing sizes of G is bounded above by the total number of subsets of V.

    Any packing T is a collection of subsets of V, so its size is at most the total number of subsets of V, by Finset.card_le_univ.

    lines 7–10

    uses Finset.card_le_univ

      · -- the packing numbers of G are bounded by the number of vertex subsets
        refine ⟨Fintype.card (Finset V), ?_⟩
        rintro n ⟨T, -, -, rfl⟩
        exact Finset.card_le_univ T
  4. The set of packing sizes in H is nonempty because the empty family is a valid triangle packing of size 0. automation

    The empty set vacuously contains only triangles and has pairwise intersections of size at most 1.

    lines 11–12

      · -- the set of admissible packing sizes of H is nonempty (empty packing)
        exact ⟨0, ∅, by simp, by simp, rfl⟩
  5. Every triangle packing in H is also a triangle packing in G.

    Since H ≤ G, any clique in H is also a clique in G, while the pairwise intersection condition does not depend on the graph.

    lines 13–15

    uses SimpleGraph.IsNClique.mono

      · -- every packing of H is a packing of G, as triangles persist under supergraphs
        rintro n ⟨T, hT, hpw, rfl⟩
        exact ⟨T, fun t ht => (hT t ht).mono hle, hpw, rfl⟩
csSup_le_csSup
The supremum of a set is bounded by the supremum of another if the second is bounded above, the first is nonempty, and the first is a subset of the second
Finset.card_le_univ
The cardinality of any finset is bounded by the cardinality of the ambient finite type
SimpleGraph.IsNClique.mono
If a subgraph has an n-clique, the supergraph also has it

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

/-- Triangle packing number is monotone under subgraph inclusion: if H ≤ G, then ν(H) ≤ ν(G). -/theorem simple_graph_triangle_packing_number_mono {V : Type*} [Fintype V] [DecidableEq V]    (G H : SimpleGraph V) (hle : H ≤ G) :    simple_graph_triangle_packing_number H ≤ simple_graph_triangle_packing_number G := by  unfold simple_graph_triangle_packing_number  apply csSup_le_csSup  · -- the packing numbers of G are bounded by the number of vertex subsets    refine ⟨Fintype.card (Finset V), ?_⟩    rintro n ⟨T, -, -, rfl⟩    exact Finset.card_le_univ T  · -- the set of admissible packing sizes of H is nonempty (empty packing)    exact ⟨0, ∅, by simp, by simp, rfl⟩  · -- every packing of H is a packing of G, as triangles persist under supergraphs    rintro n ⟨T, hT, hpw, rfl⟩    exact ⟨T, fun t ht => (hT t ht).mono hle, hpw, rfl⟩
See it in the graphDiscuss this resultChallenge it