AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_number_eq_zero_of_clique_free

theoremverified

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
Used by 5

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.

  1. 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.

    lines 3–4

    uses Nat.eq_zero_of_le_zero, Nat.sInf_le

      apply Nat.eq_zero_of_le_zero
      apply Nat.sInf_le
  2. 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.

    line 5

      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

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⟩
See it in the graphDiscuss this resultChallenge it