# Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles

Definition: Define the $$k$$-HamiltonianCycles problem as the decision problem that asks if a given graph has at least $$k$$ distinct Hamiltonian cycles.

Question: Is there some constant $$k$$ so that the $$k$$-HamiltonianCycles problem is $$NP$$-complete on the class of planar $$4$$ connected graphs? In particular, what about $$k = 3$$? If not, what about $$k = 4$$?

Motivation: It is well known that $$1$$-HamiltonianCycles is $$NP$$-complete on the class of planar $$3$$-connected graphs. On the other hand, all planar $$4$$-connected graphs have a Hamiltonian cycle, by Tutte.

Additionally, it is known that a $$4$$-connected planar graph $$G$$ is "Hamiltonian Connected." That is, given any two vertices, $$x$$ and $$y$$, there is a Hamiltonian $$xy$$-path in $$G$$. This implies that a $$4$$-connected planar graph always has at least $$2$$ Hamiltonian cycles. Given one cycle, say $$C$$, let $$e$$ be an edge not in $$C$$. If $$\gamma$$ is the Hamiltonian path between the endpoints of $$e$$, we can extend it to a Hamiltonian cycle containing $$e$$.

If the $$4$$ connected planar graph $$G = (V,E)$$ has at least one vertex of degree $$\geq 5$$, then by $$4 |V| > \sum_{v \in V} deg(v) = 2|E|$$, $$|E| > 2|V|$$. This implies that there is an edge not in the union of any two Hamiltonian cycles of $$G$$, so that one is guaranteed a third Hamiltonian cycle by the same argument as in the previous paragraph. Since a planar graph has at most $$3n - 6$$ edges, one cannot repeat this to guarantee the existence of a fourth Hamiltonian cycle.

I don't know if there is an argument guaranteeing that all $$4$$-connected planar graphs have at least $$3$$ Hamiltonian cycles, or if there is a different kind of argument guaranteeing that all $$4$$-connected planar graphs have at least $$4$$ Hamiltonian cycles. I am wondering if these problems, or similar ones, are $$NP$$-complete.

This question is similar, but not the same: https://mathoverflow.net/questions/233476/what-is-the-complexity-of-finding-a-third-hamilton-cycle-in-cubic-graph