Induced C_{2t}-saturation edge-addition existence

Question 1.7 · arXiv:2505.24100

arXiv Question high confidence— first stated 2025-06-02

Authors: Xinyue Fan, Sahab Hajebi, Sepehr Hajebi, Sophie Spirkl

Status open high confidence

Question 1.7 from arXiv:2505.24100 asks whether the edge-addition half of the induced saturation condition can be satisfied for even cycles $C_{2t-2}$ with $t \geq 6$: specifically, whether there exists a graph $G$ that is $C_{2t-2}$-free but such that adding any non-edge creates an induced $C_{2t-2}$. The paper proves Theorem 1.6 (the edge-deletion half) and notes that small cases ($C_4, C_6, C_8, C_{10}$) have known induced-saturated graphs (icosahedron, Cartesian product of two 5-cycles, dodecahedron, and a 28-vertex computer-found graph), but the full edge-addition problem for $t \geq 6$ ($C_{10}$ and beyond) remains wide open. No follow-up resolving this question was found in a wide literature search.

Reviewer notes. Paper submitted May 30 / revised June 2, 2025. The conjecture is less than one year old; absence of follow-up in the indexed literature is expected and consistent with open status. The edge-deletion half (Theorem 1.6) is the main result of the source paper; the edge-addition half (Question 1.7) is explicitly left open. Known induced-saturated examples exist only for small even cycles (C_4 through C_10), and the paper states 'it remains wide open whether induced-saturated graphs exist for even cycles on 12 or more vertices.'

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. Let $t\geq 6$ be an integer. Does there exist a graph $G$ with $E(\overline{G})\neq\varnothing$ such that $G$ is $H$-free but $G+e$ has an induced subgraph isomorphic to $C_{2t-2}$ for every $e\in E(\overline{G})$?

Context

The authors prove Theorem 1.6 constructing graphs that are $C_{2t}$-free but where removing any edge creates an induced copy of $C_{2t}$ (half of the induced saturation condition). Question 1.7 asks about the other half: whether the edge-addition condition can also be satisfied, which would be a key step toward solving the induced saturation problem for all even cycles.

Source paper

Halfway to induced saturation for even cycles
Xinyue Fan, Sahab Hajebi, Sepehr Hajebi, Sophie Spirkl · 2025-06-02
https://arxiv.org/abs/2505.24100