The decision problem of whether a \(3-\) connected planar cubic graph \(G_0\)  has a hamiltonian
cycle is NP-complete, as shown by Garey et al. [1]}.
Let \(e =uv\in E(G_0)\) . Then the decision problem of whether \(G_0\)  has a hamiltonian
cycle traversing this specified edge \(e\) , is also
NP-complete. Let \(G_0^{^{\prime }}=G_0\setminus \lbrace e\rbrace \) . Thus, the decision problem
of whether \(G_0^{^{\prime }}\)  has a hamiltonian path from \(u\)  to \(v\)  is also NP-complete.
