Optimal Constructions for Cycle Saturation

Definitions and mathematical statement

For reference, under the usual convention of finite simple undirected graphs, let $C_k$ denote the cycle on $k\geq 3$ vertices. A graph $G$ is $C_k$-saturated if it contains no subgraph isomorphic to $C_k$, but adding any missing edge creates such a subgraph. A graph $G$ is $C_k$-semisaturated if adding any missing edge creates a new copy of $C_k$; existing copies are allowed. Copies here need not be induced. With these conventions, define \[ \operatorname{sat}(n,C_k)=\min\{|E(G)|:|V(G)|=n,\ G\text{ is }C_k\text{-saturated}\}, \] \[ \operatorname{ssat}(n,C_k)=\min\{|E(G)|:|V(G)|=n,\ G\text{ is }C_k\text{-semisaturated}\}. \] These definitions provide conventional terminology; the supplied record does not establish the precise graph conventions or the intended range of $k$.

The retained conjecture says that both constructions referred to in the source attain their respective minima whenever $n>n_0(k)$. If those constructions are denoted provisionally by $G^{\mathrm{sat}}_{n,k}$ and $G^{\mathrm{ssat}}_{n,k}$, its intended logical form is: for every $k$ in the source's unspecified admissible range, there exists a positive integer $n_0(k)$ such that, for every positive integer $n>n_0(k)$, the two constructions are defined, have $n$ vertices, have their respective saturation properties, and satisfy \[ |E(G^{\mathrm{sat}}_{n,k})|=\operatorname{sat}(n,C_k),\qquad |E(G^{\mathrm{ssat}}_{n,k})|=\operatorname{ssat}(n,C_k). \] This is only a conditional schema: the supplied record does not specify either construction or its edge count. Its statement-verification field describes the constructions as diagram-dependent and unrecoverable in standalone text, and its statement status is unrecoverable. Consequently, an explicit, independently interpretable optimality conjecture cannot be recovered from this record alone; no construction or extremal formula is supplied here.

Short English statement

The source conjectures that two particular constructions attain the cycle saturation and cycle semisaturation minima for all sufficiently large $n$, with the threshold depending on $k$. The constructions and the intended range of $k$ are missing, so only a conditional formulation is possible. The supplied open label is dated curation, not an independently verified status.

Sources

• Local UnsolvedMath registry, permanent ID $30001655$, title: Optimal Constructions for Cycle Saturation; exact source problem code: catalogue entry. The supplied record gives proposed year 2011 and no named proposer.
• Combinatorics (2011), Oberwolfach Reports, pp. 5--83, DOI 10.4171/owr/2011/01. Supplied source report and literature-source label: Oberwolfach Report 01/2011. https://doi.org/10.4171/owr/2011/01.
• Füredi--Kim, supplied literature reference, DOI 10.1002/jgt.21668. https://doi.org/10.1002/jgt.21668. The record supplies no paper title or more specific bibliographic locator.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and reports that optimality is explicitly left as Conjecture 4, while the primary paper supplies bounds rather than the asserted equality. This is supplied dated curation derived from the Oberwolfach material, not independently verified here; the status and cited claims require independent verification.
• The supplied statement-verification note says that the two constructions depend on diagrams and are not specified in recoverable standalone text. No separate clean statement is promoted; the original record is retained publicly for provenance.