C4-Saturation Obstruction for Comb-Cores: A Certificate-Based Approach to Edge-Completion
Abstract
We prove that a specific comb-core graph H on 7 vertices, while avoiding all power-of-twocycle lengths, becomes C4-saturated relative to its degree-deficit vertices. This saturationproperty implies that every edge-completion of H achieving minimum degree δ ≥ 3 mustcontain a 4-cycle. We provide explicit 3-path witnesses as checkable certificates for thesaturation claim.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Graph Theory Research
Graph theory and applications
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 30 January 2026
- Language
- EN