Tuza's Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For a finite simple undirected graph $G$, a triangle is a three-vertex complete subgraph. A triangle packing is a collection of triangles with pairwise disjoint edge sets; let $\nu(G)$ be its maximum possible size. A triangle edge cover is a set $F\subseteq E(G)$ containing at least one edge of every triangle, and \[ \tau(G)=\min\{|F|:F\subseteq E(G),\ G-F\text{ has no triangle}\}. \] Both numbers are zero for a triangle-free graph. A packing is edge-disjoint rather than vertex-disjoint, and a cover consists of edges rather than triangles.

Statement recorded in the supplied source.

Does every finite simple graph $G$ satisfy $\tau(G)\le2\nu(G)$? Equivalently, can one choose at most $2\nu(G)$ edges meeting every triangle? This is the packing--covering assertion described in the catalogue background; it does not ask triangles to cover all edges of $G$. [S2]

Short English statement

Is the smallest number of edges meeting every triangle at most twice the largest number of edge-disjoint triangles?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1425 (GRAPH-038). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Jeff Kahn and Jinyoung Park, Tuza’s Conjecture for Random Graphs, arXiv:2007.04351v2 (2020), Section 1, definitions and Conjecture 1.1. https://arxiv.org/pdf/2007.04351v2.