0:00:00.000,0:00:02.000
So the answer here is n,
0:00:02.000,0:00:05.000
and to see this, let's start from the second part of the statement.
0:00:05.000,0:00:09.500
Let's say that a graph has a Hamiltonian cycle; then that means it can start
0:00:09.500,0:00:15.000
at one vertex and end at another, passing through every vertex on the way.
0:00:15.000,0:00:22.000
Now if each edge has a length 1, then the shortest tour from one end to the other
0:00:22.000,0:00:24.000
is going to pass through each of those edges.
0:00:24.000,0:00:28.000
And then the shortest tour for the given graph has a length of n.
0:00:28.000,0:00:32.000
Now let's say instead that we have a shortest tour for a given graph
0:00:32.000,0:00:37.000
with n vertices, and it has length n, with the stipulation that each edge has length 1.
0:00:37.000,9:59:59.000
Then we can simply use that shortest tour as the Hamiltonian cycle and be done.