Saturation Numbers for Cycles

Definitions and mathematical statement

For a precise conventional formulation, interpret graphs as finite, simple, and undirected, and take integers $k\geq 3$ and $n\geq 1$. These conventions and parameter ranges are not explicitly stated in the supplied record; any intended restriction such as $n\geq k$ requires confirmation.

Let $C_k$ be the cycle with vertex set $\{1,\ldots,k\}$ and edge set \[ \left\{\{i,i+1\}:1\leq i<k\right\}\cup\left\{\{k,1\}\right\}. \] A graph $G$ is $C_k$-free if it contains no subgraph isomorphic to $C_k$; the subgraph need not be induced. For distinct nonadjacent vertices $u,v$, write $G+uv$ for the graph obtained by adding the edge $\{u,v\}$. A graph $G$ is $C_k$-saturated if it is $C_k$-free and \[ \text{for every }\{u,v\}\in\binom{V(G)}{2}\setminus E(G), \qquad G+uv\text{ contains a subgraph isomorphic to }C_k. \] The universal condition includes every missing edge and is vacuous when there are no missing edges. Define \[ \operatorname{sat}(n,C_k) = \min\left\{|E(G)|:\ V(G)=\{1,\ldots,n\},\ G\text{ is }C_k\text{-saturated}\right\}. \] Problem. Determine the exact value of $\operatorname{sat}(n,C_k)$ as a function of $n$ and $k$, subject to confirmation of the intended parameter range. The supplied statement does not exclude $n<k$, prescribe a sufficiently large $n$ condition, or specify particular cycle lengths.

The supplied dated curation labels the problem partially solved and states that asymptotic order and bounds are proved while the exact value remains open in general. This is a supplied literature assessment, not an independently verified mathematical or current-status claim.

Short English statement

Determine the smallest number of edges in an $n$-vertex graph that contains no cycle of length $k$, but acquires such a cycle whenever any missing edge is added. The draft explicitly adopts the usual simple undirected graph and non-induced subgraph conventions; the source leaves the intended ranges of $n$ and $k$ unspecified.

Sources

• Local UnsolvedMath registry, supplied complete source record: permanent ID $30001653$, title "Saturation Numbers for Cycles," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2011 and supplies no named proposer.
• Supplied report attribution: Combinatorics (2011), Oberwolfach Reports, pp. 5--83, DOI 10.4171/owr/2011/01. https://doi.org/10.4171/owr/2011/01. The supplied background describes the report as documenting workshop discussions and open problems; no specific problem page or passage is supplied.
• Supplied literature reference labeled "Füredi--Kim": https://arxiv.org/abs/1103.0067.
• Supplied literature reference labeled "Exact C6 bounds": https://arxiv.org/abs/2108.03910.
• Literature assessment date: 2026-08-21. This is supplied dated curation, not independently verified. Its status is "partially solved," with the assessment that asymptotic order and bounds for cycle saturation are proved but the exact value of $\operatorname{sat}(n,C_k)$ remains open in general. The supplied background expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified; its supplied verification note says that the complete statement was preserved while previously undelimited mathematical notation was normalized into readable prose. This records the supplied editorial label and does not establish independent source verification or mathematical review.