On the number of Hamiltonian cycles in bipartite graphs (Q2785376)

Modifying \textit{A. G. Thomason's} ``lollipop'' argument [Ann. Discrete Math. 3, 259-268 (1978; Zbl 0382.05039)], the author proves that if \(C\): \(x_1y_1x_2y_2\cdots x_ny_n\) is a Hamiltonian cycle in the bipartite graph \(G\) and all vertices \(y_1,y_2,\dots,y_n\) have degree at least 3 in \(G\) then \(G\) has another Hamiltonian cycle containing the edge \(x_1y_1\). As consequences, lower bounds on the number of Hamiltonian cycles in Hamiltonian bipartite graphs are obtained, first in terms of minimum degree and secondly as a function of girth when the minimum degree is at least 4. It is conjectured that there exists a function \(f(g)\) tending to infinity with \(g\) such that every bipartite Hamiltonian graph of minimum degree 3 and girth \(g\) has at least \(f(g)\) Hamiltonian cycles. Some problems are posed two of which are: Does every Hamiltonian graph \(G\) of minimum degree at least 3 contain an edge \(e\) such that \(G-e\) and \(G/e\) are both Hamiltonian? Does there exist a 4-regular graph with precisely one Hamiltonian cycle?