Is the problem of traversing every vertex of a graph (not necessarily once) without crossing an edge more than once in P?

I know that finding a Hamiltonian circuit is in NP and I know that finding an Eulerian circuit is in P. However, what about the following problem:

• Must leave the starting vertex and visit every other vertex;

• You may only return to the start after visiting every other vertex;

• You can visit the same vertex multiple times, as long as it's not the starting vertex;

• You don't have to use every edge in the graph, but each edge can only be used once.

Is that in P or NP-hard? I tried different approaches to this but now I don't know if I'm wasting my time in case this problem doesn't have an efficient solution.

This problem is NP-hard.

Consider the following variants:

Variant 1: given a graph where each vertex has degree at most three, determine if there is a Hamiltonian path.

Variant 2: given a graph, determine if there is a trail (a path without repeated edges) that visits every vertex at least once.

Variant 1 is NP-hard [1].

Variant 1 can be reduced to variant 2 by mapping to the same graph.

If there is a Hamiltonian path on the graph, the Hamiltonian path is certainly a trail that visits every vertex at least once.

On the other hand, if there is a trail from $u$ to $v$ that visits every vertex at least once, since every vertex in the graph has degree at most three, every vertex except $u$ and $v$ must appear exactly once on the trail. If every vertex appears exactly once, the trail itself is a Hamiltonian path. If $u$ and/or $v$ appear twice, remove the first and/or the last edges on the trail respectively, then the trail becomes a Hamiltonian path. Anyway there is a Hamiltonian path in the graph.

So variant 2 is NP-hard.

Suppose the problem in OP is in P. Given an instance of variant 2, construct a new graph for every pair of vertexes $(u,v)$ by adding a new vertex $s$ and new edges $(s,u)$ and $(v,s)$. Now there is a trail that visits every vertex at least once in the original graph if and only if the answer to the problem in OP on at least one of these new graphs is "yes". So one can solve variant 2 in polynomial time by solving the problem in OP on these new graphs. So the problem in OP is NP-hard.

[1] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884.

StackExchange Computer Science Q#89349, answer score: 3