There are no nontrivial uniquely C_9-saturated graphs
Abstract
A graph G is uniquely C_t-saturated if G contains no cycle of length t and, for every edge e of the complement, G+e contains exactly one cycle of length t; it is nontrivial if it has at least t vertices. Wenger and West proved that no nontrivial uniquely C_6- or C_7-saturated graphs exist, and conjectured the same for every t >= 6; the case t=8 was verified but never published, and t >= 9 has remained open. We prove the conjecture for t=9: there is no nontrivial uniquely C_9-saturated graph. The proof is a case analysis on the length L of a longest even cycle of length at most 12 (L is 4, 6, 8, 10, or 12). The cases L=12, L=10, and L=4 are settled by hand; for L=6 and L=8, hand classifications of the components outside the cycle reduce each case to a bounded finite family of configurations, eliminated by a short, replayable computer enumeration with known-answer controls and completeness certified by zero cap hits. Along the way we prove, in sharpened form, the t=9 instance of a structural lemma Wenger and West stated without proof.
Related
BibTeX
@misc{khan2026there,
title = {{There are no nontrivial uniquely C_9-saturated graphs}},
author = {Fayzan Khan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33035},
eprint = {2609.33035},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33035},
}
RIS
TY - UNPB
TI - There are no nontrivial uniquely C_9-saturated graphs
AU - Fayzan Khan
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33035
UR - https://arxiv.org/abs/2609.33035
AB - A graph G is uniquely C_t-saturated if G contains no cycle of length t and, for every edge e of the complement, G+e contains exactly one cycle of length t; it is nontrivial if it has at least t vertices. Wenger and West proved that no nontrivial uniquely C_6- or C_7-saturated graphs exist, and conjectured the same for every t >= 6; the case t=8 was verified but never published, and t >= 9 has remained open. We prove the conjecture for t=9: there is no nontrivial uniquely C_9-saturated graph. The proof is a case analysis on the length L of a longest even cycle of length at most 12 (L is 4, 6, 8, 10, or 12). The cases L=12, L=10, and L=4 are settled by hand; for L=6 and L=8, hand classifications of the components outside the cycle reduce each case to a bounded finite family of configurations, eliminated by a short, replayable computer enumeration with known-answer controls and completeness certified by zero cap hits. Along the way we prove, in sharpened form, the t=9 instance of a structural lemma Wenger and West stated without proof.
ER -