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

How can we find a walk with the minimal length starting from a vertex $$v$$, passing through all vertices and returning back to $$v$$?

We allow vertices and edges to be repeated along the walk. The length of a walk is the number of edges it has, counting repeated edges as many times as they appear.

I'm not sure if such a problem has been extensively studied. For example, our graph is the following graph; if we choose the start vertex $$“1”$$, then find the shortest distance from $$“1”$$ passing through all vertices and returning back to $$“1”$$.

I have researched the Chinese Postman Problem and the Traveling Salesman Problem. They each have their own characteristics, but at first glance, they are different from my problem. The Chinese Postman Problem requires each edge to be traversed exactly once (i.e., edges cannot be repeated), while the Traveling Salesman Problem requires each vertex to be traversed exactly once (i.e., vertices cannot be repeated). My problem is more flexible. I'm not sure whether it can be reduced to these two problems.

If we directly apply the solution of the Traveling Salesman Problem, the following Maple solver will show that there is no traveling salesman tour. (To get back, we must repeat some vertices, such as the case where some vertices are cut vertices.)

with(GraphTheory):
G:=Graph({{1,5},{1,7},{1,10},{1,11},{2,10},{3,4},{3,10},
{4,10}, {5,6},{5,7},{6,7},{7,8},{8,11},{8,13},{9,12},
{10,11},{10,12},{11,12},{12,13}});
TravelingSalesman(G)

Out: infinity, []


• Here is a shorter proof. A Hamiltonian walk of length $n$ is a Hamiltonian cycle, where $n$ is the number of vertices. Since it is NP-hard to find a Hamiltonian cycle, it is NP-hard to find a Hamiltonian walk. Commented May 12, 2023 at 5:53