Compatible Euler-tours

Definitions and mathematical statement

Let $G$ be a finite connected loopless graph with every degree positive and even, and let its minimum degree be $2d$. Distinct parallel edges, if allowed, are treated as distinct objects. An Euler tour is a closed walk using every edge exactly once. At each visit to a vertex it pairs the entering edge with the leaving edge; the final and initial edges are paired too. These unordered pairs are its transitions.

Two Euler tours are compatible when they have no transition in common at any vertex. Let $q(G)$ be the greatest size of a family whose tours are pairwise compatible. The conjectured bound is \[ 2d-2\le q(G)\le2d-1. \] Thus the substantive assertion asks for at least $2d-2$ mutually compatible tours, for every such graph. At a vertex of degree $2d$, each tour uses $d$ distinct pairs from the $\binom{2d}{2}$ possible pairs, explaining the upper bound.

Tours are considered as cyclic edge traversals: rotating the start point or reversing a traversal does not provide a new transition system. Pairwise compatibility is a simultaneous requirement among all tours. Constructing a tour compatible with one previously chosen tour does not automatically construct a family of the required cardinality.

Short English statement

Does an Eulerian graph of minimum degree $2d$ always have at least $2d-2$ Euler tours sharing no local edge transition?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000013 (AMR-029-0013), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Compatible Euler-tours. Original source indexed by AMR-029-0013. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Compatible Euler-tours. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Compatible_Euler-tours.