AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_packing_number_induce_le

theoremverified

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
Used by 1

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.

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

    lines 5–9

    uses Function.Embedding.subtype, Finset.map_injective, csSup_le_csSup

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

    lines 10–12

    uses Finset.card_le_univ

      · refine ⟨Fintype.card (Finset V), ?_⟩
        rintro n ⟨T, _, _, rfl⟩
        exact Finset.card_le_univ T
  3. 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.

    line 13

      · exact ⟨0, ∅, by simp, by simp, rfl⟩
  4. 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.

    lines 14–15

    uses Finset.card_map

      · rintro n ⟨T, hT, hpw, rfl⟩
        refine ⟨T.map e, ?_, ?_, Finset.card_map _⟩
  5. 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.

    lines 16–18

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

    lines 19–26

    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.

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