Recently, this problem was given in my algorithm class:
"Given an undirected graph G = (V, E). We want to remove some edges such that all biconnected components in G does not change (specifically, "change" here refers to set of vertices). Find a way of removing maximum number of edges."
We can see that for cases in which a component consists of a Hamiltonian cycle, the problem becomes finding the Hamiltonian cycle and remove all other edges in that component. This is a NP-Complete problem. So, is it possible conclude that the original problem is also NP-Complete?
As a technicality, the original problem is NP-hard, not NP-complete (as it is not in NP, which only contains decision problems).
If you established that this algorithm is forced to find a hamiltonian cycle for every graph which has one (which seems to make sense), then this algorithm can be used to solve the hamiltonian cycle problem, which would mean that it must be at least as hard -- therefore it is NP-hard.