﻿[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.