Is the problem of traversing every vertex of a graph (not necessarily once) without crossing an edge more than once in P?
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.