simple_graph_triangle_cover_number_delete_edge_le
Deleting an edge e from G decreases the triangle cover number by at most 1: τ(G) ≤ τ(G \ {e}) + 1.
Statement
theorem simple_graph_triangle_cover_number_delete_edge_le {V : Type*} [Fintype V] (G : SimpleGraph V) (e : Sym2 V) (he : e ∈ G.edgeSet) : simple_graph_triangle_cover_number G ≤ simple_graph_triangle_cover_number (G.deleteEdges {e}) + 1
- 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.
- Used by 1
- simple_graph_triangle_cover_number_le_two_mul_packing_number_of_decreasing_edgeInduction step for the easy branch: if every graph on the same vertex type with strictly smaller triangle packing number satisfies τ ≤ 2ν,…
The proof, explained
Let H = G \ {e} be the graph obtained by deleting the edge e, and let F be a minimum triangle cover of H, so that |F| = τ(H). Adjoining the deleted edge e to F produces a set of edges F ∪ {e} of G with size at most |F| + 1. Every triangle in G either contains e (and is therefore covered by e) or does not contain e (in which case it remains a triangle in H and is covered by some edge in F). Thus F ∪ {e} is a valid triangle cover for G, which implies τ(G) ≤ |F ∪ {e}| ≤ τ(H) + 1 = τ(G \ {e}) + 1.
Let H = G \ {e} be the subgraph of G obtained by deleting the edge e.
We enable classical logic and define the abbreviation H for the graph G.deleteEdges {e} with the edge e removed.
classical -- τ(G) is the least cardinality of a triangle cover; take a minimum cover F of G \ {e}. set H : SimpleGraph V := G.deleteEdges {e} with hHdef
There exists a minimum triangle cover F of H, whose cardinality is τ(H).
The family of triangle covers of H is nonempty because the full edge set E(H) covers every triangle of H: for any 3-clique {u, v, w} in H, the edge {u, v} belongs to E(H) and is contained in {u, v, w}. Because this set of cover sizes is a nonempty set of natural numbers, by `Nat.sInf_mem` it contains its infimum τ(H). Let F be a minimum triangle cover witnessing this infimum, so F ⊆ E(H), F covers all 3-cliques of H, and |F| = τ(H).
uses
SimpleGraph.mem_edgeFinset,Finset.card_eq_three.mp,SimpleGraph.mem_edgeSet,Sym2.mem_iff,Nat.sInf_mem-- The family of cardinalities of triangle covers of H is nonempty: the full edge set works. have hSne : {n : ℕ | ∃ F : Finset (Sym2 V), (∀ f ∈ F, f ∈ H.edgeSet) ∧ (∀ t : Finset V, H.IsNClique 3 t → ∃ f ∈ F, ∀ x ∈ f, x ∈ t) ∧ F.card = n}.Nonempty := by refine ⟨_, H.edgeFinset, ?_, ?_, rfl⟩ · intro f hf; rwa [SimpleGraph.mem_edgeFinset] at hf · intro t ht obtain ⟨u, v, w, huv, -, -, rfl⟩ := Finset.card_eq_three.mp ht.card_eq refine ⟨s(u, v), ?_, ?_⟩ · rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] exact ht.isClique (by simp) (by simp) huv · intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> simp obtain ⟨F, hFsub, hFcov, hFcard⟩ := Nat.sInf_mem hSne
Every edge in F is an edge of G.
Since F is a triangle cover of H = G \ {e}, its edges satisfy F ⊆ E(H) = E(G) \ {e}, so every edge in F is in particular an edge of G.
uses
SimpleGraph.edgeSet_deleteEdgeshave hFsubG : ∀ f ∈ F, f ∈ G.edgeSet := by intro f hf have := hFsub f hf rw [hHdef, SimpleGraph.edgeSet_deleteEdges] at this exact this.1
The set F ∪ {e} covers every triangle in G.
Let t be a triangle (3-clique) in G. We split into two cases based on whether the deleted edge e is contained in t: 1. If both endpoints of e lie in t, then e covers t, and e ∈ F ∪ {e}. 2. If e is not contained in t, then no pair of vertices in t forms the edge e. Thus all edges of the clique t remain in H = G \ {e}, meaning t is a 3-clique in H. Since F covers all triangles of H, some edge f ∈ F has both endpoints in t, and f also belongs to F ∪ {e}.
uses
Finset.mem_insert_self,SimpleGraph.isClique_iff,SimpleGraph.deleteEdges_adj,Sym2.mem_iff,Finset.mem_insert_of_mem-- Adjoining e to F covers every triangle of G. have hcoverG : ∀ t : Finset V, G.IsNClique 3 t → ∃ f ∈ insert e F, ∀ x ∈ f, x ∈ t := by intro t ht by_cases hcase : ∀ x ∈ e, x ∈ t · exact ⟨e, Finset.mem_insert_self e F, hcase⟩ · -- A triangle of G not containing e is a triangle of G \ {e}. have hclq : H.IsClique (↑t : Set V) := by have hG := ht.isClique rw [SimpleGraph.isClique_iff] at hG ⊢ intro a ha b hb hab rw [SimpleGraph.deleteEdges_adj] refine ⟨hG ha hb hab, ?_⟩ intro hmem exact hcase fun x hx => by rw [← hmem] at hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> assumption obtain ⟨f, hfF, hft⟩ := hFcov t ⟨hclq, ht.card_eq⟩ exact ⟨f, Finset.mem_insert_of_mem hfF, hft⟩
Every edge in F ∪ {e} is an edge of G.
Any edge in F ∪ {e} is either e (which belongs to E(G) by hypothesis) or belongs to F (which is a subset of E(G) by Step 3).
uses
Finset.mem_inserthave hsubG' : ∀ f ∈ insert e F, f ∈ G.edgeSet := by intro f hf rw [Finset.mem_insert] at hf rcases hf with rfl | hf · exact he · exact hFsubG f hf
τ(G) ≤ |F ∪ {e}|.
Because F ∪ {e} consists of edges of G and covers every triangle of G, its cardinality belongs to the set of triangle cover sizes of G. By definition of τ(G) as the infimum of this set, τ(G) ≤ |F ∪ {e}|.
uses
Nat.sInf_lehave hmemG : (insert e F).card ∈ {n : ℕ | ∃ F : Finset (Sym2 V), (∀ f ∈ F, f ∈ G.edgeSet) ∧ (∀ t : Finset V, G.IsNClique 3 t → ∃ f ∈ F, ∀ x ∈ f, x ∈ t) ∧ F.card = n} := ⟨insert e F, hsubG', hcoverG, rfl⟩ have h1 : simple_graph_triangle_cover_number G ≤ (insert e F).card := Nat.sInf_le hmemG
|F ∪ {e}| ≤ τ(H) + 1.
The cover F was chosen with |F| = τ(H). Inserting a single element e into F increases its cardinality by at most 1, giving |F ∪ {e}| ≤ |F| + 1 = τ(H) + 1.
uses
Finset.card_insert_lehave h3 : F.card = simple_graph_triangle_cover_number H := hFcard have h2 : (insert e F).card ≤ simple_graph_triangle_cover_number H + 1 := by rw [← h3] exact Finset.card_insert_le e F
Combining the bounds yields τ(G) ≤ τ(G \ {e}) + 1.
Rewriting H as G \ {e}, transitivity of the inequalities τ(G) ≤ |F ∪ {e}| and |F ∪ {e}| ≤ τ(G \ {e}) + 1 finishes the proof via linear arithmetic.
rw [hHdef] at h2 ⊢ omega
Finset.card_eq_three.mp- A finite set has cardinality 3 if and only if it consists of three distinct elements.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1: |{a} ∪ s| ≤ |s| + 1.
Finset.mem_insert- An element belongs to {b} ∪ s if and only if it equals b or belongs to s.
Finset.mem_insert_of_mem- If an element belongs to s, then it also belongs to {b} ∪ s.
Finset.mem_insert_self- An element a belongs to {a} ∪ s.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element of that set.
Nat.sInf_mem- Any nonempty set of natural numbers contains its infimum (minimum).
SimpleGraph.deleteEdges_adj- Vertices u and v are adjacent in G \ s if and only if they are adjacent in G and the edge between them is not in s.
SimpleGraph.edgeSet_deleteEdges- The edge set of G after deleting a set of edges s is the set difference E(G) \ s.
SimpleGraph.isClique_iff- A set of vertices is a clique in G if and only if every pair of distinct vertices in the set is adjacent in G.
SimpleGraph.mem_edgeFinset- An edge belongs to the finite edge set of a graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet- The unordered pair s(v, w) belongs to the edge set of G if and only if v and w are adjacent in G.
Sym2.mem_iff- A vertex x belongs to the unordered pair s(u, v) if and only if x = u or x = v.
- In Lean, `sInf` on `ℕ` is defined to return 0 on the empty set, so to extract a minimum triangle cover attaining `τ(H)` via `Nat.sInf_mem`, the formal proof must first explicitly prove that the family of triangle covers of `H = G \ {e}` is nonempty (lines 8–20), which a paper proof would take for granted.
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.
/-- Deleting an edge e from G decreases the triangle cover number by at most 1: τ(G) ≤ τ(G \ {e}) + 1. -/theorem simple_graph_triangle_cover_number_delete_edge_le {V : Type*} [Fintype V] (G : SimpleGraph V) (e : Sym2 V) (he : e ∈ G.edgeSet) : simple_graph_triangle_cover_number G ≤ simple_graph_triangle_cover_number (G.deleteEdges {e}) + 1 := by classical -- τ(G) is the least cardinality of a triangle cover; take a minimum cover F of G \ {e}. set H : SimpleGraph V := G.deleteEdges {e} with hHdef -- The family of cardinalities of triangle covers of H is nonempty: the full edge set works. have hSne : {n : ℕ | ∃ F : Finset (Sym2 V), (∀ f ∈ F, f ∈ H.edgeSet) ∧ (∀ t : Finset V, H.IsNClique 3 t → ∃ f ∈ F, ∀ x ∈ f, x ∈ t) ∧ F.card = n}.Nonempty := by refine ⟨_, H.edgeFinset, ?_, ?_, rfl⟩ · intro f hf; rwa [SimpleGraph.mem_edgeFinset] at hf · intro t ht obtain ⟨u, v, w, huv, -, -, rfl⟩ := Finset.card_eq_three.mp ht.card_eq refine ⟨s(u, v), ?_, ?_⟩ · rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] exact ht.isClique (by simp) (by simp) huv · intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> simp obtain ⟨F, hFsub, hFcov, hFcard⟩ := Nat.sInf_mem hSne have hFsubG : ∀ f ∈ F, f ∈ G.edgeSet := by intro f hf have := hFsub f hf rw [hHdef, SimpleGraph.edgeSet_deleteEdges] at this exact this.1 -- Adjoining e to F covers every triangle of G. have hcoverG : ∀ t : Finset V, G.IsNClique 3 t → ∃ f ∈ insert e F, ∀ x ∈ f, x ∈ t := by intro t ht by_cases hcase : ∀ x ∈ e, x ∈ t · exact ⟨e, Finset.mem_insert_self e F, hcase⟩ · -- A triangle of G not containing e is a triangle of G \ {e}. have hclq : H.IsClique (↑t : Set V) := by have hG := ht.isClique rw [SimpleGraph.isClique_iff] at hG ⊢ intro a ha b hb hab rw [SimpleGraph.deleteEdges_adj] refine ⟨hG ha hb hab, ?_⟩ intro hmem exact hcase fun x hx => by rw [← hmem] at hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> assumption obtain ⟨f, hfF, hft⟩ := hFcov t ⟨hclq, ht.card_eq⟩ exact ⟨f, Finset.mem_insert_of_mem hfF, hft⟩ have hsubG' : ∀ f ∈ insert e F, f ∈ G.edgeSet := by intro f hf rw [Finset.mem_insert] at hf rcases hf with rfl | hf · exact he · exact hFsubG f hf have hmemG : (insert e F).card ∈ {n : ℕ | ∃ F : Finset (Sym2 V), (∀ f ∈ F, f ∈ G.edgeSet) ∧ (∀ t : Finset V, G.IsNClique 3 t → ∃ f ∈ F, ∀ x ∈ f, x ∈ t) ∧ F.card = n} := ⟨insert e F, hsubG', hcoverG, rfl⟩ have h1 : simple_graph_triangle_cover_number G ≤ (insert e F).card := Nat.sInf_le hmemG have h3 : F.card = simple_graph_triangle_cover_number H := hFcard have h2 : (insert e F).card ≤ simple_graph_triangle_cover_number H + 1 := by rw [← h3] exact Finset.card_insert_le e F rw [hHdef] at h2 ⊢ omega