/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Tuza's conjecture

References:

    Wikipedia

    [Tu90] Tuza, Zs. (1990). "A conjecture on triangles of graphs." Graphs Combin. 6, pp. 373--380.

    [Ha99] Haxell, P. E. (1999). "Packing and covering triangles in graphs." Discrete Math. 195, pp. 251--254.

@[expose] public sectionnamespace TuzaConjecturevariable {V : Type*}

C is a triangle cover of G: a set of edges of G meeting every triangle of G. Removing the edges of C from G leaves a triangle-free graph.

def IsTriangleCover (G : SimpleGraph V) (C : Set (Sym2 V)) : Prop := C ⊆ G.edgeSet ∧ ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ C, ∀ x ∈ e, x ∈ t

T is a triangle packing of G: a set of pairwise edge-disjoint triangles of G. Two distinct triangles are edge-disjoint exactly when they share at most one vertex.

def IsTrianglePacking (G : SimpleGraph V) (T : Set (Finset V)) : Prop := (∀ t ∈ T, G.IsNClique 3 t) ∧ ∀ t₁ ∈ T, ∀ t₂ ∈ T, t₁ ≠ t₂ → ((t₁ : Set V) ∩ (t₂ : Set V)).ncard ≤ 1

The triangle covering number τ(G): the least number of edges meeting every triangle of G.

noncomputable def triangleCoverNumber (G : SimpleGraph V) : ℕ := sInf {n | ∃ C : Set (Sym2 V), IsTriangleCover G C ∧ C.ncard = n}

The triangle packing number ν(G): the greatest number of pairwise edge-disjoint triangles of G.

noncomputable def trianglePackingNumber (G : SimpleGraph V) : ℕ := sSup {n | ∃ T : Set (Finset V), IsTrianglePacking G T ∧ T.ncard = n}

The empty set of edges covers all triangles of a triangle-free graph.

@[category API, AMS 5] lemma isTriangleCover_empty (G : SimpleGraph V) (h : G.CliqueFree 3) : IsTriangleCover G (∅ : Set (Sym2 V)) := V:Type u_1G:SimpleGraph Vh:G.CliqueFree 3⊢ IsTriangleCover G ∅ V:Type u_1G:SimpleGraph Vh:G.CliqueFree 3t:Finset Vht:G.IsNClique 3 t⊢ ∃ e ∈ ∅, ∀ x ∈ e, x ∈ t All goals completed! 🐙

A triangle-free graph has triangle covering number zero.

@[category API, AMS 5] lemma triangleCoverNumber_eq_zero (G : SimpleGraph V) (h : G.CliqueFree 3) : triangleCoverNumber G = 0 := Nat.le_zero.mp (Nat.sInf_le ⟨∅, isTriangleCover_empty G h, Set.ncard_empty _⟩)

Tuza's conjecture (1981): every finite graph $G$ satisfies $\tau(G) \le 2\nu(G)$, where $\tau(G)$ is its triangle covering number and $\nu(G)$ is its triangle packing number. The bound would be sharp, for example for $K_4$ and $K_5$.

@[category research open, AMS 5] theorem tuza_conjecture {V : Type} [Fintype V] (G : SimpleGraph V) : triangleCoverNumber G ≤ 2 * trianglePackingNumber G := V:Typeinst✝:Fintype VG:SimpleGraph V⊢ triangleCoverNumber G ≤ 2 * trianglePackingNumber G All goals completed! 🐙

Haxell (1999): every finite graph satisfies $\tau(G) \le (66/23)\nu(G)$.

Reference: [Ha99].

@[category research solved, AMS 5] theorem tuza_conjecture.variants.haxell {V : Type} [Fintype V] (G : SimpleGraph V) : (triangleCoverNumber G : ℝ) ≤ 66 / 23 * trianglePackingNumber G := V:Typeinst✝:Fintype VG:SimpleGraph V⊢ ↑(triangleCoverNumber G) ≤ 66 / 23 * ↑(trianglePackingNumber G) All goals completed! 🐙

Tuza's conjecture for triangle-free graphs.

A triangle-free graph needs no edges to cover its triangles, so the conjectured inequality holds trivially.

V:Typeinst✝:Fintype VG:SimpleGraph Vh:G.CliqueFree 3⊢ 0 ≤ 2 * trianglePackingNumber G All goals completed! 🐙end TuzaConjecture