simple_graph_triangle_cover_number_eq_zero_of_clique_free
A triangle-free graph has triangle cover number 0.
Statement
theorem simple_graph_triangle_cover_number_eq_zero_of_clique_free {V : Type*} (G : SimpleGraph V) (h : G.CliqueFree 3) : simple_graph_triangle_cover_number G = 0
- Source
- Sanity lemma for the triangle cover number, arXiv:2610.15539 (Tuza's conjecture under an edge-count condition).
- Verified
- 14 Oct 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.
- Used by 5
- simple_graph_triangle_cover_number_le_two_of_packing_number_le_oneTuza's conjecture holds for graphs with packing number at most 1: if ν(G) ≤ 1, then τ(G) ≤ 2.
- simple_graph_triangle_cover_number_le_three_mul_packing_numberEvery finite graph satisfies τ(G) ≤ 3ν(G): the edges of a maximum family of edge-disjoint triangles meet every triangle.
- simple_graph_triangle_cover_number_monoTriangle cover number is monotone under subgraph inclusion: if H ≤ G, then τ(H) ≤ τ(G).
- simple_graph_triangle_cover_number_delete_edge_leDeleting an edge e from G decreases the triangle cover number by at most 1: τ(G) ≤ τ(G \ {e}) + 1.
- simple_graph_triangle_cover_number_le_two_mul_packing_of_uniform_local_reductionsIf every finite graph containing a triangle has a proper subgraph and a local packing-cover certificate that extends every packing of that…
The proof, explained
The triangle cover number of a graph is defined as the minimum size of an edge set that intersects every triangle (3-clique). Since the graph is assumed to be triangle-free, the empty set of edges vacuously covers every triangle. Because the empty set has size 0 and the cover number is a non-negative integer, the triangle cover number must be 0.
It suffices to show that 0 is the cardinality of a valid triangle cover of G.
The triangle cover number of G is defined as the infimum of the sizes of edge sets that cover all 3-cliques. Since any natural number less than or equal to 0 must be 0 (by Nat.eq_zero_of_le_zero), and the infimum of a set of natural numbers is bounded above by any member of the set (by Nat.sInf_le), it suffices to exhibit a valid triangle cover of size 0.
uses
Nat.eq_zero_of_le_zero,Nat.sInf_leapply Nat.eq_zero_of_le_zero apply Nat.sInf_le
The empty set of edges is a valid triangle cover of size 0.
We choose the edge set F = ∅. Vacuously, all of its elements are edges of G, and its cardinality is 0. Furthermore, the requirement that every 3-clique contains an edge of F is vacuously satisfied because G is assumed to be clique-free of order 3 (h), so no 3-cliques exist in G.
exact ⟨∅, by simp, fun t ht => absurd ht (h t), rfl⟩
Nat.eq_zero_of_le_zero- A natural number that is less than or equal to 0 is equal to 0.
Nat.sInf_le- The infimum of a set of natural numbers is at most any element of the set.
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_eq_zero_of_clique_free {V : Type*} (G : SimpleGraph V) (h : G.CliqueFree 3) : simple_graph_triangle_cover_number G = 0 := by apply Nat.eq_zero_of_le_zero apply Nat.sInf_le exact ⟨∅, by simp, fun t ht => absurd ht (h t), rfl⟩