From one to many rainbow Hamiltonian cycles

Given a graph $G$ and a family $\mathcal{G}=\{G_1,\dots ,G_n\}$ of subgraphs of $G$, a transversal of $\mathcal{G}$ is a pair $(T,\varphi )$ such that $T\subseteq E(G)$ and $\varphi :T\to [n]$ is a bijection satisfying $e \in G_{\phi(e)}$foreach$e \in T$\mathrm{.}WecallatransversalHamiltonianif$T$correspondstotheedgesetofaHamiltoniancyclein$G$. We show that, under certain conditions on the maximum degree of $G$ and the minimum degrees of the $G_i\in \mathcal{G}$, for every $\mathcal{G}$ which contains a Hamiltonian transversal, the number of Hamiltonian transversals contained in $\mathcal{G}$ is bounded below by a function of $G$’s maximum degree. This generalizes a theorem of Thomassen stating that, for $m\ge 300$, no $m$-regular graph is uniquely Hamiltonian. We also extend Joos and Kim’s recent result that, if $G = K_n$andeach$G_i \in $\mathcal{G}$$hasminimumdegreeatleast$\frac{n}{2}$, then $\mathcal{G}$ has a Hamiltonian transversal: we show that, in this setting, $\mathcal{G}$ has exponentially many Hamiltonian transversals. Finally, we prove analogues of both of these theorems for transversals which form perfect matchings of $G$.