[SOLVED] What is the minimum degree of vertex required for each vertex to have a Hamiltonian cycle?

What is the minimum degree of vertex required for each vertex to have a Hamiltonian cycle?

I googled it and found:

If G = (V,E) has n ≥ 3 vertices and every vertex has degree ≥ n/2 then G has a Hamilton circuit.

But my question is if the degree of each vertex is 2 or more, then the graph can also have a Hamiltonian Cycle.

example:-

          1---->2
          2---->3
          3---->4
          4---->5
          5---->6
          6---->7
          7---->8
          8---->1

suppose the graph is undirected...

in the above example degree of each vertex is 2, so the graph will have a Hamiltonian cycle.

Then, what does the above-quoted text make sense?

Solution

Attach 2 triangular graphs by a single vertex:

*     *
|\   /|
| \ / |
|  *  |
| / \ |
|/   \|
*     *

The vertices on the sides have degrees of 2-2-2-2, the one in the middle has a degree of 4.

so it fulfills the attempted requirement of degree of each vertex is 2 or more, but it doesn't actually contain a Hamiltonian circle
and "coincidentally" it doesn't fulfill the cited requirement. n=5 in this case and vertices would need a degree >=2.5 (so, 3 in practice) in order to contain a Hamiltonian circle for sure.

And the for sure is the important part here: while you may find graphs which do not fulfill the >=n/2 requirement and still contain a Hamiltonian circle, you can't find a graph which fulfills the requirement and doesn't contain a Hamiltonian circle.