The minimum number of triangles covering the edges of a graph

Suppose that a connected graph G has n vertices and m edges, and each edge is contained in some triangle of G. Bounds are established here on the minimum number t min (G) of triangles that cover the edges of G. We prove that ⌈(n ‐ 1)/2⌉ ⩽ t min (G) with equality attained only by 3‐cactii and by strongly related graphs. We obtain sharp upper bounds: if G is not a 4‐clique, then.The triangle cover number t min (G) is also bounded above by Γ(G) = m ‐ n + c, the cyclomatic number of a graph G of order n with m edges and c connected components. Here we give a combinatorial proof for t min (G) ⩽ Γ(G) and characterize the family of all extremal graphs satisfying equality.