simple_graph_triangle_cover_number_mono
Triangle cover number is monotone under subgraph inclusion: if H ≤ G, then τ(H) ≤ τ(G).
Statement
theorem simple_graph_triangle_cover_number_mono {V : Type*} [Fintype V] (G H : SimpleGraph V) (hle : H ≤ G) : simple_graph_triangle_cover_number H ≤ simple_graph_triangle_cover_number G
- Source
- step towards simple_graph_triangle_cover_number_le_two_mul_packing_number
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_triangle_cover_numberτ(G): the minimum number of edges of G such that every triangle of G contains one of them.
- simple_graph_triangle_cover_number_eq_zero_of_clique_freeA triangle-free graph has triangle cover number 0.
The proof, explained
The triangle cover number τ(G) is the minimum size of an edge set that intersects every triangle (3-clique) in G. To prove that τ(H) ≤ τ(G) whenever H ≤ G, the argument selects a minimum triangle cover F of G and restricts it to H by setting F' = F ∩ E(H). Because every triangle in H is also a triangle in G, its covering edge in F has both endpoints in H, forcing that edge to belong to H; hence F' covers all triangles in H, giving τ(H) ≤ |F'| ≤ |F| = τ(G).
The set of sizes of triangle covers of G is nonempty.
Working classically, the proof shows that the set of triangle cover sizes is nonempty by demonstrating that the full edge set of G (filtered from the set of all pairs) is a triangle cover. Every edge in this set is an edge of G by definition. Furthermore, any 3-clique t in G contains three distinct vertices x, y, z; since they form a clique, x and y are adjacent in G, so the edge s(x, y) is an edge of G with both endpoints in t.
uses
Finset.card_eq_three.1,Finset.mem_filter,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 rw [Finset.mem_filter] at he exact 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), ?_, ?_⟩ · rw [Finset.mem_filter] exact ⟨Finset.mem_univ _, hadj⟩ · intro v hv simp only [Sym2.mem_iff] at hv rcases hv with rfl | rfl <;> simp
There exists a minimum triangle cover F of G, and its restriction F' to edges of H consists entirely of edges of H.
Since the set of triangle cover sizes of G is nonempty, its infimum is attained by some finset F, meaning |F| = τ(G) and F covers all triangles of G. We define F' by restricting F to the edges of H (filtering by `· ∈ H.edgeSet`). By definition of the filter, every edge in F' is an edge of H.
uses
Nat.sInf_mem,Finset.mem_filterobtain ⟨F, hFedge, hFcover, hFcard⟩ := Nat.sInf_mem hne change F.card = simple_graph_triangle_cover_number G at hFcard set F' : Finset (Sym2 V) := F.filter (· ∈ H.edgeSet) have hF'edge : ∀ e ∈ F', e ∈ H.edgeSet := by intro e he rw [Finset.mem_filter] at he exact he.2
F' covers every triangle in H.
Given any triangle t in H, since H ≤ G, t is also a triangle in G. Thus F contains an edge e with both endpoints in t. Decomposing e into an unordered pair s(u, v), the fact that e is an edge of G implies u ≠ v. Since both u and v belong to the clique t in H, they are adjacent in H. Therefore, e is an edge of H and belongs to F', showing that F' covers t.
uses
Sym2.ind,Finset.mem_filterhave hF'cover : ∀ t : Finset V, H.IsNClique 3 t → ∃ e ∈ F', ∀ x ∈ e, x ∈ t := by intro t ht obtain ⟨e, heF, het⟩ := hFcover t (ht.mono hle) induction' e using Sym2.ind with u v have heG : G.Adj u v := hFedge s(u, v) heF have hne : u ≠ v := G.ne_of_adj heG have hu : u ∈ t := het u (by simp) have hv : v ∈ t := het v (by simp) have hadj : H.Adj u v := ht.isClique hu hv hne refine ⟨s(u, v), ?_, het⟩ rw [Finset.mem_filter] exact ⟨heF, hadj⟩
The triangle cover number of H is at most that of G: τ(H) ≤ τ(G).
Because F' is a valid triangle cover of H, its size |F'| belongs to the set of cover sizes of H, which implies τ(H) ≤ |F'| by definition of the infimum. Moreover, as F' was obtained by filtering F, we have |F'| ≤ |F|. Since |F| = τ(G), transitivity yields τ(H) ≤ τ(G).
uses
Nat.sInf_le,Finset.card_filter_lehave hHle : simple_graph_triangle_cover_number H ≤ F'.card := by apply Nat.sInf_le exact ⟨F', hF'edge, hF'cover, rfl⟩ rw [← hFcard] exact hHle.trans (Finset.card_filter_le _ _)
Finset.card_eq_three.1- A finite set has cardinality 3 if and only if (in the forward direction) it consists of three distinct elements.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set `Finset.univ`.
Sym2.mem_iff- An element belongs to the unordered pair s(a, b) if and only if it is equal to a or equal to b.
Nat.sInf_mem- The infimum of a nonempty set of natural numbers is an element of that set.
Sym2.ind- Every unordered pair in Sym2 α is of the form s(x, y) for some x, y in α.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element in the set.
Finset.card_filter_le- Filtering a finite set yields a subset whose cardinality is at most the original cardinality.
- In Lean, `simple_graph_triangle_cover_number` is defined via `sInf` over natural numbers. Unlike an informal paper proof which can simply pick a minimum triangle cover, the formal proof must first show that the set of triangle covers is nonempty (lines 6–20) before extracting a minimizer via `Nat.sInf_mem`.
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.
/-- Triangle cover number is monotone under subgraph inclusion: if H ≤ G, then τ(H) ≤ τ(G). -/theorem simple_graph_triangle_cover_number_mono {V : Type*} [Fintype V] (G H : SimpleGraph V) (hle : H ≤ G) : simple_graph_triangle_cover_number H ≤ 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 rw [Finset.mem_filter] at he exact 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), ?_, ?_⟩ · rw [Finset.mem_filter] exact ⟨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 set F' : Finset (Sym2 V) := F.filter (· ∈ H.edgeSet) have hF'edge : ∀ e ∈ F', e ∈ H.edgeSet := by intro e he rw [Finset.mem_filter] at he exact he.2 have hF'cover : ∀ t : Finset V, H.IsNClique 3 t → ∃ e ∈ F', ∀ x ∈ e, x ∈ t := by intro t ht obtain ⟨e, heF, het⟩ := hFcover t (ht.mono hle) induction' e using Sym2.ind with u v have heG : G.Adj u v := hFedge s(u, v) heF have hne : u ≠ v := G.ne_of_adj heG have hu : u ∈ t := het u (by simp) have hv : v ∈ t := het v (by simp) have hadj : H.Adj u v := ht.isClique hu hv hne refine ⟨s(u, v), ?_, het⟩ rw [Finset.mem_filter] exact ⟨heF, hadj⟩ have hHle : simple_graph_triangle_cover_number H ≤ F'.card := by apply Nat.sInf_le exact ⟨F', hF'edge, hF'cover, rfl⟩ rw [← hFcard] exact hHle.trans (Finset.card_filter_le _ _)