Tuza's conjecture for graphs of maximum degree at most seven

Abstract

Tuza conjectured that every finite simple graph $G$ satisfies $\tau (G)\le 2\nu (G)$, where $\nu (G)$ is the maximum number of pairwise edge-disjoint triangles and $\tau (G)$ is the minimum number of edges whose deletion makes $G$ triangle-free. Puleo proved the conjecture for every graph of maximum average degree less than $7$; this covers maximum degree at most $6$ but no $7$-regular graph. We prove the conjecture for maximum degree at most $7$. The proof uses Puleo's reducible-set framework. At average degree seven his discharging step no longer forces a reducible configuration. In a minimal $7$-regular counterexample every vertex link is a connected seven-vertex graph outside the weak Konig-Egervary class. An exhaustive census of such links supplies, at every vertex, an incident edge lying in four, five or six triangles. We prove that its endpoints form a reducible pair: codegrees five and six use a packing and covering template and Fano-plane witnesses, while codegree four uses an explicit catalogue of 1,144 machine-checked local certificates. We do not provide a human-readable proof of that catalogue; the certificates and their verifiers accompany the paper. The constant $2$ is sharp already at maximum degree three.

17 pages. Ancillary files include 1,144 machine-checkable local certificates and their verification code. Companion repository: https://github.com/agupta/tuza-maximum-degree-seven