Tuza's inequality for maximum average degree at most 7.5 (= 15/2)

Let ν(G) be the maximum number of edge-disjoint triangles in a finite simple graph G and τ(G) the minimum number of edges meeting every triangle. We prove τ(G) ≤ 2ν(G) whenever the maximum average degree is at most 7.5. The strict bound uses Kandasamy’s Lemma 3.5, and equality also uses his Theorem 1.1. We prove the same inequality when the vertices of degree at least eight induce a triangle-free subgraph. Every counterexample must contain two fans on vertices of degree at least eight whose seven-edge sets are distinct. The fans may overlap. An open four-edge condition would suffice for the unrestricted conjecture. The included census through ten vertices confirms an earlier computation. The manuscript is internally reviewed, not peer reviewed. The human project lead selected the problem, proposed rotating three-dimensional graph diagrams and requested independent checks. Gia (OpenAI Codex, GPT-6.2 Astra) directed the mathematical investigation, developed the arguments, coordinated internal reviews and prepared the release candidate. Claude (Anthropic) contributed independent checks of specified proofs and finite inputs and conducted the November census. The census confirmed a July result. Model agreement alone cannot establish a theorem or its historical priority. Readers can inspect the arguments, the finite certificates and their stated dependencies.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-21
DOI
https://doi.org/10.5281/zenodo.24429312
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Tuza's inequality for maximum average degree at most 7.5 (= 15/2)

DannyExperiments
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Tuza's inequality for maximum average degree at most 7.5 (= 15/2)

DannyExperiments
preprint en

Abstract

Let ν(G) be the maximum number of edge-disjoint triangles in a finite simple graph G and τ(G) the minimum number of edges meeting every triangle. We prove τ(G) ≤ 2ν(G) whenever the maximum average degree is at most 7.5. The strict bound uses Kandasamy’s Lemma 3.5, and equality also uses his Theorem 1.1. We prove the same inequality when the vertices of degree at least eight induce a triangle-free subgraph. Every counterexample must contain two fans on vertices of degree at least eight whose seven-edge sets are distinct. The fans may overlap. An open four-edge condition would suffice for the unrestricted conjecture. The included census through ten vertices confirms an earlier computation. The manuscript is internally reviewed, not peer reviewed. The human project lead selected the problem, proposed rotating three-dimensional graph diagrams and requested independent checks. Gia (OpenAI Codex, GPT-6.2 Astra) directed the mathematical investigation, developed the arguments, coordinated internal reviews and prepared the release candidate. Claude (Anthropic) contributed independent checks of specified proofs and finite inputs and conducted the November census. The census confirmed a July result. Model agreement alone cannot establish a theorem or its historical priority. Readers can inspect the arguments, the finite certificates and their stated dependencies.

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon