• Amara On Demand is featured in a brand new book called Ghost Work
Check it out! Hide

## ← 10ps-10 Just Once 2 Solution

• 1 Follower
• 10 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=F4A7raMqVqg" data-team="udacity"></div> ``` 1 Language

Showing Revision 1 created 10/24/2012 by Amara Bot.

1. So the answer here is n,

2. and to see this, let's start from the second part of the statement.
3. Let's say that a graph has a Hamiltonian cycle; then that means it can start
4. at one vertex and end at another, passing through every vertex on the way.
5. Now if each edge has a length 1, then the shortest tour from one end to the other
6. is going to pass through each of those edges.
7. And then the shortest tour for the given graph has a length of n.
8. Now let's say instead that we have a shortest tour for a given graph
9. with n vertices, and it has length n, with the stipulation that each edge has length 1.
10. Then we can simply use that shortest tour as the Hamiltonian cycle and be done.