Results 1 to 3 of 3

Math Help - Hamiltonian Graphs

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Italy
    Posts
    7

    Hamiltonian Graphs

    Could someone please assist in solving the following problem:

    Let G be a 6-regular graph of order 10 and take u,v in V(G). Prove that G, G-u, G-u-v are all Hamiltonian.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Hamiltonian Graphs

    According to Wikipedia (my books are in storage): "A simple graph with n vertices (n ≥ 3) is Hamiltonian if each vertex has degree n / 2 or greater (Dirac 1952)"
    Each vertex of G has degree 6 >= 10/2, so G is Hamiltonian.
    Each vertex of G-u has degree 5 or 6 >= 9/2, so G-u is Hamiltonian.
    Each vertex of G-u-v has degree 4, 5 or 6 >= 8/2, so G-u-v is Hamiltonian.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    Italy
    Posts
    7

    Re: Hamiltonian Graphs

    Thanks for response, I used another approach, yours is simpler but I did not know of such a result. I used a Theorem which states that if the minimum degree is greater than or equal to [(n+k-2)/2] then G is k-connected. Where '[]' is ceiling function.
    I then used Theorem which states "If G is a graph of order n >= 3 such that for every pair u,v of distinct nonadjacent vertices deg u + deg v >= n then G is Hamiltonian."

    Could you please see if you can help with most recent problem I posted. Also about Hamiltonian graphs.
    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. Hamiltonian System
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: March 28th 2010, 11:36 AM
  3. If T is a tree, how can T^2 be hamiltonian?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 16th 2009, 09:24 PM
  4. hamiltonian graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 30th 2009, 10:15 PM
  5. Hamiltonian regular graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 8th 2006, 07:41 PM

Search Tags


/mathhelpforum @mathhelpforum