Spanning Near-Squares of Odd Cycles

Definitions and mathematical statement

Let $n\geq 7$ be an odd integer. Under the standard convention that graphs are finite, simple, and undirected, write $\delta(G)$ for the minimum vertex degree of a graph $G$. Let $C_n$ have vertices $v_0,\ldots,v_{n-1}$ in cyclic order. Its square $C_n^2$ joins two distinct vertices precisely when their distance in $C_n$ is at most $2$.

The following makes the target precise under the interpretation that "peripheral edges" are the edges of the original cycle and that "consecutive" refers to its cyclic order. Define \[ D_n=\{v_{2j+3}v_{2j+4}:j=0,\ldots,(n-5)/2\}, \qquad H_n=C_n^2-D_n. \] Thus $D_n$ consists of alternate cycle edges covering exactly $v_3,\ldots,v_{n-1}$. In $H_n$, the three consecutive vertices $v_0,v_1,v_2$ have degree $4$, and every other vertex has degree $3$.

Under this interpretation, the supplied question is whether \[ \text{for every odd integer }n\geq7\text{ and every graph }G,\quad \left(|V(G)|=n\ \text{and}\ \delta(G)\geq\lceil n/2\rceil\right) \Longrightarrow H_n\subseteq G, \] where $H_n\subseteq G$ means that there is a bijection $f:V(H_n)\to V(G)$ such that every edge $uv\in E(H_n)$ satisfies $f(u)f(v)\in E(G)$. The required copy is spanning and need not be induced.

The source record does not explicitly define "peripheral edges" or state the graph convention. Consequently, this precise formulation is conditional on the interpretations above; their agreement with the original workshop problem requires human review.

Short English statement

For each odd $n\geq7$, must every $n$-vertex graph of minimum degree at least $\lceil n/2\rceil$ contain the specified spanning subgraph of a squared cycle, with three consecutive vertices of degree $4$ and all others of degree $3$? The explicit target above interprets peripheral edges as original cycle edges. The supplied dated curation labels the problem partially solved and the exact question unresolved; this assessment has not been independently verified.

Sources

• Supplied local problem registry, permanent UnsolvedMath ID $30002470$, title "Spanning Near-Squares of Odd Cycles," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The supplied proposed year is $2014$; no individual proposer is identified.
• Supplied source citation: Combinatorics (2014), Oberwolfach Reports, DOI 10.4171/owr/2014/01, pp. 5--90. https://doi.org/10.4171/owr/2014/01. The record describes this report as documenting workshop discussions and open problems.
• Supplied literature source: "Oberwolfach combinatorics report." https://ems.press/content/serial-article-files/46491.
• Supplied literature source: "Heinig, dense graph cycle spaces." https://arxiv.org/abs/1112.5101.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem partially solved, reports related dense asymptotic spanning-cycle results above the exact threshold, and reports finding no result proving the specified spanning graph for every odd $n$. It describes the exact problem as unresolved. This is supplied dated literature triage derived from the OWR curation, not an independently verified assessment; its time-sensitive status and cited claims require independent checking.