Results 1 to 2 of 2

Math Help - Minimum number to remove from a complete graph

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    43

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    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 ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  2. Minimum number of edges in a graph of order n
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 12th 2011, 04:27 PM
  3. number of subgraphs in a complete graph
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 29th 2010, 12:04 PM
  4. the complete graph k5
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 26th 2009, 05:52 PM
  5. Help complete a graph?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 20th 2008, 04:59 PM

Search Tags


/mathhelpforum @mathhelpforum