[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:02.00,Default,,0000,0000,0000,,So the answer here is n,
Dialogue: 0,0:00:02.00,0:00:05.00,Default,,0000,0000,0000,,and to see this, let's start from the second part of the statement.
Dialogue: 0,0:00:05.00,0:00:09.50,Default,,0000,0000,0000,,Let's say that a graph has a Hamiltonian cycle; then that means it can start
Dialogue: 0,0:00:09.50,0:00:15.00,Default,,0000,0000,0000,,at one vertex and end at another, passing through every vertex on the way.
Dialogue: 0,0:00:15.00,0:00:22.00,Default,,0000,0000,0000,,Now if each edge has a length 1, then the shortest tour from one end to the other
Dialogue: 0,0:00:22.00,0:00:24.00,Default,,0000,0000,0000,,is going to pass through each of those edges.
Dialogue: 0,0:00:24.00,0:00:28.00,Default,,0000,0000,0000,,And then the shortest tour for the given graph has a length of n.
Dialogue: 0,0:00:28.00,0:00:32.00,Default,,0000,0000,0000,,Now let's say instead that we have a shortest tour for a given graph
Dialogue: 0,0:00:32.00,0:00:37.00,Default,,0000,0000,0000,,with n vertices, and it has length n, with the stipulation that each edge has length 1.
Dialogue: 0,0:00:37.00,9:59:59.99,Default,,0000,0000,0000,,Then we can simply use that shortest tour as the Hamiltonian cycle and be done.