For any union (edge-wise) of two edge disjoint Hamiltonian cycles, there may be a different pair of edge disjoint Hamiltonian cycles which has the same union. I found for all small examples (up to 8 vertices) there are no unions which can only be obtained through one pair of edge disjoint Hamiltonian cycles. Does a unique union exist on more vertices?
Are unions of two edge-disjoint Hamiltonian cycles over the same vertices unique
graph theory
Best Answer
The conjecture that given two edge-disjoint Hamiltonian cycles, there is a different pair of edge-disjoint Hamiltonian cycles with the same union, is true, as follows from a 1978 result of Thomason. The rest of this answer describes that result.
Given a multigraph $G = (V,E)$ (possibly having loops), define a Hamiltonian pair to be a pair $\{h,\bar{h}\}$ of edge-disjoint Hamiltonian cycles in $G$. Note that there are different conventions for counting Hamiltonian cycles of multigraphs. For our purposes, the "fat triangle" consisting of three vertices, each pair of which is joined by two edges, has four distinct Hamiltonian pairs.
Let $P_G$ denote the set of Hamiltonian pairs of $G$, and given $x,y \in E$, let $P_G(x,y)$ denote the set of Hamiltonian pairs in which $x$ and $y$ lie in the same cycle. Note that if $x$ is a vertex of $G$ and $G$ is $4$-regular, then $x$ is the endpoint of exactly four edges, say $e_1$, $e_2$, $e_3$, $e_4$, and $P_G = \bigsqcup_{i=2}^4 P_G(e_1,e_i)$, from which it follows that $|P_G| = \sum_{i=2}^4 |P_G(e_1,e_i)|$.
In Section 2 of
Thomason, A.G., Hamiltonian Cycles and Uniquely Edge Colourable Graphs, Ann. Discrete Math. 3, 259-268 (1978).
the author proves the following result. (Incidentally, this journal edition was published as a book titled Advances in Graph Theory (1978) and edited by Béla Bollobás.)
Theorem. If $G$ is a $4$-regular multigraph with at least three vertices and $x$ and $y$ are two edges of $G$, then the number of Hamiltonian pairs of $G$ for which $x$ and $y$ lie in the same cycle is even.
By our earlier observation, which is made in Thomason's paper, if one can prove that $|P_G(x,y)|$ is even for all edges $x$, $y$ in a $4$-regular graph $G$, it will follow that $|P_G|$, the number of Hamiltonian pairs, is even. Now, let $G$ be the union of two edge-disjoint Hamiltonian cycles on $n$ vertices, viewed as subgraphs of $K_n$. Then $G$ is a $4$-regular graph. One Hamiltonian pair is given by taking the two Hamiltonian cycles defining $G$. Since one can assume $G$ has at least three vertices, using Thomason's result, one can produce another Hamiltonian pair in $G$, which is necessarily a Hamiltonian decomposition of $G$ because $G$ is $4$-regular.
Thomason goes on to prove the stronger result that if $m \ge 1$ and $G$ is a $2m$-regular multigraph with at least three vertices, then $G$ has at least $(3m-2)(3m-5)...7 \cdot 4$ Hamiltonian decompositions. In particular, $4$-regular graphs have at least $4$ distinct Hamiltonian pairs. Thomason also proves that for every $n \ge 10$, there is a $4$-regular graph on $n$ vertices having exactly $32$ Hamiltonian pairs.