simple_graph_triangle_packing_number_induce_eq_of_packing_subset
If 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] equals that of G.
Statement
theorem simple_graph_triangle_packing_number_induce_eq_of_packing_subset {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (S : Finset V) (T : Finset (Finset V)) (hT : ∀ t ∈ T, G.IsNClique 3 t) (hTp : (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) (hTc : T.card = simple_graph_triangle_packing_number G) (hsub : ∀ t ∈ T, ∀ x ∈ t, x ∈ S) : simple_graph_triangle_packing_number (G.induce (S : Set V)) = simple_graph_triangle_packing_number G
- Source
- step towards simple_graph_triangle_packing_cover_bounded_induced_kernel
- Verified
- 04 Nov 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_induce_leThe triangle packing number of an induced subgraph is at most that of the whole graph.
The proof, explained
The theorem is proved by establishing two inequalities. The triangle packing number of an induced subgraph G[S] is always at most that of G because any packing in G[S] is also a packing in G. Conversely, since S contains all vertices of a maximum triangle packing T of G, restricting each triangle in T to S yields a valid edge-disjoint packing of triangles in G[S] of size |T| = ν(G), showing ν(G[S]) ≥ ν(G).
Each triangle in the packing T restricts to a subset of S that embeds back to the original triangle.
Using classical logic, define f to map any vertex set to its subtype restriction in S, let emb : S ↪ V be the subtype inclusion, and let U = f(T). For each triangle t ∈ T, all vertices of t lie in S by assumption (hsub), so embedding f(t) back into V recovers t identically (Finset.subtype_map_of_mem).
uses
Finset.subtype_map_of_memclassical let f : Finset V → Finset S := fun t => t.subtype (fun x => x ∈ S) let emb : S ↪ V := Function.Embedding.subtype (fun x => x ∈ S) let U := T.image f have hmap : ∀ t ∈ T, (f t).map emb = t := by intro t ht exact Finset.subtype_map_of_mem (hsub t ht)
The restriction map f is injective on T, so |U| = |T|.
If f(a) = f(b) for a, b ∈ T, applying the inclusion embedding to both sides (congrArg) and substituting the recovery identity gives a = b. Because f is injective on T, the image U has the same cardinality as T (Finset.card_image_iff.mpr).
uses
congrArg,Finset.card_image_iff.mprhave hinj : Set.InjOn f T := by intro a ha b hb hab have heq := congrArg (fun t : Finset S => t.map emb) hab rw [hmap a ha, hmap b hb] at heq exact heq have hcard : U.card = T.card := Finset.card_image_iff.mpr hinj
Every element of U is a triangle in the induced subgraph G[S].
Any t ∈ U is f(s) for some s ∈ T. By G.isNClique_induce_iff, f(s) is a 3-clique in the induced subgraph G[S] if and only if its image under inclusion in V is a 3-clique in G. That image is s, which is a 3-clique in G by the assumption hT.
uses
Finset.mem_image.mp,G.isNClique_induce_iffhave hc : ∀ t ∈ U, (G.induce (S : Set V)).IsNClique 3 t := by intro t ht obtain ⟨s, hs, rfl⟩ := Finset.mem_image.mp ht apply (G.isNClique_induce_iff (S : Set V) (f s) 3).mpr change G.IsNClique 3 ((f s).map emb) rw [hmap s hs] exact hT s hs
Any two distinct triangles in U share at most one vertex.
Let s, t ∈ U be distinct, corresponding to distinct triangles s', t' ∈ T. Because the inclusion embedding preserves intersections (Finset.map_inter) and embeddings preserve cardinality, |s ∩ t| = |s' ∩ t'|. Since T is a triangle packing (hTp), |s' ∩ t'| ≤ 1, hence |s ∩ t| ≤ 1.
uses
Finset.mem_image.mp,congrArg,Finset.map_interhave hp : (U : Set (Finset S)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by intro s hs t ht hne obtain ⟨s', hs', rfl⟩ := Finset.mem_image.mp hs obtain ⟨t', ht', rfl⟩ := Finset.mem_image.mp ht have hne' : s' ≠ t' := by intro h; exact hne (congrArg f h) have h := hTp hs' ht' hne' have hi : ((f s' ∩ f t').map emb).card = (s' ∩ t').card := by rw [Finset.map_inter, hmap s' hs', hmap t' ht'] simpa using hi.trans_le h
The triangle packing number of G[S] is at least |T|.
By definition, the triangle packing number is the supremum of sizes of triangle packings. In the finite type Finset S, packing sizes are bounded above by the total number of subsets (Finset.card_le_univ). Since U is a valid packing in G[S] of size |T|, |T| is bounded above by the supremum (le_csSup).
uses
le_csSup,Finset.card_le_univhave hl : T.card ≤ simple_graph_triangle_packing_number (G.induce (S : Set V)) := by unfold simple_graph_triangle_packing_number apply le_csSup · refine ⟨Fintype.card (Finset S), ?_⟩ rintro n ⟨P, _, _, rfl⟩ exact Finset.card_le_univ P · exact ⟨U, hc, hp, hcard⟩
The triangle packing number of G[S] equals that of G.
The triangle packing number of any induced subgraph G[S] is at most that of G (simple_graph_triangle_packing_number_induce_le). Since T was chosen to be a maximum packing of G, |T| is the packing number of G (hTc), so the previous step gives the reverse inequality. Antisymmetry of ≤ (le_antisymm) concludes that the two packing numbers are equal.
uses
le_antisymm,simple_graph_triangle_packing_number_induce_leapply le_antisymm (simple_graph_triangle_packing_number_induce_le G S) simpa [hTc] using hl
Finset.subtype_map_of_mem- If every element of a finite set s satisfies property p, restricting s to the subtype and then embedding back recovers s.
congrArg- Functions preserve equality: if a₁ = a₂, then f(a₁) = f(a₂).
Finset.card_image_iff.mpr- A function that is injective on a finite set preserves cardinality under its image.
Finset.mem_image.mp- An element belongs to the image f(s) if and only if it is the image of some element in s.
G.isNClique_induce_iff- A vertex subset in the induced subgraph G[S] is an n-clique if and only if its image under the subtype inclusion is an n-clique in G.
Finset.map_inter- Mapping by an embedding distributes over intersections of finite sets.
le_csSup- Any element of a set bounded above in a conditionally complete lattice is at most the supremum of the set.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the type.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
simple_graph_triangle_packing_number_induce_le- The triangle packing number of an induced subgraph G[S] is at most the triangle packing number of G.
- The proof represents a triangle packing as a collection of 3-cliques whose pairwise intersections have size at most 1, which corresponds to edge-disjoint triangles.
- Because the vertices of the induced subgraph G[S] form a subtype `S`, Finset embeddings (`emb : S ↪ V`) and subtype restrictions are used to translate cliques between G and G[S].
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_eq_of_packing_subset {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (S : Finset V) (T : Finset (Finset V)) (hT : ∀ t ∈ T, G.IsNClique 3 t) (hTp : (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) (hTc : T.card = simple_graph_triangle_packing_number G) (hsub : ∀ t ∈ T, ∀ x ∈ t, x ∈ S) : simple_graph_triangle_packing_number (G.induce (S : Set V)) = simple_graph_triangle_packing_number G := by classical let f : Finset V → Finset S := fun t => t.subtype (fun x => x ∈ S) let emb : S ↪ V := Function.Embedding.subtype (fun x => x ∈ S) let U := T.image f have hmap : ∀ t ∈ T, (f t).map emb = t := by intro t ht exact Finset.subtype_map_of_mem (hsub t ht) have hinj : Set.InjOn f T := by intro a ha b hb hab have heq := congrArg (fun t : Finset S => t.map emb) hab rw [hmap a ha, hmap b hb] at heq exact heq have hcard : U.card = T.card := Finset.card_image_iff.mpr hinj have hc : ∀ t ∈ U, (G.induce (S : Set V)).IsNClique 3 t := by intro t ht obtain ⟨s, hs, rfl⟩ := Finset.mem_image.mp ht apply (G.isNClique_induce_iff (S : Set V) (f s) 3).mpr change G.IsNClique 3 ((f s).map emb) rw [hmap s hs] exact hT s hs have hp : (U : Set (Finset S)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by intro s hs t ht hne obtain ⟨s', hs', rfl⟩ := Finset.mem_image.mp hs obtain ⟨t', ht', rfl⟩ := Finset.mem_image.mp ht have hne' : s' ≠ t' := by intro h; exact hne (congrArg f h) have h := hTp hs' ht' hne' have hi : ((f s' ∩ f t').map emb).card = (s' ∩ t').card := by rw [Finset.map_inter, hmap s' hs', hmap t' ht'] simpa using hi.trans_le h have hl : T.card ≤ simple_graph_triangle_packing_number (G.induce (S : Set V)) := by unfold simple_graph_triangle_packing_number apply le_csSup · refine ⟨Fintype.card (Finset S), ?_⟩ rintro n ⟨P, _, _, rfl⟩ exact Finset.card_le_univ P · exact ⟨U, hc, hp, hcard⟩ apply le_antisymm (simple_graph_triangle_packing_number_induce_le G S) simpa [hTc] using hl