Fleischner mentions in his article Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs about the uniqueness of compatible cycle decomposition that it is straight forward to see. (on page 455)
We can indeed argue by contradiction that if there was any other compatible disjoint cycle decomposition then it would contradict the uniqueness of the dominating cycle and unique Hamiltonian cycle(multigraph) being constructed in the Theorem 3.
What is puzzling for me is that how do that compatible disjoint cycle decomposition to begin with. Is there any result which can tell about compatible disjoint cycle decomposition or am I missing something there?
CYCLE DECOMPOSITION : A system of cycles $S = \{C_1, \ldots, C_m\}$ in a multigraph graph $H$ is called a cycle cover of $H$ if the union of the cycles in $S$ covers all the edges of $H$. If the cycles in $S$ do not share any edges, $S$ is called a cycle decomposition of $H$. And, $S = \emptyset $ is a cycle decomposition if $H$ has no edges.
TRANSITION SYSTEM : For every $v \in V(G)$, let $X(v)$ denote a partition of the set of edges incident to $v$ into classes of two elements. Each class is called a transition, and we call $X = \bigcup_{v \in V(G)} X(v)$ a (complete) system of transitions.
COMPATIBILITY between a cycle decomposition $S$ and an Eulerian trail $T $ is defined as follows:
- For a given Eulerian trail $T$ let $X_T$ be the system of transitions that describes how the trail moves from one edge to another at each vertex.
- For a cycle decomposition $S$, let $X_S$ be the system of transitions that describes how the cycle decomposition pairs edges at each vertex.
- The cycle decomposition $S$ is said to be compatible with the Eulerian trail $T$ if the systems of transitions $X_T$ and $X_S$ are disjoint, meaning that no transition in $T$ belongs to the same cycle in $S$.
P.S: The aforementioned article is behind a paywall. I used scihub to download it.
