# Given that Minimum Spanning Tree is NP-complete show that Hamiltonian Cycle is NP complete

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?

We know that MST $\in P$. If MST $\in NPC$, then by definition of $NPC$ it means that every language in $NP$ is polynomially reducible to MST. But then, since MST $\in P$, every problem in $NP$ is in $P$. Thus, we can reduce any language $L$ in $NP$ to any other language $L'$ that has at least one member $X'_t \in L'$ and one member $X'_f \not \in L'$ as follows: compute whether $X \in L$ in polynomial time (since $L \in NP \in P$). Then, if $X \in L$, reduce it to $X'_t$. Otherwise, reduce it to $X'_f$.