CODEWITHSUNDEEP
algorithmgraphhamiltonian-cycle
Abhishek Jaiswal
Abhishek Jaiswal

Reputation: 308

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?

Upvotes: 0

Views: 1422

Answers (2)

tevemadar
tevemadar

Reputation: 13225

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.

Upvotes: 2

Tarik
Tarik

Reputation: 11209

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

Having a degree 2 for each vertex is a necessary but not sufficient condition to ensure a graph has a hamiltonian cycle. Accordingly, the example you provide has a hamiltonian cycle, but not all graphs having vertices of degree two necessarily have a hamiltonian cycle.

The paragraph you quoted explains the condition that guarantees the existence of a hamiltonian cycle.

[EDIT 1] "Can you please give me the example of a graph having degree 2 of each vertex but not having Hamiltonian Cycle please?"

Answer: Draw two independent triangles. Each vertex is if degree two, but you obviously cannot have a hamiltonian cycle.

However, if you have a hamiltonian cycle, that implies that all the vertices are at least of degree 2. Meaning that there is no way you will have a hamiltonian cycle if any of the vertices is of degree 0 or 1.

From a logical point of view, p => q is not equivalent to q => p. I walked in the rain without umbrella implies I got wet. I got wet does not mean that it was raining.

Graph has a hamiltonian circuit => each vertex has at least degree 2.

Each vertex has at least degree 2 does not => graph has hamiltonian circuit.

However:

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

Note: => is the symbol for implies

Upvotes: 2

Related Questions