Minimum number to remove from a complete graph

Printable View

• Oct 14th 2010, 10:30 AM
zadir
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!
Thank you!
• Oct 14th 2010, 03:11 PM
Traveller
The answer is n-2. Can you show why removing n-2 edges is sufficient to prevent G from containing a Hamiltonian cycle ?

Now we will prove why n-2 edges are necessary. The base case is easy to see. Assume that the claim holds true for upto n=m. For n = m+1, suppose removing m-2 edges is sufficient. Then choose such an edge which is removed and remove a vertex v that was incident to it, to form graph G'. Thus n decreases to m and the edges removed from G' are m-3. So, by our induction hypothesis, G' must contain a Hamiltonian cycle. If v has sufficient number of edges to G', then we can include it to expand the Hamiltonian cycle. If not, then in G, a large number of edges that we have removed must have been incident to v. Note that we can conclude the same for every vertex which had an incident edge removed. Can you complete the proof ?