Minimum number to remove from a complete graph
At least how many edges should we remove from a G complete graph with n vertice so that G contains no Hamiltonian cycle?
So I want the minimum number to remove so that there is a graph on n vertices with that many edges removed that has no Hamiltonian cycle.
I think we should see two things if we find this minimum number:
- First, we should prove that if we remove that many edges then the graph has no Hamiltonian cycle.
- Secondly, we should prove that if we remove less edges from the graph, then it still has a Hamiltonian cycle.
Unfortunately I can't see them, but I would be glad if you helped me!