So first of all I know finding MST is in P and is not NP complete. But I checked last year exams from my University and there is a problem: Given that Minimum Spanning Tree is NP-complete show that Hamiltonian Cycle is NP complete.
So I guess it is an assumption.
Is it just to say that if we find Hamiltonian cycle we can remove an edge with the heaviest weight and we get MST? But this is not a case because Hamiltonian cycle does not give us least weight edges.. This probably could be done with Traveling Salesmen Problem though.
Anyway, any ideas?