simple_graph_triangle_cover_number_le_of_edge_reduction
Let G be a finite simple graph, F a nonempty edge subset, S a pairwise edge-disjoint triangle family, and X an edge subset such that X meets every triangle containing an edge of F and E(S) \ F ⊆ X. Then the triangle cover number of G is at most that of G \ (F ∪ X) plus |X|.
Statement
open Classical in theorem simple_graph_triangle_cover_number_le_of_edge_reduction {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (F : Finset (Sym2 V)) (hF : F ⊆ G.edgeFinset) (hFne : F.Nonempty) (S : Finset (Finset V)) (hS : ∀ t ∈ S, G.IsNClique 3 t) (hSpairwise : (S : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) (X : Finset (Sym2 V)) (hX : X ⊆ G.edgeFinset) (hXmeets : ∀ t : Finset V, G.IsNClique 3 t → (∃ e ∈ F, ∀ x ∈ e, x ∈ t) → ∃ e ∈ X, ∀ x ∈ e, x ∈ t) (hES : (S.biUnion finite_vertex_set_edge_encoding \ F) ⊆ X) : simple_graph_triangle_cover_number G ≤ simple_graph_triangle_cover_number (G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))) + X.card
- Source
- arXiv:2611.11128 Lemma 2.2 -- Triangle-overlap cores and density bounds for Tuza's conjecture
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_triangle_cover_numberτ(G): the minimum number of edges of G such that every triangle of G contains one of them.
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod.
- Used by 1
- simple_graph_edge_reduction_inequalityLet G be a finite simple graph. Suppose there exist a nonempty edge set F ⊆ E(G), a set S of pairwise edge-disjoint triangles of G, and an…
Read back from the Lean
Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$. Let $F$ be a nonempty finite set of edges of $G$. Let $S$ be a finite set of 3-cliques of $G$ such that any two distinct cliques in $S$ share at most 1 vertex (i.e., $|s \cap t| \le 1$). Let $X$ be a finite set of edges of $G$ satisfying: 1. For every 3-clique $t$ of $G$, if $t$ contains an edge of $F$ (an edge whose endpoints both belong to $t$), then $t$ also contains an edge of $X$. 2. All edges spanned by cliques in $S$ that are not in $F$ belong to $X$ (i.e., $(\bigcup_{s \in S} E(s)) \setminus F \subseteq X$, where $E(s)$ is the set of unordered pairs of distinct vertices in $s$). Then the triangle cover number of $G$ is at most the triangle cover number of the graph obtained by deleting all edges in $F \cup X$ from $G$, plus $|X|$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To bound the triangle cover number $\tau_3(G)$, we delete the edges $F \cup X$ to form $H = G \setminus (F \cup X)$. Since the full edge set of $H$ is a trivial triangle cover, the set of cover sizes is nonempty, so $H$ admits a minimum triangle cover $C$ with $|C| = \tau_3(H)$. We then show that $C \cup X$ is a valid triangle cover of $G$: any triangle in $G$ either remains a clique in $H$ (hence covered by $C$) or contains an edge deleted into $F \cup X$, which by assumption or directly yields a covering edge in $X$. Since $C \cup X \subseteq E(G)$ covers all triangles of $G$, subadditivity gives $\tau_3(G) \le |C \cup X| \le |C| + |X| = \tau_3(H) + |X|$.
For any finite simple graph $H$, the set of cardinalities of triangle covers is nonempty.
We show that the full edge set $E(H)$ (`H.edgeFinset`) forms a valid triangle cover of $H$. First, every edge in `H.edgeFinset` belongs to $E(H)$ (SimpleGraph.mem_edgeFinset). Second, any triangle $t$ in $H$ has cardinality 3 (Finset.card_eq_three.mp), so $t = \{u, v, w\}$ with $u \ne v$. Since $t$ is a clique, the pair $\{u, v\}$ is an edge of $H$ (SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet), and both of its vertices lie in $t$ (Sym2.mem_iff). Thus $E(H)$ meets every triangle of $H$, showing the set of triangle cover sizes is nonempty.
uses
SimpleGraph.mem_edgeFinset,Finset.card_eq_three.mp,SimpleGraph.mem_edgeSet,Sym2.mem_iffclassical 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
Let $H = G \setminus (F \cup X)$; there exists a minimum triangle cover $C$ of $H$ with $|C| = \tau_3(H)$.
We define the reduced graph $H$ by deleting the edges in $F \cup X$ from $G$. By simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty, the collection of cardinalities of triangle covers of $H$ is nonempty, so by Nat.sInf_mem its infimum is attained by some cover $C \subseteq E(H)$ whose size equals the triangle cover number $\tau_3(H)$.
uses
simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty,Nat.sInf_memset H : SimpleGraph V := G.deleteEdges (↑(F ∪ X) : Set (Sym2 V)) obtain ⟨C, hCsub, hCcov, hCcard⟩ := Nat.sInf_mem (simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty H) change C.card = simple_graph_triangle_cover_number H at hCcard
Every edge in $C \cup X$ is an edge of $G$.
For any $e \in C \cup X$ (Finset.mem_union), if $e \in C$, then $e \in E(H) = E(G) \setminus (F \cup X)$ by SimpleGraph.edgeSet_deleteEdges, so $e \in E(G)$. If $e \in X$, then $e \in E(G)$ by hypothesis $X \subseteq E(G)$ (SimpleGraph.mem_edgeFinset).
uses
Finset.mem_union,SimpleGraph.edgeSet_deleteEdges,SimpleGraph.mem_edgeFinsethave hsubG : ∀ e ∈ C ∪ X, e ∈ G.edgeSet := by intro e he rw [Finset.mem_union] at he rcases he with heC | heX · have := hCsub e heC rw [SimpleGraph.edgeSet_deleteEdges] at this exact this.1 · have := hX heX rwa [SimpleGraph.mem_edgeFinset] at this
The edge set $C \cup X$ covers every triangle of $G$.
Let $t$ be a triangle in $G$. We case-split on whether $t$ remains a clique in $H$. If $t$ is a clique in $H$, it is a triangle in $H$, so $C$ contains an edge of $t$, which is in $C \cup X$ (Finset.mem_union_left). If $t$ is not a clique in $H$ (SimpleGraph.isClique_iff, Set.Pairwise), there exist distinct vertices $u, v \in t$ not adjacent in $H$. Because they are adjacent in $G$, the edge $\{u, v\}$ must have been deleted, so $\{u, v\} \in F \cup X$ (SimpleGraph.deleteEdges_adj, Finset.mem_coe, Finset.mem_union). Both vertices lie in $t$ (Sym2.mem_iff). If $\{u, v\} \in F$, then by hypothesis hXmeets, $X$ contains an edge of $t$, which belongs to $C \cup X$ (Finset.mem_union_right). If $\{u, v\} \in X$, then $\{u, v\}$ itself is an edge of $t$ in $C \cup X$ (Finset.mem_union_right). In all cases, $C \cup X$ meets $t$.
uses
Finset.mem_union_left,SimpleGraph.isClique_iff,Set.Pairwise,SimpleGraph.deleteEdges_adj,Finset.mem_coe,Finset.mem_union,Sym2.mem_iff,Finset.mem_union_righthave hcovG : ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ C ∪ X, ∀ x ∈ e, x ∈ t := by intro t ht by_cases hclq : H.IsClique (↑t : Set V) · obtain ⟨e, heC, het⟩ := hCcov t ⟨hclq, ht.card_eq⟩ exact ⟨e, Finset.mem_union_left X heC, het⟩ · rw [SimpleGraph.isClique_iff, Set.Pairwise] at hclq push Not at hclq obtain ⟨u, hu, v, hv, huv, hnotadj⟩ := hclq have hGadj : G.Adj u v := ht.isClique hu hv huv rw [SimpleGraph.deleteEdges_adj] at hnotadj have hdel : s(u, v) ∈ (↑(F ∪ X) : Set (Sym2 V)) := by by_contra h exact hnotadj ⟨hGadj, h⟩ rw [Finset.mem_coe, Finset.mem_union] at hdel have hxuv : ∀ x ∈ s(u, v), x ∈ t := by intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> assumption rcases hdel with hdelF | hdelX · obtain ⟨e, heX, het⟩ := hXmeets t ht ⟨s(u, v), hdelF, hxuv⟩ exact ⟨e, Finset.mem_union_right C heX, het⟩ · exact ⟨s(u, v), Finset.mem_union_right C hdelX, hxuv⟩
The triangle cover number of $G$ is at most $\tau_3(G \setminus (F \cup X)) + |X|$.
Because $C \cup X \subseteq E(G)$ meets every triangle in $G$, its size $|C \cup X|$ belongs to the set of triangle cover sizes of $G$. By definition of $\tau_3(G)$ as the infimum of this set, $\tau_3(G) \le |C \cup X|$ (Nat.sInf_le). By subadditivity of cardinality (Finset.card_union_le), $|C \cup X| \le |C| + |X| = \tau_3(H) + |X|$, which closes by linear arithmetic (omega). Transitivity of inequality yields the desired bound.
uses
Nat.sInf_le,Finset.card_union_lehave hmemG : (C ∪ X).card ∈ {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} := ⟨C ∪ X, hsubG, hcovG, rfl⟩ have hle : simple_graph_triangle_cover_number G ≤ (C ∪ X).card := Nat.sInf_le hmemG have hcardle : (C ∪ X).card ≤ simple_graph_triangle_cover_number H + X.card := by have := Finset.card_union_le C X omega exact hle.trans hcardle
SimpleGraph.mem_edgeFinset- An edge belongs to the finite edge set of a graph if and only if it belongs to its edge set.
Finset.card_eq_three.mp- A finite set has cardinality 3 if and only if it consists of three distinct elements.
SimpleGraph.mem_edgeSet- An unordered pair of vertices belongs to the edge set of a graph if and only if the vertices are adjacent in the graph.
Sym2.mem_iff- A vertex $x$ belongs to the unordered pair $\{u, v\}$ if and only if $x = u$ or $x = v$.
simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty- For any finite simple graph, the set of cardinalities of its triangle covers is nonempty.
Nat.sInf_mem- If a set of natural numbers is nonempty, its infimum (minimum) belongs to the set.
Finset.mem_union- An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
SimpleGraph.edgeSet_deleteEdges- The edge set of a graph after deleting a set of edges is the difference of the original edge set and the deleted set.
Finset.mem_union_left- An element of a finite set $s$ also belongs to the union $s \cup t$.
SimpleGraph.isClique_iff- A vertex set is a clique in a graph if and only if every pair of distinct vertices in it is adjacent.
Set.Pairwise- A binary relation holds for all pairs of distinct elements in a given set.
SimpleGraph.deleteEdges_adj- Two vertices are adjacent in a graph with deleted edges if and only if they were adjacent in the original graph and the edge between them was not deleted.
Finset.mem_coe- An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
Finset.mem_union_right- An element of a finite set $t$ also belongs to the union $s \cup t$.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element in the set.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities.
- The helper lemma `simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty` (lines 1–16) is proved first to show that the entire edge set $E(H)$ covers all triangles of $H$, ensuring that the set of triangle cover sizes is nonempty and its infimum $\tau_3(H)$ is attained.
- Several hypotheses in the theorem statement ($F \subseteq E(G)$, $F$ nonempty, the family $S$ of pairwise edge-disjoint triangles, and $E(S) \setminus F \subseteq X$) are not used in the proof; they belong to the wider edge-reduction framework, but the upper bound requires only $X \subseteq E(G)$ and the condition that $X$ meets every triangle containing an edge of $F$.
- The inequality $|C \cup X| \le \tau_3(H) + |X|$ is closed by `omega` on line 71 using `Finset.card_union_le` together with $|C| = \tau_3(H)$.
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.
lemma simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty {V : Type*} [Fintype V] (H : SimpleGraph V) : {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 classical 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 <;> simpopen Classical in/-- Under an edge reduction (F, S, X), the triangle cover number of G is at most that of G \ (F ∪ X) plus |X|. -/theorem simple_graph_triangle_cover_number_le_of_edge_reduction {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (F : Finset (Sym2 V)) (hF : F ⊆ G.edgeFinset) (hFne : F.Nonempty) (S : Finset (Finset V)) (hS : ∀ t ∈ S, G.IsNClique 3 t) (hSpairwise : (S : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) (X : Finset (Sym2 V)) (hX : X ⊆ G.edgeFinset) (hXmeets : ∀ t : Finset V, G.IsNClique 3 t → (∃ e ∈ F, ∀ x ∈ e, x ∈ t) → ∃ e ∈ X, ∀ x ∈ e, x ∈ t) (hES : (S.biUnion finite_vertex_set_edge_encoding \ F) ⊆ X) : simple_graph_triangle_cover_number G ≤ simple_graph_triangle_cover_number (G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))) + X.card := by set H : SimpleGraph V := G.deleteEdges (↑(F ∪ X) : Set (Sym2 V)) obtain ⟨C, hCsub, hCcov, hCcard⟩ := Nat.sInf_mem (simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty H) change C.card = simple_graph_triangle_cover_number H at hCcard have hsubG : ∀ e ∈ C ∪ X, e ∈ G.edgeSet := by intro e he rw [Finset.mem_union] at he rcases he with heC | heX · have := hCsub e heC rw [SimpleGraph.edgeSet_deleteEdges] at this exact this.1 · have := hX heX rwa [SimpleGraph.mem_edgeFinset] at this have hcovG : ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ C ∪ X, ∀ x ∈ e, x ∈ t := by intro t ht by_cases hclq : H.IsClique (↑t : Set V) · obtain ⟨e, heC, het⟩ := hCcov t ⟨hclq, ht.card_eq⟩ exact ⟨e, Finset.mem_union_left X heC, het⟩ · rw [SimpleGraph.isClique_iff, Set.Pairwise] at hclq push Not at hclq obtain ⟨u, hu, v, hv, huv, hnotadj⟩ := hclq have hGadj : G.Adj u v := ht.isClique hu hv huv rw [SimpleGraph.deleteEdges_adj] at hnotadj have hdel : s(u, v) ∈ (↑(F ∪ X) : Set (Sym2 V)) := by by_contra h exact hnotadj ⟨hGadj, h⟩ rw [Finset.mem_coe, Finset.mem_union] at hdel have hxuv : ∀ x ∈ s(u, v), x ∈ t := by intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> assumption rcases hdel with hdelF | hdelX · obtain ⟨e, heX, het⟩ := hXmeets t ht ⟨s(u, v), hdelF, hxuv⟩ exact ⟨e, Finset.mem_union_right C heX, het⟩ · exact ⟨s(u, v), Finset.mem_union_right C hdelX, hxuv⟩ have hmemG : (C ∪ X).card ∈ {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} := ⟨C ∪ X, hsubG, hcovG, rfl⟩ have hle : simple_graph_triangle_cover_number G ≤ (C ∪ X).card := Nat.sInf_le hmemG have hcardle : (C ∪ X).card ≤ simple_graph_triangle_cover_number H + X.card := by have := Finset.card_union_le C X omega exact hle.trans hcardle