# Hamiltonian Graphs

• Sep 22nd 2012, 05:38 AM
dlucio
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! (Bow)
• Sep 23rd 2012, 12:34 AM
johnsomeone
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.
• Sep 25th 2012, 02:10 AM
dlucio
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.