Verifying some properties of Hamiltonian Graphs

graph theoryhamiltonian-path

I want to verify these two properties of Hamiltonian graphs:

  1. Graph having multiple Hamiltonian cycles can have different cycle lengths or all are of same length?
    i.e. All Hamiltonian cycles have same length or they can have different lengths.
  2. Does Hamiltonian cycle is longest length cycle in graph?

For first property Complete graph comes to my mind but they have all same length Hamiltonian cycles.
For second property I think Hamiltonian is longest as it passes through every vertex.

Please can someone provide me more clarification about my ideas?

Best Answer

Let's look at the definition of a Hamiltonian cycle:

It is a cycle (i.e. closed path. You see, no repetition of vertices except for the starting point, no repetition of edges) that goes through all the vertices.

  1. So if we fix $n$ to be the number of vertices, each Hamiltonian cycle has the length $n$.

  2. Now suppose there is a cycle of length more than $n$. Then it has to visit some vertex multiple times, but this is in contradiction with the definition of a cycle.

Related Question