simple_graph_triangle_packing_number_induce_le
The triangle packing number of an induced subgraph is at most that of the whole graph.
Statement
theorem simple_graph_triangle_packing_number_induce_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (S : Finset V) : simple_graph_triangle_packing_number (G.induce (S : Set V)) ≤ simple_graph_triangle_packing_number G
- Source
- Induced-kernel transport prerequisite for the triangle packing campaign.
- Verified
- 04 Nov 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 1
- simple_graph_triangle_packing_number_induce_eq_of_packing_subsetIf a subset S contains all vertices of a maximum packing of triangles in G, then the triangle packing number of the induced subgraph G[S]…
The proof, explained
The triangle packing number of a graph is defined as the supremum of cardinalities of families of edge-disjoint triangles (sharing at most one vertex). Given any triangle packing in the induced subgraph G[S], pushing its triangles forward along the canonical inclusion S ↪ V produces a triangle packing in G of the exact same size. Since these achievable packing sizes form non-empty, bounded sets of natural numbers, the inclusion of achievable sizes implies that the packing number of the induced subgraph is at most that of the whole graph.
The inequality between triangle packing numbers reduces to showing that the set of achievable packing sizes in G is bounded above, the set in G[S] is nonempty, and every packing size achievable in G[S] is also achievable in G.
We define the subtype embedding f : S ↪ V and the induced map e : Finset S ↪ Finset V on vertex subsets, which is injective by Finset.map_injective. Unfolding the definition of the triangle packing number as the supremum of packing cardinalities, csSup_le_csSup reduces the inequality to verifying that the achievable packing sizes in G are bounded above, those in G[S] are nonempty, and any packing size in G[S] can be achieved in G.
uses
Function.Embedding.subtype,Finset.map_injective,csSup_le_csSupclassical let f : S ↪ V := Function.Embedding.subtype (fun x => x ∈ S) let e : Finset S ↪ Finset V := ⟨fun t => t.map f, Finset.map_injective f⟩ unfold simple_graph_triangle_packing_number apply csSup_le_csSup
The set of triangle packing sizes in G is bounded above.
The total number of finite subsets of V, |Finset V|, serves as an upper bound: any triangle packing T is a subset of Finset V, so its cardinality satisfies |T| ≤ |Finset V| by Finset.card_le_univ.
uses
Finset.card_le_univ· refine ⟨Fintype.card (Finset V), ?_⟩ rintro n ⟨T, _, _, rfl⟩ exact Finset.card_le_univ T
The set of triangle packing sizes in G[S] is nonempty.
The empty set ∅ is a valid triangle packing of size 0, since the requirement that every element is a triangle and the pairwise intersection condition both hold vacuously.
· exact ⟨0, ∅, by simp, by simp, rfl⟩
Any packing size n achievable in G[S] can be achieved in G by mapping the packing forward along e.
Given an edge-disjoint triangle packing T of size n in G[S], we consider its image T.map e in G. Since e is an embedding, Finset.card_map guarantees that |T.map e| = |T| = n. It remains to show that every member of T.map e is a triangle in G and that they pairwise share at most one vertex.
uses
Finset.card_map· rintro n ⟨T, hT, hpw, rfl⟩ refine ⟨T.map e, ?_, ?_, Finset.card_map _⟩
Every element of the pushed-forward packing is a triangle (3-clique) in G.
Any element t ∈ T.map e has the form e(s) for some s ∈ T by Finset.mem_map.mp. By G.isNClique_induce_iff, a vertex subset in the induced subgraph is a 3-clique if and only if its image in the ambient graph is a 3-clique. Since s is a triangle in G[S], e(s) is a triangle in G.
uses
Finset.mem_map.mp,G.isNClique_induce_iff· intro t ht obtain ⟨s, hs, rfl⟩ := Finset.mem_map.mp ht exact (G.isNClique_induce_iff (S : Set V) s 3).mp (hT s hs)
The triangles in the pushed-forward packing pairwise share at most one vertex.
Let s, t ∈ T.map e be distinct triangles. By Finset.mem_map.mp, s = e(s') and t = e(t') for s', t' ∈ T. Since e(s') ≠ e(t'), congruence with e (congrArg) implies s' ≠ t', so |s' ∩ t'| ≤ 1 by the pairwise property of T. Since e(s') = s'.map f and e(t') = t'.map f, Finset.map_inter gives e(s') ∩ e(t') = (s' ∩ t').map f. Finally, Finset.card_map shows |e(s') ∩ e(t')| = |s' ∩ t'| ≤ 1.
uses
Finset.mem_map.mp,congrArg,Finset.map_inter,Finset.card_map· intro s hs t ht hne obtain ⟨s', hs', rfl⟩ := Finset.mem_map.mp hs obtain ⟨t', ht', rfl⟩ := Finset.mem_map.mp ht have hne' : s' ≠ t' := by intro h; exact hne (congrArg e h) have h := hpw hs' ht' hne' change ((s'.map f) ∩ (t'.map f)).card ≤ 1 rw [← Finset.map_inter, Finset.card_map] exact h
Function.Embedding.subtype- The canonical inclusion of a subtype into its ambient type as an embedding.
Finset.map_injective- Mapping a finite set along an injective function is an injective operation on finite sets.
csSup_le_csSup- In a conditionally complete lattice, if t is bounded above, s is nonempty, and s ⊆ t, then sSup s ≤ sSup t.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the total cardinality of that type.
Finset.card_map- The image of a finite set under an embedding has the same cardinality as the original set.
Finset.mem_map.mp- An element belongs to the image of a finite set under an embedding if and only if it is the image of some element in that set.
G.isNClique_induce_iff- A finite set of vertices in an induced subgraph induces an n-clique if and only if its image in the ambient graph induces an n-clique.
congrArg- Applying a function to equal inputs yields equal outputs.
Finset.map_inter- The image of the intersection of two finite sets under an embedding equals the intersection of their images.
- In Lean, the vertices of the induced subgraph G[S] belong to the subtype S rather than V. Consequently, subgraphs and triangle packings in G[S] are formally pushed forward to G via the explicit subtype embedding f : S ↪ V and the induced map e : Finset S ↪ Finset V.
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_induce_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (S : Finset V) : simple_graph_triangle_packing_number (G.induce (S : Set V)) ≤ simple_graph_triangle_packing_number G := by classical let f : S ↪ V := Function.Embedding.subtype (fun x => x ∈ S) let e : Finset S ↪ Finset V := ⟨fun t => t.map f, Finset.map_injective f⟩ unfold simple_graph_triangle_packing_number apply csSup_le_csSup · refine ⟨Fintype.card (Finset V), ?_⟩ rintro n ⟨T, _, _, rfl⟩ exact Finset.card_le_univ T · exact ⟨0, ∅, by simp, by simp, rfl⟩ · rintro n ⟨T, hT, hpw, rfl⟩ refine ⟨T.map e, ?_, ?_, Finset.card_map _⟩ · intro t ht obtain ⟨s, hs, rfl⟩ := Finset.mem_map.mp ht exact (G.isNClique_induce_iff (S : Set V) s 3).mp (hT s hs) · intro s hs t ht hne obtain ⟨s', hs', rfl⟩ := Finset.mem_map.mp hs obtain ⟨t', ht', rfl⟩ := Finset.mem_map.mp ht have hne' : s' ≠ t' := by intro h; exact hne (congrArg e h) have h := hpw hs' ht' hne' change ((s'.map f) ∩ (t'.map f)).card ≤ 1 rw [← Finset.map_inter, Finset.card_map] exact h