simple_graph_triangle_packing_number_mono
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
- 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.
- Used by 6
- simple_graph_external_k4_private_pair_decreases_packingLet P be a maximum edge-disjoint triangle packing containing abc, and let a and b occur in no other triangle of P. If x lies outside the…
- simple_graph_stable_disjoint_edges_outside_packing_incompatible_exampleThere is a stable graph of triangle packing number three, a maximum packing P, and a five-edge triangle cover containing two…
- simple_graph_triangle_packing_number_delete_edge_lt_or_eqFor every finite graph G, either some single-edge deletion strictly decreases the triangle packing number, or every single-edge deletion…
- 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.
- simple_graph_triangle_packing_decreases_of_high_codegreeDeleting an edge with more than twice the maximum triangle packing number common neighbors strictly decreases the packing number.
- simple_graph_triangle_cover_number_le_two_mul_packing_number_of_decreasing_edgeInduction step for the easy branch: if every graph on the same vertex type with strictly smaller triangle packing number satisfies τ ≤ 2ν,…
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.
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.
unfold simple_graph_triangle_packing_numberTo 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.
uses
csSup_le_csSupapply csSup_le_csSupThe 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.
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
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.
· -- the set of admissible packing sizes of H is nonempty (empty packing) exact ⟨0, ∅, by simp, by simp, rfl⟩
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.
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
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.
/-- 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⟩