Attack log — Tuza's triangle packing-covering conjecture

2026-08-17 — start

• Folder empty except PROBLEM.md. House: write only here; no git; cite what we beat; no invented dent.
• Conjecture (Tuza 1981/1990): every finite simple graph satisfies $\tau(G)\le 2\nu(G)$, where $\nu$ is the maximum number of pairwise edge-disjoint triangles and $\tau$ is the minimum number of edges meeting every triangle.
• Tonight: a certified extremal split or bounded-treewidth example, a new local exchange rule with an independently checkable certificate, or a documented residue. Isolated ILP tables are residue unless they imply a reusable lemma.

Published record (fetched tonight)

Tight examples already in Tuza 1990: every block graph whose blocks are $K_2$, $K_4$ or $K_5$ has $\tau=2\nu$. $K_4$ has $(\nu,\tau)=(1,2)$; $K_5$ has $(2,4)$. Cui–Haxell–Ma characterised the planar equality case.

Still open, and named as such tonight:

• the conjecture in general (universal constant still $66/23$);
• split graphs in full generality (threshold and $\delta\ge 3n/5$ only);
• treewidth 7 (Botler et al. stop at 6);
• Gupta Question 12.1: does $\mathrm{mad}<8$ imply Tuza?
• Gupta Question 12.3: does any 7-regular graph have $\tau=2\nu$?
• Gupta Question 12.4: $K_5$-free graphs.

Local PDFs: compute/refs/. Gupta ancillary checkers copied to compute/gupta_anc/ (replay only; not a dent).

Plan

1. Independently recompute $\nu,\tau$ on the named tight graphs, and replay Gupta's 7-vertex connected-non-WKE degree lemma (his Lemma 4.5).
2. New finite lemma: the same census on eight vertices (the link of an 8-regular vertex). This is the first step of Gupta's Question 12.1 / $\Delta\le 8$.
3. Search a new local exchange: in an 8-regular graph, the two ends of a triangle-codegree 7 (or 6) edge. Certificates must be independently checkable.
4. In parallel: small split-graph and 7-regular census for new $\tau=2\nu$ examples that are not Tuza's $K_4/K_5$-block family.
5. If the exchange search or the census does not produce a reusable lemma, leave the residue. Do not claim $\Delta\le 8$ or a split theorem we did not prove.

2026-08-17 — published numbers replayed

compute/replay_known.py independently recomputed $(\nu,\tau)$ by complete search:

Agrees with Tuza / Gupta's sharpness script. $K_8$ is 7-regular with ratio $3/2$, so Gupta's $\Delta\le 7$ theorem is not tight on the complete graph.

2026-08-17 — WKE census, n=5..8

Unlabelled, via nauty geng + two independent WKE checkers (bitset tables and a brute matching/cover scan). They agree on every n=8 graph.

n=7 unlabelled: 117 connected non-WKE graphs, every one has at least three vertices of degree $\ge 4$. This is Gupta's Lemma 4.5 (unlabelled form). Replay, not a dent. (Labelled 2^{21} counts 167871 / 166793 / 4620 not yet re-run; the unlabelled statement already matches.)

n=8 unlabelled, the first step of Gupta Question 12.1 / $\Delta\le 8$:

Lemma (verified tonight). Every connected non-WKE graph on eight vertices has maximum degree at least 4. The bound is sharp: exactly eight such graphs have $\Delta=4$. In particular the n=7 statement “at least three vertices of degree $\ge 4$” fails at n=8 (two counterexamples, graph6 G?r@e[ and G?ouUW).

Consequence for an 8-regular minimal counterexample: every link is one of the 443, so every vertex is incident with an edge of triangle-codegree in $\{4,5,6,7\}$. We cannot force codegree $\ge 5$. Gupta's high-codegree shortcut therefore does not survive at degree 8 without a codegree-4 catalogue on a 12-vertex local graph ($|A|=|B|=3$).

The eight $\Delta=4$ graphs are stored in compute/certs/n8_exceptions.json. Two of them are 4-regular (GEnfbW, 6 triangles; GEnbvG, 7 triangles).

2026-08-17 — labelled n=7 WKE replay

census_wke.py 7 --labelled scanned all $2^{21}=2{,}097{,}152$ labelled 7-vertex graphs. Exact match with Gupta Lemma 4.5:

Two independent WKE implementations (bitset tables; brute matching/cover) agree on every n=8 unlabelled graph (0 disagreements among the 443 connected non-WKE).

2026-08-17 — 8-regular codegree-7 pairs, complete

Unlabelled cores: all 1044 graphs on 7 vertices. Search (reduce_codegree.py): 1002 hub-only templates, 42 CBC certificates that use triangles inside the core, 0 failures.

Independent rebuild-and-check (verify_c7.py): every stored template $R$ expands to an explicit $(S,X)$ satisfying Puleo's three conditions; every ILP triple does too. PASS all 1044 cores.

The complete core $H=K_7$ (graph6 F~~~w) is the affine plane of order 3: $S$ is an STS(9) on $\{u,v\}\cup C$, $X=E(K_7)\cup\{uv\}$, $|S|=12$, $|X|=22\le 24$. Every pair of the 9 local vertices lies in exactly one member of $S$.

Lemma (tonight). If $G$ is 8-regular and $uv\in E(G)$ has triangle-codegree 7, then $\{u,v\}$ is Puleo-reducible. Certificates: compute/certs/c7_8reg_verified.json.

This is a new local exchange. It does not prove $\Delta\le 8$ or $\mathrm{mad}<8$: the n=8 census does not force codegree 7, only codegree $\ge 4$.

2026-08-17 — codegree 6 attempted, not closed

Same template with $t=3$ on the 156 unlabelled 6-vertex cores: 120 template, 24 transferable ILP, 12 failures including the empty graph and $K_6$. The empty-core failure is an artefact of forcing $\{ua,vb\}$ into $X$; neighbourhood-dependent certificates exist there. A transferable codegree-6 rule is not claimed. Residue: certs/reduce_c6_8reg.json.

2026-08-17 — split census n≤10

geng -S, $(\nu,\tau)$ by CBC, classical = triangle-support induces $K_3$, $K_4$ or $K_5$ (Tuza's one-clique-block family, the only split members of his $K_2/K_4/K_5$-block graphs).

No new tight split example and no split counterexample through 10 vertices. Isolated table; the implied experimental claim is “through n=10, every tight split graph is Tuza-classical”. Not a general split theorem.

2026-08-17 — 7-regular census, Gupta Q12.3

All 7-regular graphs on $n\le 12$ (1 + 5 + 1547 = 1553 unlabelled graphs). None have $\tau=2\nu$.

Spot-checked the n=12 maximiser by a second CBC run: $(\nu,\tau)=(12,16)$. Finite answer to the small-order part of Gupta Question 12.3: no 7-regular tight example exists through 12 vertices, and the unique ratio-$3/2$ graph on these orders is $K_8$. Not a bound for all 7-regular graphs.

2026-08-17 — what is a dent vs residue

• Dent: 8-regular codegree-7 Puleo reduction, 1044 independently checked certificates. New local exchange rule.
• Reusable finite lemma, not a $\Delta\le 8$ proof: every connected non-WKE 8-vertex graph has $\Delta\ge 4$, sharp on eight graphs; the n=7 “three vertices of degree $\ge 4$” statement fails at n=8.
• Residue: split n≤10 all-classical tight list; 7-regular n≤12 no-tight list; codegree-6 12-core remainder.
• Not claimed: $\Delta\le 8$, $\mathrm{mad}<8$, a split theorem, an improvement of Haxell's $66/23$, a 7-regular $\tau\le 3/2\,\nu$ theorem beyond n=12. Haxell's 1999 PDF stayed behind the Elsevier paywall; the bound is taken from every 2026 paper that quotes it.