Question: How can we find a shortest closed walk passing through all vertices?

A Hamiltonian walk on a connected graph is a closed walk of minimal length which visits every vertex of a graph (and may visit vertices and edges multiple times). (See


Please note that there is a distinction between a Hamiltonian walk and a Hamiltonian cycle. Any graph can have a Hamiltonian walk, but not necessarily a Hamiltonian cycle.  The Hamiltonian number h(n) of a connected G is the length of a Hamiltonian walk. 

For example, let's consider the graph FriendshipGraph(2).


Then its Hamiltonian number is 6.  A Hamiltonian walk is as shown in the following picture.




PS: After being reminded by others, I learned that a method in the following post seems to work, but I don't understand why it works for now. 

it's possible to formulate this as a Travelling Salesman Problem by augmenting the sparse graph into a complete graph by adding edges. These new edges represent shortest paths between any two vertices in the original graph and have weight equal to the path length.


It seems that the correctness of this transformation requires rigorous proof.


Please Wait...