Faithful cycle covers

Definitions and mathematical statement

Let $G=(V,E)$ be a finite loopless undirected multigraph; parallel edges are distinct. For $X\subseteq V$, write $\delta(X)$ for the set of edges with exactly one endpoint in $X$. An integer demand function $p:E\to\mathbb Z_{\ge0}$ is admissible if, for every $X\subseteq V$, the total $p(\delta(X))=\sum_{e\in\delta(X)}p(e)$ is even and \[ 2p(e)\le p(\delta(X))\qquad(e\in\delta(X)). \] Thus no edge of a cut is assigned greater demand than all the other cut edges combined. Empty cuts impose no individual-edge condition.

A faithful cycle cover for $p$ is a finite multiset of cycles of $G$ in which each edge $e$ occurs exactly $p(e)$ times, counted with multiplicity across the multiset. A cycle uses each of its vertices once, except for its coinciding start and finish; a pair of parallel edges may form a cycle of length two. Repetition of an entire cycle is allowed, while traversing a single edge repeatedly within one cycle is not.

The conjecture asserts that every admissible demand function taking only even values has a faithful cycle cover. Zero values are permitted and force those edges to be unused. The constant assignment $p(e)=2$ on a bridgeless graph gives the familiar double-cover special case, but the present statement allows different even demands on different edges. The demand and cut conditions are quantified over the entire graph, with no connectivity or planarity assumption.

Short English statement

Do all nonnegative even edge demands satisfying the necessary cut inequalities decompose exactly into a multiset of cycles?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3164 (OPG-140), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Faithful cycle covers. Original problem and discussion. http://www.openproblemgarden.org/op/faithful_cycle_covers.