simple_graph_triangle_cover_number_induce_le
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
- simple_graph_triangle_cover_numberτ(G): the minimum number of edges of G such that every triangle of G contains one of them.
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)$.
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$.
uses
Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_univ,Sym2.mem_iffclassical 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
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`.
uses
Nat.sInf_memobtain ⟨F, hFedge, hFcover, hFcard⟩ := Nat.sInf_mem hne change F.card = simple_graph_triangle_cover_number G at hFcard
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]$.
uses
Function.Embedding.subtype,Finset.mem_filter.mplet 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
$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$.
uses
Sym2.ind,Finset.mem_map.mp,Finset.mem_filter.mpr,Finset.mem_univ,Sym2.mem_iffhave 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
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|$.
uses
Finset.card_map,Finset.card_le_card,Finset.mem_map.mp,Finset.mem_filter.mphave 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
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.
uses
Nat.sInf_lehave 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.
- In Lean, the vertices of an induced subgraph are represented as a subtype `↥S`. As a result, the proof explicitly sets up the canonical embedding `emb : S ↪ V` and its induced map on unordered pairs `edgeEmb : Sym2 S ↪ Sym2 V` to relate the edges and triangles of the induced subgraph to those of the ambient graph.
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_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