Results 1 to 2 of 2

Math Help - Hamiltonian graph

  1. #1
    Junior Member
    Joined
    Jan 2011
    Posts
    45

    Hamiltonian graph

    Why does a graph having a Hamiltonian cycle cannot break into more than k components if k>=1 vertices are removed?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778

    Re: Hamiltonian graph

    Well, if you have a simple cycle with no other edges, then removing k vertices leaves at most k components. In an arbitrary graph with a Hamiltonian cycle, you have other edges, so the number of components cannot be higher.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hamiltonian Graph help
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: June 6th 2011, 02:54 AM
  2. Replies: 0
    Last Post: April 9th 2011, 08:57 AM
  3. Replies: 1
    Last Post: October 13th 2010, 03:58 AM
  4. Graph Theory Hamiltonian Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2009, 08:41 PM
  5. The Tutte graph is not hamiltonian
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 14th 2009, 02:51 PM

Search Tags


/mathhelpforum @mathhelpforum