Erdős Problem #167

Erdős Problem 167: triangle packing and covering

Statement and outcome

Let $\nu(G)$ be the maximum number of pairwise edge-disjoint triangles, and let $\tau(G)$ be the fewest edges meeting every triangle. Tuza's conjecture is $\tau(G)\le2\nu(G)$. We prove the elementary factor-three bound, prove the full factor-two assertion whenever $\nu(G)=1$, extend that special case over independent triangle components, and verify both standard sharp examples. The general assertion remains unresolved in this attempt.

Universal bounds

The union of the edges in a maximum triangle packing meets every triangle, since otherwise another triangle could be added. Thus \[ \nu(G)\le\tau(G)\le3\nu(G). \] The first inequality holds because each edge in a cover can meet at most one triangle of an edge-disjoint packing. Also $\tau(G)\le |E(G)|/2$: a random bipartition retains each edge as a crossing edge with probability $1/2$, so some bipartite subgraph has at least half the edges. This separate bound is useful for dense examples, but does not imply Tuza's inequality.

The case of packing number one

Assume there is at least one triangle and every two triangles share an edge. If one edge belongs to all triangles, then $\tau=1$. Otherwise choose distinct triangles $abc$ and $abd$. There is a triangle avoiding $ab$. To meet both chosen triangles in edges, it must be $acd$ or $bcd$: the only compatible choices of one of $ac,bc$ and one of $ad,bd$ share respectively $a$ or $b$. Relabel $a,b$ if necessary, so the third triangle is $acd$.

Every further triangle must meet all of $abc,abd,acd$ in edges. If it does not contain $a$, it must contain both $bc$ and $bd$, so is $bcd$. If it contains $a$, its other two vertices must be two of $b,c,d$, since otherwise it misses an edge of one of the three chosen faces. Thus every triangle is one of the four faces of this $K_4$.

Two opposite edges, for example $ab$ and $cd$, meet all four faces. Hence $\tau\le2=2\nu$. This proves, more precisely, that a graph with $\nu=1$ either has a common triangle edge or has all its triangles within one $K_4$. In particular, a $K_4$-free graph with $\nu=1$ has $\tau=1$.

A component extension and sharp examples

Form the auxiliary graph whose vertices are the triangles of $G$, joining two when they share an edge. Distinct components use disjoint sets of original edges; consequently both $\nu$ and $\tau$ add over these components. If each component is a clique, its packing number is one and the preceding proof gives Tuza's bound after summation. This includes arbitrarily many separated books and $K_4$ components.

For $K_4$, every two triangles share an edge and no edge meets all four, so $(\nu,\tau)=(1,2)$. For $K_5$, two edge-disjoint triangles exist. Three would use nine of the ten edges; their union has even degree at every vertex, whereas deleting one edge from $K_5$ leaves two vertices of degree three. Thus $\nu(K_5)=2$.

For completeness, a triangle-free graph with $n$ vertices and $e$ edges has at most $n^2/4$ edges: for each edge $uv$, the disjoint neighbourhoods give $d_u+d_v\le n$. Summing gives $\sum_vd_v^2\le ne$, whereas Cauchy gives $\sum_vd_v^2\ge4e^2/n$. Applied to $n=5$, at most six edges can remain. Deleting four edges to leave $K_{2,3}$ is possible, so $\tau(K_5)=4$.

Assessment and attribution

The factor-three packing argument and the two sharp examples appeared in the old local gpt_pro_5.2/167.tex; they have been checked and the $K_5$ packing obstruction is now supplied explicitly. The pairwise-intersecting classification provides a further proved special case. It does not handle components whose triangles admit larger packings with complicated overlap. Source: https://www.erdosproblems.com/167. No claim of a new theorem or a general solution is made.

COMPLETION ESTIMATE

COMPLETION: 30%

Erdos problem #167 (Tuza's conjecture)

1) FORMAL RESTATEMENT

For a graph $G$ let:

• $\nu(G)$ be the maximum number of edge-disjoint triangles in $G$.
• $\tau(G)$ be the minimum number of edges to delete from $G$ to obtain a triangle-free graph.

Equivalently, $\tau(G)$ is the minimum size of an edge set that intersects every triangle. Tuza's conjecture asks whether for all graphs $G$, \[ \tau(G)\le 2\nu(G). \] The problem file notes this is tight for $K_4$ and $K_5$.

2) QUICK LITERATURE/CONTEXT CHECK

The file states Krivelevich proved $\tau(G)\le (2+o(1))\nu(G)$ and that Tuza proved the conjecture for planar graphs. I do not rely on these.

3) ATTACK PLAN

Reformulate as a vertex-cover vs matching problem in a $3$-uniform hypergraph (triangles as hyperedges). This immediately gives the easy bound $\tau\le 3\nu$. Then verify tightness examples and brute-check small graphs.

4) WORK

Lemma 167.1 (easy $3\nu$ bound via maximal matching).

For every graph $G$, \[ \tau(G)\le 3\nu(G). \]

Proof. Form a $3$-uniform hypergraph $\mathcal H$ whose vertex set is $E(G)$ and whose hyperedges are the edge-sets of triangles of $G$. Then a matching in $\mathcal H$ is exactly a set of edge-disjoint triangles in $G$, so its maximum size is $\nu(G)$. A vertex cover in $\mathcal H$ is a set of edges of $G$ meeting every triangle, so its minimum size is $\tau(G)$.

Let $M$ be a maximum matching in $\mathcal H$ of size $\nu(G)$. Consider the set $C$ of all vertices of $\mathcal H$ that lie in hyperedges of $M$. Since each hyperedge has size $3$, we have $|C|=3\nu(G)$. We claim $C$ is a vertex cover: if there were a hyperedge $e$ disjoint from $C$, then $e$ is disjoint from every hyperedge of $M$, so $M\cup\{e\}$ is a larger matching, contradicting maximality of $M$. Thus $\tau(G)=\tau(\mathcal H)\le |C|=3\nu(G)$. $\square$

Lemma 167.2 (tightness of constant $2$ on $K_4$ and $K_5$).

1. For $K_4$, $\nu(K_4)=1$ and $\tau(K_4)=2$.
2. For $K_5$, $\nu(K_5)=2$ and $\tau(K_5)=4$.

Proof. For $K_4$: any two triangles share an edge, so $\nu=1$. To destroy all triangles, one must make the graph bipartite; the maximum triangle-free graph on $4$ vertices has $4$ edges, so at least $6-4=2$ edges must be removed, and removing a matching of size $2$ suffices. Hence $\tau=2$.

For $K_5$: two edge-disjoint triangles exist, e.g. on vertex sets $\{1,2,3\}$ and $\{1,4,5\}$, so $\nu\ge 2$. Three edge-disjoint triangles would require $9$ distinct edges, but any third triangle would share an edge with one of these two (easy check), so $\nu=2$. A triangle-free graph on $5$ vertices has at most $\lfloor 25/4\rfloor=6$ edges (Turán bound for $K_3$), so from $10$ edges we must remove at least $4$. Removing $4$ edges to leave $K_{2,3}$ (which has $6$ edges and is triangle-free) is possible, so $\tau=4$. Thus $\tau=2\nu$ in both cases. $\square$

FAST REALITY CHECK (brute verification for $n\le 6$).

By exhaustive enumeration of all graphs on $n\le 6$ vertices, Tuza's inequality $\tau(G)\le 2\nu(G)$ holds in all cases. Moreover, the worst ratio $\tau/\nu$ observed for $n\le 6$ is exactly $2$, attained already by $K_4$.

5) VERIFICATION

• Lemma 167.1 uses only the fact that a maximum matching hits all hyperedges via its union of vertices.
• Lemma 167.2 checks the extremal values directly and uses only the $K_3$-free edge bound $\lfloor n^2/4\rfloor$ for $n=5$.
• Computation: verified by brute force (32768 graphs for $n=6$), with exact optimization of triangle packings and triangle edge-covers.

6) FINAL

UNRESOLVED

1. (i) Strongest fully proved partial result obtained here. A universal factor-$3$ bound $\tau(G)\le 3\nu(G)$ (Lemma 167.1), plus exact tightness examples $\tau=2\nu$ for $K_4$ and $K_5$ (Lemma 167.2). Verified by brute force for all graphs on $\le 6$ vertices.

2. (ii) Exact first gap. Improve the general factor from $3$ to $2$: prove that every graph has an edge set of size at most $2\nu(G)$ meeting every triangle.

3. (iii) Top 3 next moves (concrete targets).
   1. Strengthen Lemma 167.1 by exploiting structure of triangle hypergraphs that come from graphs (not arbitrary $3$-uniform hypergraphs), e.g. via local degree constraints.
   2. Attempt a decomposition: find a maximum triangle packing, then show the remaining triangles can be hit by at most $\nu(G)$ additional edges using a discharging argument.
   3. Use linear programming relaxation of the triangle edge-cover problem and prove integrality gap $\le 2$ for triangle hypergraphs.

4. (iv) Minimal counterexample structure (if the conjecture is false). A counterexample would be a graph $G$ whose triangle hypergraph has vertex cover number strictly larger than twice its matching number. It would need many triangles with substantial overlap so that any small edge set misses some triangle, while still allowing only a small number of edge-disjoint triangles.