simple_graph_triangle_cover_number_le_three_mul_packing_number
Every finite graph satisfies τ(G) ≤ 3ν(G): the edges of a maximum family of edge-disjoint triangles meet every triangle.
Statement
theorem simple_graph_triangle_cover_number_le_three_mul_packing_number {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : simple_graph_triangle_cover_number G ≤ 3 * simple_graph_triangle_packing_number G
- Formalizes
- The trivial bound ν(G) ≤ τ(G) ≤ 3ν(G), recalled in arXiv:2610.15539 (Tuza's conjecture under an edge-count condition), Sec. 1 (display after Conjecture 1.1); the bound Tuza's conjecture improves to 2ν.
- Verified
- 14 Oct 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.
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
- 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_eq_zero_of_packing_number_eq_zeroIf a finite graph has packing number 0, then its triangle cover number is 0.
The proof, explained
To prove τ(G) ≤ 3ν(G), we choose a maximum family T of pairwise edge-disjoint triangles in G, so that |T| = ν(G). Let F be the set of all edges of the triangles in T; then |F| ≤ 3|T| = 3ν(G). By the maximality of T, every triangle in G must share at least two vertices with some triangle in T, meaning that it contains at least one edge of that triangle. Thus F is an edge cover of all triangles in G, which implies τ(G) ≤ |F| ≤ 3ν(G).
If the vertex set V is empty, the theorem holds trivially because there are no triangles.
We case-split on whether V is empty or nonempty using `isEmpty_or_nonempty`. When V is empty, any triangle (3-clique) would have 3 vertices in an empty set, yielding 0 = 3 via `Finset.card_empty` and `Finset.eq_empty_of_isEmpty`, an arithmetic contradiction. Thus G has no triangles, so `simple_graph_triangle_cover_number_eq_zero_of_clique_free` shows τ(G) = 0, and 0 ≤ 3ν(G) holds by `Nat.zero_le`.
uses
isEmpty_or_nonempty,simple_graph_triangle_cover_number_eq_zero_of_clique_free,Finset.eq_empty_of_isEmpty,Finset.card_empty,Nat.zero_leclassical rcases isEmpty_or_nonempty V with hV | hV · rw [simple_graph_triangle_cover_number_eq_zero_of_clique_free G (fun t ht => by have := ht.card_eq rw [Finset.eq_empty_of_isEmpty t, Finset.card_empty] at this omega)] exact Nat.zero_le _
There exists a maximum family T of pairwise edge-disjoint triangles in G, with |T| = ν(G).
We define P to be the set of sizes of all collections of pairwise edge-disjoint triangles in G. The set P is bounded above by the total number of vertex subsets via `Finset.card_le_univ`, and nonempty because the empty family ∅ has size 0. By `Nat.sSup_mem`, P contains its supremum. Letting T be a packing achieving this maximum size, we have |T| = ν(G), and by `le_csSup`, any other edge-disjoint triangle packing has size at most |T|.
uses
Finset.card_le_univ,Nat.sSup_mem,le_csSupset P : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ t ∈ T, G.IsNClique 3 t) ∧ (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} with hP have hbdd : BddAbove P := by refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩ rintro n ⟨T, -, -, rfl⟩ exact Finset.card_le_univ T have hne : P.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ obtain ⟨T, hT, hTp, hTc⟩ := Nat.sSup_mem hne hbdd have hmax : ∀ T' : Finset (Finset V), (∀ t ∈ T', G.IsNClique 3 t) → (T' : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) → T'.card ≤ T.card := by intro T' h1 h2 rw [hTc] exact le_csSup hbdd ⟨T', h1, h2, rfl⟩
Each triangle in T consists of three distinct vertices, and F is defined as the union of the edges of all triangles in T.
Every triangle t ∈ T has cardinality 3, so by `Finset.card_eq_three.1`, it can be written as {x, y, z} with x, y, z pairwise distinct. By `choose!`, we extract vertex choice functions fx, fy, fz. We then define E(t) to be the set of the three edges of t, and F to be the union of E(t) over all t ∈ T.
uses
Finset.card_eq_three.1-- three edges of each triangle have h3 : ∀ t ∈ T, ∃ x y z : V, x ≠ y ∧ x ≠ z ∧ y ≠ z ∧ t = {x, y, z} := by intro t ht exact Finset.card_eq_three.1 (hT t ht).card_eq choose! fx fy fz hxy hxz hyz hxyz using h3 set E : Finset V → Finset (Sym2 V) := fun t => {s(fx t, fy t), s(fy t, fz t), s(fx t, fz t)} with hE set F := T.biUnion E with hF
The candidate edge cover F has cardinality at most 3|T|.
By subadditivity of the union (`Finset.card_biUnion_le`), |F| ≤ ∑_{t ∈ T} |E(t)|. Each E(t) is defined by three vertex insertions, so |E(t)| ≤ 3 by `Finset.card_insert_le` and `Nat.succ_le_succ`. Summing this upper bound over all t ∈ T using `Finset.sum_le_sum` gives |F| ≤ ∑_{t ∈ T} 3 = 3|T| via `Finset.sum_const`, `smul_eq_mul`, and `mul_comm`.
uses
Finset.card_biUnion_le,Finset.sum_le_sum,Finset.card_insert_le,Nat.succ_le_succ,Finset.sum_const,smul_eq_mul,mul_commhave hFcard : F.card ≤ 3 * T.card := by calc F.card ≤ ∑ t ∈ T, (E t).card := Finset.card_biUnion_le _ ≤ ∑ _t ∈ T, 3 := by apply Finset.sum_le_sum intro t _ simp only [hE] exact (Finset.card_insert_le _ _).trans (Nat.succ_le_succ ((Finset.card_insert_le _ _).trans (by simp))) _ = 3 * T.card := by rw [Finset.sum_const, smul_eq_mul, mul_comm]
Every element of F is an edge of the graph G.
Any edge e ∈ F belongs to E(t) for some triangle t ∈ T by `Finset.mem_biUnion`. The three vertices fx(t), fy(t), fz(t) belong to t. Since t is a 3-clique in G, every pair of distinct vertices in t is adjacent in G. Checking each of the three edges in E(t) using `Finset.mem_insert` and `Finset.mem_singleton`, we find that e is an edge of G.
uses
Finset.mem_biUnion,Finset.mem_insert,Finset.mem_singletonhave hFedge : ∀ e ∈ F, e ∈ G.edgeSet := by intro e he simp only [hF, Finset.mem_biUnion] at he obtain ⟨t, ht, he⟩ := he have hcl := (hT t ht).isClique have hsub : ∀ x ∈ ({fx t, fy t, fz t} : Finset V), x ∈ t := by intro x hx rw [← hxyz t ht] at hx exact hx have hx : fx t ∈ t := hsub _ (by simp) have hy : fy t ∈ t := hsub _ (by simp) have hz : fz t ∈ t := hsub _ (by simp) simp only [hE, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl · exact hcl hx hy (hxy t ht) · exact hcl hy hz (hyz t ht) · exact hcl hx hz (hxz t ht)
Any two distinct vertices of a triangle s ∈ T form one of its three edges in E(s).
Since s = {fx(s), fy(s), fz(s)}, any distinct vertices u, w ∈ s are two distinct vertices among fx(s), fy(s), fz(s). A case analysis on all pairs, using symmetry of unordered pairs (`Sym2.eq_swap`), confirms that the unordered pair {u, w} is in E(s).
uses
Finset.mem_insert,Finset.mem_singleton,Sym2.eq_swap-- every pair of distinct vertices of a packing triangle spans one of its three edges have hpair : ∀ s ∈ T, ∀ u ∈ s, ∀ w ∈ s, u ≠ w → s(u, w) ∈ E s := by intro s hs u hu w hw huw rw [hxyz s hs] at hu hw simp only [Finset.mem_insert, Finset.mem_singleton] at hu hw simp only [hE, Finset.mem_insert, Finset.mem_singleton] rcases hu with rfl | rfl | rfl <;> rcases hw with rfl | rfl | rfl <;> first | exact absurd rfl huw | simp [Sym2.eq_swap]
The edge set F covers every triangle in G: every triangle contains at least one edge from F.
Let t be a triangle in G. If t shared at most one vertex with every triangle s ∈ T, then t could not already be in T (since |t ∩ t| = 3 by `Finset.inter_self`), and T ∪ {t} would be a pairwise edge-disjoint packing of size |T| + 1 by `Finset.card_insert_of_notMem`. This would contradict the maximality of T. Hence some triangle s ∈ T must share at least two vertices with t: |s ∩ t| ≥ 2. By `Finset.one_lt_card.1`, s ∩ t contains two distinct vertices u and w. Then {u, w} is an edge in E(s) ⊆ F whose endpoints both lie in t.
uses
Finset.inter_self,Finset.mem_insert.1,Finset.coe_insert,Finset.inter_comm,Finset.card_insert_of_notMem,Finset.one_lt_card.1,Finset.mem_inter,Finset.mem_biUnion.2,Sym2.mem_iffhave hcover : ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t := by intro t ht -- some packing triangle shares two vertices with `t` have : ∃ s ∈ T, 2 ≤ (s ∩ t).card := by by_contra hno push_neg at hno have htT : t ∉ T := by intro htT have := hno t htT rw [Finset.inter_self, ht.card_eq] at this omega have h1 : ∀ s ∈ insert t T, G.IsNClique 3 s := by intro s hs rcases Finset.mem_insert.1 hs with rfl | hs · exact ht · exact hT s hs have h2 : ((insert t T : Finset (Finset V)) : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by rw [Finset.coe_insert] refine hTp.insert ?_ intro s hs _ have := hno s hs exact ⟨by rw [Finset.inter_comm]; omega, by omega⟩ have := hmax _ h1 h2 rw [Finset.card_insert_of_notMem htT] at this omega obtain ⟨s, hs, hst⟩ := this obtain ⟨u, hu, w, hw, huw⟩ := Finset.one_lt_card.1 hst rw [Finset.mem_inter] at hu hw refine ⟨s(u, w), Finset.mem_biUnion.2 ⟨s, hs, hpair s hs u hu.1 w hw.1 huw⟩, ?_⟩ intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl · exact hu.2 · exact hw.2
The triangle cover number satisfies τ(G) ≤ 3ν(G).
Since F is a valid triangle cover of G, the minimum cover size τ(G) is at most |F| by `Nat.sInf_le`. Chaining this with |F| ≤ 3|T| and |T| = ν(G) yields τ(G) ≤ 3ν(G).
uses
Nat.sInf_lecalc simple_graph_triangle_cover_number G ≤ F.card := Nat.sInf_le ⟨F, hFedge, hcover, rfl⟩ _ ≤ 3 * T.card := hFcard _ = 3 * simple_graph_triangle_packing_number G := by rw [hTc]; rfl
isEmpty_or_nonempty- Every type is either empty or nonempty.
simple_graph_triangle_cover_number_eq_zero_of_clique_free- If a simple graph contains no triangles (is 3-clique free), its triangle cover number is 0.
Finset.eq_empty_of_isEmpty- Any finite set over an empty type is the empty set.
Finset.card_empty- The cardinality of the empty set is 0.
Nat.zero_le- 0 is less than or equal to any natural number.
Finset.card_le_univ- The cardinality of any finite subset is at most the cardinality of the full finite type.
Nat.sSup_mem- A nonempty set of natural numbers that is bounded above contains its supremum (maximum).
le_csSup- Any element in a bounded-above set is at most the supremum of the set.
Finset.card_eq_three.1- If a finite set has cardinality 3, then it consists of three pairwise distinct elements.
Finset.card_biUnion_le- The cardinality of a union of finite sets is at most the sum of their individual cardinalities.
Finset.sum_le_sum- A sum of terms is bounded by the sum of termwise upper bounds.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
Nat.succ_le_succ- If n ≤ m, then n + 1 ≤ m + 1.
Finset.sum_const- Summing a constant over a finite set equals the cardinality of the set times the constant.
smul_eq_mul- Scalar multiplication of natural numbers coincides with ordinary multiplication.
mul_comm- Multiplication of natural numbers is commutative.
Finset.mem_biUnion- An element belongs to a union of sets ⋃_{a ∈ s} t(a) if and only if it belongs to t(a) for some a ∈ s.
Finset.mem_insert- An element belongs to {a} ∪ s if and only if it equals a or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Sym2.eq_swap- An unordered pair is symmetric: s(a, b) = s(b, a).
Finset.inter_self- The intersection of a finite set with itself is the set itself.
Finset.mem_insert.1- If an element belongs to {a} ∪ s, it equals a or belongs to s.
Finset.coe_insert- The coercion of {a} ∪ s to a set equals the set insertion of a into the coercion of s.
Finset.inter_comm- Intersection of finite sets is commutative.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
Finset.one_lt_card.1- If a finite set has cardinality strictly greater than 1, it contains two distinct elements.
Finset.mem_inter- An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.mem_biUnion.2- If an element belongs to t(a) for some a ∈ s, it belongs to ⋃_{a ∈ s} t(a).
Sym2.mem_iff- A vertex x is an endpoint of an unordered pair s(a, b) if and only if x = a or x = b.
Nat.sInf_le- If a natural number belongs to a set, it is an upper bound on the infimum of that set.
- Classical logic is assumed globally at line 4, allowing the proof to use the axiom of choice (`choose!`) on line 28 to pick three distinct vertices for each triangle in the packing.
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_le_three_mul_packing_number {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : simple_graph_triangle_cover_number G ≤ 3 * simple_graph_triangle_packing_number G := by classical rcases isEmpty_or_nonempty V with hV | hV · rw [simple_graph_triangle_cover_number_eq_zero_of_clique_free G (fun t ht => by have := ht.card_eq rw [Finset.eq_empty_of_isEmpty t, Finset.card_empty] at this omega)] exact Nat.zero_le _ set P : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ t ∈ T, G.IsNClique 3 t) ∧ (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} with hP have hbdd : BddAbove P := by refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩ rintro n ⟨T, -, -, rfl⟩ exact Finset.card_le_univ T have hne : P.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ obtain ⟨T, hT, hTp, hTc⟩ := Nat.sSup_mem hne hbdd have hmax : ∀ T' : Finset (Finset V), (∀ t ∈ T', G.IsNClique 3 t) → (T' : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) → T'.card ≤ T.card := by intro T' h1 h2 rw [hTc] exact le_csSup hbdd ⟨T', h1, h2, rfl⟩ -- three edges of each triangle have h3 : ∀ t ∈ T, ∃ x y z : V, x ≠ y ∧ x ≠ z ∧ y ≠ z ∧ t = {x, y, z} := by intro t ht exact Finset.card_eq_three.1 (hT t ht).card_eq choose! fx fy fz hxy hxz hyz hxyz using h3 set E : Finset V → Finset (Sym2 V) := fun t => {s(fx t, fy t), s(fy t, fz t), s(fx t, fz t)} with hE set F := T.biUnion E with hF have hFcard : F.card ≤ 3 * T.card := by calc F.card ≤ ∑ t ∈ T, (E t).card := Finset.card_biUnion_le _ ≤ ∑ _t ∈ T, 3 := by apply Finset.sum_le_sum intro t _ simp only [hE] exact (Finset.card_insert_le _ _).trans (Nat.succ_le_succ ((Finset.card_insert_le _ _).trans (by simp))) _ = 3 * T.card := by rw [Finset.sum_const, smul_eq_mul, mul_comm] have hFedge : ∀ e ∈ F, e ∈ G.edgeSet := by intro e he simp only [hF, Finset.mem_biUnion] at he obtain ⟨t, ht, he⟩ := he have hcl := (hT t ht).isClique have hsub : ∀ x ∈ ({fx t, fy t, fz t} : Finset V), x ∈ t := by intro x hx rw [← hxyz t ht] at hx exact hx have hx : fx t ∈ t := hsub _ (by simp) have hy : fy t ∈ t := hsub _ (by simp) have hz : fz t ∈ t := hsub _ (by simp) simp only [hE, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl · exact hcl hx hy (hxy t ht) · exact hcl hy hz (hyz t ht) · exact hcl hx hz (hxz t ht) -- every pair of distinct vertices of a packing triangle spans one of its three edges have hpair : ∀ s ∈ T, ∀ u ∈ s, ∀ w ∈ s, u ≠ w → s(u, w) ∈ E s := by intro s hs u hu w hw huw rw [hxyz s hs] at hu hw simp only [Finset.mem_insert, Finset.mem_singleton] at hu hw simp only [hE, Finset.mem_insert, Finset.mem_singleton] rcases hu with rfl | rfl | rfl <;> rcases hw with rfl | rfl | rfl <;> first | exact absurd rfl huw | simp [Sym2.eq_swap] have hcover : ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t := by intro t ht -- some packing triangle shares two vertices with `t` have : ∃ s ∈ T, 2 ≤ (s ∩ t).card := by by_contra hno push_neg at hno have htT : t ∉ T := by intro htT have := hno t htT rw [Finset.inter_self, ht.card_eq] at this omega have h1 : ∀ s ∈ insert t T, G.IsNClique 3 s := by intro s hs rcases Finset.mem_insert.1 hs with rfl | hs · exact ht · exact hT s hs have h2 : ((insert t T : Finset (Finset V)) : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by rw [Finset.coe_insert] refine hTp.insert ?_ intro s hs _ have := hno s hs exact ⟨by rw [Finset.inter_comm]; omega, by omega⟩ have := hmax _ h1 h2 rw [Finset.card_insert_of_notMem htT] at this omega obtain ⟨s, hs, hst⟩ := this obtain ⟨u, hu, w, hw, huw⟩ := Finset.one_lt_card.1 hst rw [Finset.mem_inter] at hu hw refine ⟨s(u, w), Finset.mem_biUnion.2 ⟨s, hs, hpair s hs u hu.1 w hw.1 huw⟩, ?_⟩ intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl · exact hu.2 · exact hw.2 calc simple_graph_triangle_cover_number G ≤ F.card := Nat.sInf_le ⟨F, hFedge, hcover, rfl⟩ _ ≤ 3 * T.card := hFcard _ = 3 * simple_graph_triangle_packing_number G := by rw [hTc]; rfl