# Thread: Hamiltonian Graphs

1. ## 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!

2. ## 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.

3. ## 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.

,

,

### let G be a 6-regular of order 6

Click on a term to search for related topics.