AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_number_induce_le

theoremverified

The triangle cover number of an induced subgraph does not exceed that of the host graph.

Statement

theorem simple_graph_triangle_cover_number_induce_le
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (S : Finset V) :
    simple_graph_triangle_cover_number (G.induce (S : Set V)) ≤
      simple_graph_triangle_cover_number G
Source
step towards simple_graph_triangle_packing_cover_bounded_induced_kernel
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The triangle cover number $\tau(G)$ is the minimum cardinality of an edge set that intersects every triangle in $G$. We take a minimum triangle cover $F$ of $G$, so that $|F| = \tau(G)$. We pull $F$ back to the induced subgraph $G[S]$ to form a candidate edge set $F'$. Because every triangle in $G[S]$ maps to a triangle in $G$ and simple graphs contain no self-loops, $F'$ covers every triangle in $G[S]$. The canonical injection on pairs maps $F'$ into $F$, yielding $\tau(G[S]) \le |F'| \le |F| = \tau(G)$.

  1. The set of cardinalities of triangle-covering edge sets of $G$ is nonempty.

    We enable classical logic. To show nonemptiness, we witness that the entire edge set of $G$ covers every triangle: any 3-clique $t = \{x, y, z\}$ in $G$ has an edge $s(x, y)$ between two of its vertices, and both endpoints belong to $t$.

    lines 5–18

    uses Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_univ, Sym2.mem_iff

      classical
      have hne : {n | ∃ F : Finset (Sym2 V), (∀ e ∈ F, e ∈ G.edgeSet) ∧
          (∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t) ∧ F.card = n}.Nonempty := by
        refine ⟨_, Finset.univ.filter (· ∈ G.edgeSet), ?_, ?_, rfl⟩
        · intro e he
          exact (Finset.mem_filter.mp he).2
        · intro t ht
          obtain ⟨x, y, z, hxy, -, -, rfl⟩ := Finset.card_eq_three.1 ht.card_eq
          have hadj : G.Adj x y := ht.isClique (by simp) (by simp) hxy
          refine ⟨s(x, y), ?_, ?_⟩
          · exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hadj⟩
          · intro v hv
            simp only [Sym2.mem_iff] at hv
            rcases hv with rfl | rfl <;> simp
  2. There exists a minimum-cardinality triangle cover $F$ of $G$ whose size equals the triangle cover number of $G$.

    Because the set of sizes of triangle covers of $G$ is a nonempty set of natural numbers, its infimum is attained by some element via `Nat.sInf_mem`. We choose $F$ to be this minimizing edge set; its cardinality is, by definition, `simple_graph_triangle_cover_number G`.

    lines 19–20

    uses Nat.sInf_mem

      obtain ⟨F, hFedge, hFcover, hFcard⟩ := Nat.sInf_mem hne
      change F.card = simple_graph_triangle_cover_number G at hFcard
  3. We define a candidate cover $F'$ on $S$ and verify that all its elements are edges of $G[S]$.

    Using the subtype embedding $\text{emb} : S \hookrightarrow V$ and the induced embedding on unordered pairs $\text{edgeEmb} : \operatorname{Sym}^2(S) \hookrightarrow \operatorname{Sym}^2(V)$, let $F'$ be the finset of pairs in $S$ that are edges of the induced subgraph $G[S]$ and whose image under $\text{edgeEmb}$ belongs to $F$. By definition (extracting the edge condition from the filter via `Finset.mem_filter.mp`), every element of $F'$ is an edge of $G[S]$.

    lines 21–27

    uses Function.Embedding.subtype, Finset.mem_filter.mp

      let emb : S ↪ V := Function.Embedding.subtype (fun x => x ∈ S)
      let edgeEmb : Sym2 S ↪ Sym2 V := emb.sym2Map
      let F' : Finset (Sym2 S) := Finset.univ.filter fun e =>
        e ∈ (G.induce (S : Set V)).edgeSet ∧ edgeEmb e ∈ F
      have hF'edge : ∀ e ∈ F', e ∈ (G.induce (S : Set V)).edgeSet := by
        intro e he
        exact (Finset.mem_filter.mp he).2.1
  4. $F'$ covers every triangle in the induced subgraph $G[S]$.

    Given a 3-clique $t$ in $G[S]$, its image under $\text{emb}$ is a 3-clique in $G$. Since $F$ covers all triangles in $G$, there is an edge $e \in F$ whose endpoints both lie in the mapped clique. Writing $e = s(u, v)$ via `Sym2.ind`, the vertices $u$ and $v$ are images under $\text{emb}$ of vertices $a, b \in t$. These vertices must be distinct, because otherwise $e = s(\text{emb}(a), \text{emb}(a)) \in F$ would be a self-loop in $G$, contradicting simplicity. Because $t$ is a clique, $a$ and $b$ are adjacent in $G[S]$, so $s(a, b)$ is an edge of $G[S]$ that maps to $e \in F$. Thus $s(a, b) \in F'$, and its endpoints both belong to $t$.

    lines 28–52

    uses Sym2.ind, Finset.mem_map.mp, Finset.mem_filter.mpr, Finset.mem_univ, Sym2.mem_iff

      have hF'cover : ∀ t : Finset S, (G.induce (S : Set V)).IsNClique 3 t →
          ∃ e ∈ F', ∀ x ∈ e, x ∈ t := by
        intro t ht
        have htG : G.IsNClique 3 (t.map emb) := by
          exact (G.isNClique_induce_iff (S : Set V) t 3).mp ht
        obtain ⟨e, heF, het⟩ := hFcover (t.map emb) htG
        induction e using Sym2.ind with
        | _ u v =>
          have hu : u ∈ t.map emb := het u (by simp)
          have hv : v ∈ t.map emb := het v (by simp)
          obtain ⟨a, ha, rfl⟩ := Finset.mem_map.mp hu
          obtain ⟨b, hb, rfl⟩ := Finset.mem_map.mp hv
          have hab : a ≠ b := by
            intro h
            subst b
            have : G.Adj (emb a) (emb a) := hFedge _ heF
            exact (G.ne_of_adj this) rfl
          have hadj : (G.induce (S : Set V)).Adj a b := ht.isClique ha hb hab
          refine ⟨s(a,b), ?_, ?_⟩
          · apply Finset.mem_filter.mpr
            refine ⟨Finset.mem_univ _, hadj, ?_⟩
            simpa [edgeEmb, emb] using heF
          · intro x hx
            simp only [Sym2.mem_iff] at hx
            rcases hx with rfl | rfl <;> assumption
  5. The cardinality of $F'$ is at most that of $F$ ($|F'| \le |F|$).

    Because $\text{edgeEmb}$ is an embedding, mapping $F'$ by $\text{edgeEmb}$ preserves cardinality via `Finset.card_map`. Furthermore, every element in the image belongs to $F$ by construction of $F'$, so the image is a subset of $F$. By `Finset.card_le_card`, $|F'| \le |F|$.

    lines 53–60

    uses Finset.card_map, Finset.card_le_card, Finset.mem_map.mp, Finset.mem_filter.mp

      have hcard : F'.card ≤ F.card := by
        calc
          F'.card = (F'.map edgeEmb).card := (Finset.card_map _).symm
          _ ≤ F.card := by
            apply Finset.card_le_card
            intro e he
            obtain ⟨x,hx,rfl⟩ := Finset.mem_map.mp he
            exact (Finset.mem_filter.mp hx).2.2
  6. The triangle cover number of $G[S]$ is bounded by $|F'|$, which chains with $|F'| \le |F| = \tau(G)$ to conclude.

    Because $F'$ is an edge set in $G[S]$ that covers all triangles of $G[S]$, its size $|F'|$ belongs to the set of valid triangle cover sizes. Thus the infimum defining the triangle cover number satisfies $\tau(G[S]) \le |F'|$ by `Nat.sInf_le`. Chaining this with $|F'| \le |F|$ and $|F| = \tau(G)$ completes the proof.

    lines 61–65

    uses Nat.sInf_le

      have hle : simple_graph_triangle_cover_number (G.induce (S : Set V)) ≤ F'.card := by
        apply Nat.sInf_le
        exact ⟨F', hF'edge, hF'cover, rfl⟩
      rw [← hFcard]
      exact hle.trans hcard
Finset.mem_filter.mp
An element in a filtered set belongs to the original set and satisfies the filter condition.
Finset.mem_filter.mpr
An element belonging to a set and satisfying a condition belongs to the filtered set.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Sym2.mem_iff
An element belongs to an unordered pair `s(b, c)` if and only if it equals `b` or `c`.
Nat.sInf_mem
Every nonempty set of natural numbers contains its infimum (minimum).
Function.Embedding.subtype
The canonical inclusion map from a subtype into the ambient type is an embedding (an injective function).
Sym2.ind
To prove a statement for all unordered pairs, it suffices to prove it for pairs of the form `s(x, y)`.
Finset.mem_map.mp
An element in the image of a set under an embedding is the image of some element in the original set.
Finset.card_map
Applying an embedding to a finite set preserves its cardinality.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the other set's cardinality.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element in the set.

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_cover_number_induce_le    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (S : Finset V) :    simple_graph_triangle_cover_number (G.induce (S : Set V)) ≤      simple_graph_triangle_cover_number G := by  classical  have hne : {n | ∃ F : Finset (Sym2 V), (∀ e ∈ F, e ∈ G.edgeSet) ∧      (∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t) ∧ F.card = n}.Nonempty := by    refine ⟨_, Finset.univ.filter (· ∈ G.edgeSet), ?_, ?_, rfl⟩    · intro e he      exact (Finset.mem_filter.mp he).2    · intro t ht      obtain ⟨x, y, z, hxy, -, -, rfl⟩ := Finset.card_eq_three.1 ht.card_eq      have hadj : G.Adj x y := ht.isClique (by simp) (by simp) hxy      refine ⟨s(x, y), ?_, ?_⟩      · exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hadj⟩      · intro v hv        simp only [Sym2.mem_iff] at hv        rcases hv with rfl | rfl <;> simp  obtain ⟨F, hFedge, hFcover, hFcard⟩ := Nat.sInf_mem hne  change F.card = simple_graph_triangle_cover_number G at hFcard  let emb : S ↪ V := Function.Embedding.subtype (fun x => x ∈ S)  let edgeEmb : Sym2 S ↪ Sym2 V := emb.sym2Map  let F' : Finset (Sym2 S) := Finset.univ.filter fun e =>    e ∈ (G.induce (S : Set V)).edgeSet ∧ edgeEmb e ∈ F  have hF'edge : ∀ e ∈ F', e ∈ (G.induce (S : Set V)).edgeSet := by    intro e he    exact (Finset.mem_filter.mp he).2.1  have hF'cover : ∀ t : Finset S, (G.induce (S : Set V)).IsNClique 3 t →      ∃ e ∈ F', ∀ x ∈ e, x ∈ t := by    intro t ht    have htG : G.IsNClique 3 (t.map emb) := by      exact (G.isNClique_induce_iff (S : Set V) t 3).mp ht    obtain ⟨e, heF, het⟩ := hFcover (t.map emb) htG    induction e using Sym2.ind with    | _ u v =>      have hu : u ∈ t.map emb := het u (by simp)      have hv : v ∈ t.map emb := het v (by simp)      obtain ⟨a, ha, rfl⟩ := Finset.mem_map.mp hu      obtain ⟨b, hb, rfl⟩ := Finset.mem_map.mp hv      have hab : a ≠ b := by        intro h        subst b        have : G.Adj (emb a) (emb a) := hFedge _ heF        exact (G.ne_of_adj this) rfl      have hadj : (G.induce (S : Set V)).Adj a b := ht.isClique ha hb hab      refine ⟨s(a,b), ?_, ?_⟩      · apply Finset.mem_filter.mpr        refine ⟨Finset.mem_univ _, hadj, ?_⟩        simpa [edgeEmb, emb] using heF      · intro x hx        simp only [Sym2.mem_iff] at hx        rcases hx with rfl | rfl <;> assumption  have hcard : F'.card ≤ F.card := by    calc      F'.card = (F'.map edgeEmb).card := (Finset.card_map _).symm      _ ≤ F.card := by        apply Finset.card_le_card        intro e he        obtain ⟨x,hx,rfl⟩ := Finset.mem_map.mp he        exact (Finset.mem_filter.mp hx).2.2  have hle : simple_graph_triangle_cover_number (G.induce (S : Set V)) ≤ F'.card := by    apply Nat.sInf_le    exact ⟨F', hF'edge, hF'cover, rfl⟩  rw [← hFcard]  exact hle.trans hcard
See it in the graphDiscuss this resultChallenge it