This is an old question of Aradhana Narula-Tam and Philip Lin that I think deserves wider circulation. It appeared in Discrete Math. 257 (2002), page 613, but not many people have looked at it and it might have a simple solution.
A graph is $k$-trail-ordered if for every list $v_0, \ldots, v_k$ of $k + 1$ distinct vertices, there is a trail (i.e., a walk with no repeated edges) that visits $v_0, \ldots, v_k$ in order (among a possibly longer trail). The question is, is every $k$-edge-connected graph also $k$-trail-ordered? If not, then what is the least edge-connectivity $f(k)$ such that every $f(k)$-edge-connected graph is $k$-trail-ordered?
Note that in the desired trail, each $v_i$ may appear repeatedly, as long as the list of vertices visited has $v_0, \ldots, v_k$ as a sublist in order. The problem arose in the context of a wavelength assignment problem in a WDM optical network. Whitney’s Theorem on edge-disjoint paths yields $f(2)=2$, as desired. In [1] it was proved that $f(3)=3$. Florian Pfender points out that a result of Okamura [2] yields a proof that $f(k)=k$ when $k$ is even, and consequently $f(k) \le k + 1$ when $k$ is odd. Therefore, it remains to decide between $k$ and $k + 1$ when $k$ is odd.
[1] A. Narula-Tam, P. J. Lin, E. Modiano, Efficient routing and wavelength assignment for reconfigurable WDM networks, IEEE J. Selected Areas Comm. 20 (2002) 75–88.
[2] H. Okamura, Paths in $k$-edge-connected graphs, J. Combin. Theory Ser. B 45 (1988) 345–355.
