Tuza's Inequality and Equality Characterization for 5-Degenerate Graphs
We characterize equality in Tuza’s triangle packing–covering inequality for finite simple 5- degenerate graphs. Equality holds exactly when every nonempty triangle component, connected through shared graph edges, has edge support K4 or K5. We prove the combined statement, including τ (G) ≤ 2ν(G), where ν(G) is the maximum number of edge-disjoint triangles and τ (G) is the minimum number of graph edges meeting every triangle. Triangle-free background edges and clique blocks sharing vertices are allowed; graph order and maximum degree are unrestricted. The inequality has a short deduction from published local reductions. The equality classification requires additional residual-packing compatibility and a strict-cover saving for arbitrary outside attachments. The exact combined theorem has been checked in Lean with pinned dependencies. Historical priority and external specialist peer review remain unestablished.
Authors
- GPT Chat
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-30
- DOI
- https://doi.org/10.5281/zenodo.23821825
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00