Oberwolfach Problem

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $H$ be a finite simple undirected $2$-regular graph on $n$ vertices, meaning every vertex has degree two; thus $H$ is a disjoint union of cycles of lengths at least three. The complete graph $K_n$ has all unordered pairs of different vertices as edges. An $H$-decomposition of $K_n$ is a collection of spanning subgraphs $H_1,\ldots,H_r$, each isomorphic to $H$, such that their edge sets partition $E(K_n)$. Degree counting forces $2r=n-1$, so $n$ must be odd and $r=(n-1)/2$.

Statement recorded in the supplied source.

Classify all finite $2$-regular graphs $H$ for which $K_{|V(H)|}$ admits an $H$-decomposition. Equivalently, for every odd $n\ge3$ and every partition $n=\ell_1+\cdots+\ell_s$ with $\ell_i\ge3$, determine whether $K_n$ can be decomposed into $(n-1)/2$ spanning copies of $C_{\ell_1}\sqcup\cdots\sqcup C_{\ell_s}$. Here $C_\ell$ is a cycle of length $\ell$, and $\sqcup$ denotes disjoint union. Even orders are impossible by parity; the finite classification includes the small exceptional cases, not only sufficiently large orders. [S2]

Short English statement

Determine precisely which collections of cycle lengths can form repeated spanning factors that partition all edges of a complete graph.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1421 (GRAPH-034). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Peter Keevash and Katherine Staden, The Generalised Oberwolfach Problem, arXiv:2004.09937v1 (2020), Section 1, “Oberwolfach Problem (Ringel)”, page 1. https://arxiv.org/pdf/2004.09937v1.