Tuza's Conjecture for Maximum Degree at Most Seven
Tuza conjectured that every finite simple graph satisfies , where counts pairwise edge-disjoint triangles and is the fewest edges whose deletion leaves the graph triangle-free. Puleo had proved it for maximum average degree below 7. Proved here for every graph of maximum degree at most seven, crossing the equality boundary of Puleo's sparsity theorem.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-assisted
- Method
- Computation
- Field
- Extremal graph theory
- Posed by
- Zsolt Tuza
- Year posed
- 1981
- Years open
- 45y
- Solved
- 2026-08-06
- Model
- Claude Code (Claude 5 family), OpenAI Codex (GPT-5.6 family)
- Vendor
- Anthropic, OpenAI
- Collaborators
- Anish Gupta
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 30 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Settles a class, not the conjecture: Tuza's conjecture remains open in general.
What the AI did
Both were "used extensively for proof exploration, software development, exact computational checks, literature discovery, and drafting and editing the manuscript", with the author selecting the arguments and methods and checking the sources and computations. Broad rather than step-attributed, so the lower tier applies.
Verification
A preprint days old with no independent review. A certificate catalogue and verification programs ship as ancillary files and in a companion repository, so the computational part is reproducible.