Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour.

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.

A finite connected Eulerian graph has an Euler tour $W$, a closed trail using every edge exactly once. Consecutiveness in $W$ is cyclic, including the last and first edges. A cycle decomposition is an edge partition into connected $2$-regular subgraphs.

Statement recorded in the supplied source.

For every Eulerian graph $G$ of minimum degree at least $4$ and every prescribed Euler tour $W$, does there exist a cycle decomposition such that no cycle contains two edges consecutive in $W$? [S2]

Short English statement

Can the edges of an Eulerian graph be split into cycles that avoid every transition in a prescribed Euler tour?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3175 (OPG-46606). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour., original node 46606, statement and mathematical discussion. https://www.openproblemgarden.org/op/decomposing_an_eulerian_graph_into_cycles_with_no_two_consecutives_edges_on_a_prescirbed_eulerian_tour.