AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_packing_number_induce_eq_of_packing_subset

theoremverified

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

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

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

    lines 9–15

    uses Finset.subtype_map_of_mem

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

    lines 16–21

    uses congrArg, Finset.card_image_iff.mpr

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

    lines 22–28

    uses Finset.mem_image.mp, G.isNClique_induce_iff

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

    lines 29–37

    uses Finset.mem_image.mp, congrArg, Finset.map_inter

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

    lines 38–44

    uses le_csSup, Finset.card_le_univ

      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⟩
  6. 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.

    lines 45–46

    uses le_antisymm, simple_graph_triangle_packing_number_induce_le

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

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