Semisaturation Number of the Five-Cycle

Definitions and mathematical statement

Use the standard convention that graphs are finite, simple, and undirected, and that copies of cycles are not required to be induced. These conventions are not explicitly specified in the supplied record and require confirmation against the references. For an integer $k\ge 3$, let $C_k$ denote the cycle on $k$ vertices. A graph $G$ is $C_k$-semisaturated if, for every pair of distinct nonadjacent vertices $u,v$, adding the edge $uv$ creates a copy of $C_k$ containing that edge. Equivalently, adding any missing edge strictly increases the number of copies of $C_k$. The graph $G$ may already contain copies of $C_k$. Define \[ \operatorname{ssat}(n,C_k)=\min\left\{|E(G)|: |V(G)|=n,\ G\text{ is }C_k\text{-semisaturated}\right\}. \] For comparison, $\operatorname{sat}(n,C_k)$ is the corresponding minimum restricted to graphs containing no copy of $C_k$.

The self-contained conjecture selected by the supplied corrected statement is \[ \operatorname{ssat}(n,C_5)=\frac{11}{8}n+O(1)\qquad(n\to\infty). \] Precisely, does there exist a real constant $M\ge 0$ and an integer $N\ge 5$ such that, for every integer $n\ge N$, \[ \left|\operatorname{ssat}(n,C_5)-\frac{11}{8}n\right|\le M? \] The original statement additionally conjectures that certain stated constructions for $\operatorname{sat}(n,C_k)$ and $\operatorname{ssat}(n,C_k)$ are optimal whenever $n>n_0(k)$. The supplied record does not describe those constructions, their edge counts, or their applicable values of $k$. Consequently, that additional assertion cannot be formulated precisely here and remains an unresolved part of the original statement.

Short English statement

Is the minimum number of edges in an $n$-vertex graph for which every added missing edge creates a new five-cycle within a bounded additive distance of $11n/8$, uniformly for all sufficiently large integers $n$? Existing five-cycles are allowed. The original record also contains a construction-dependent optimality conjecture whose required constructions are not supplied.

Sources

• Local UnsolvedMath registry, permanent ID $30001654$, source problem code catalogue entry, title: Semisaturation Number of the Five-Cycle. The supplied record assigns the year 2011 and supplies no individual proposer.
• Combinatorics (2011), Oberwolfach Reports, DOI 10.4171/owr/2011/01, pp. 5--83. The supplied background identifies Oberwolfach Reports as documentation of mathematical workshops and their open-problem discussions. https://doi.org/10.4171/owr/2011/01
• Füredi--Kim, reference supplied in the literature sources: https://arxiv.org/abs/1103.0067.
• Supplied literature-source label: Oberwolfach Report 01/2011. https://doi.org/10.4171/owr/2011/01
• Literature assessment dated 2026-08-21: the supplied curation labels the problem open and states that the $C_5$ semisaturation equality is conjectured in the primary paper, while related bounds do not establish this exact asymptotic. This is supplied dated curation, not an independently verified literature assessment; the background explicitly requests independent verification of time-sensitive status and cited claims.
• The supplied registry labels the statement corrected_verified and reports that the official report confirms the self-contained conjecture, with the separate construction-dependent claim excluded from that correction. This source-verification assertion is supplied metadata and has not been independently checked here.